A174558 -id:A174558 - cp's OEIS frontend

A018807 Number of ways to place n^2 nonattacking kings on 2n X 2n chessboard.

1, 4, 79, 3600, 281571, 32572756, 5109144543, 1027533353168, 254977173389319, 75925129079783308, 26568150968269086211, 10749154284380665611224, 4963704194366362387891227, 2588716234142991968960920692, 1511548995678989691821551648635

Offset: 0

David W. Wilson

Rotations and reflections are considered distinct.
Also, number of ways to tile a (2n+1) X (2n+1) board with n^2 2 X 2 tiles and 4n+1 1 X 1 tiles, rotations and reflections counted as distinct. - David W. Wilson, Aug 18 2011
Number of maximum independent vertex sets in the 2n X 2n king graph. - Eric W. Weisstein, Jun 20 2017

David W. Wilson, Table of n, a(n) for n = 0..26
Zealint Blog (Russian) Source for a(12) through a(20), March 14 2011. a(21) through a(26) from same source, July 9 2011.
Tricia Muldoon Brown, Queens, Attack!, The Mathematical Intelligencer (2020).
Tricia Muldoon Brown, Maximum arrangements of nonattacking kings on the 2n × 2n chessboard, Georgia Southern University (2020).
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 160-162.
Michael Larsen, The Problem of Kings, The Electronic Journal of Combinatorics 2, 1995
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Main diagonal of A350819.

Cf. A174558, A174155, A174154, A173782, A173783, A061594, A061593.

Asymptotic (M. Larsen, 1995): log(a(n)) = 2n*log(n) - 2n*log(2) + O(n^(4/5)*log(n)).

a(0) added by Geoffrey H. Morley, Feb 06 2013

A350819 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the 2m X 2n king graph.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 79, 32, 1, 1, 80, 408, 408, 80, 1, 1, 192, 1847, 3600, 1847, 192, 1, 1, 448, 7698, 26040, 26040, 7698, 448, 1, 1, 1024, 30319, 166368, 281571, 166368, 30319, 1024, 1, 1, 2304, 114606, 976640, 2580754, 2580754, 976640, 114606, 2304, 1

Offset: 0

Andrew Howroyd, Jan 17 2022

Number of ways to tile a (2m+1) X (2n+1) board with m*n 2 X 2 tiles and 2m+2n+1 1 X 1 tiles.

For m,n > 0, T(m,n) is the number of minimum dominating sets in the (3m-1) X (3n-1) king graph.

			Table begins:
=============================================
m\n | 0   1    2      3       4        5
----+----------------------------------------
  0 | 1   1    1      1       1        1 ...
  1 | 1   4   12     32      80      192 ...
  2 | 1  12   79    408    1847     7698 ...
  3 | 1  32  408   3600   26040   166368 ...
  4 | 1  80 1847  26040  281571  2580754 ...
  5 | 1 192 7698 166368 2580754 32572756 ...
  ...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Rows 0..12 are A000012, A001787(n+1), A061593, A061594, A173782, A173783, A174154, A174155, A174558, A195648, A195649, A195650, A195651.
Main diagonal is A018807.
Cf. A350815, A350818.

T(m,n) = T(n,m).

T(m,n) = A350818(2*m, 2*n) = A350815(3*m-1, 3*n-1).

A189889 Maximum number of nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

1, 1, 1, 4, 5, 9, 10, 16, 18, 25, 27, 36, 39, 49, 52, 64, 68, 81, 85, 100, 105, 121, 126, 144, 150, 169, 175, 196, 203, 225, 232, 256, 264, 289, 297, 324, 333, 361, 370, 400, 410, 441, 451, 484, 495, 529, 540, 576, 588, 625

Offset: 1

Vaclav Kotesovec, Apr 30 2011

a(n) is the independence number of the Cayley graph on the group Z_n X Z_n with generators (+-e_1, +-e_2)<>(0,0) where e_i is in {0,1} for i=1,2. - Miquel A. Fiol, Aug 07 2024

For n>=4 a(n) is the maximum number of edges of an n-cycle graph with chords not containing any triangle with some edges of the cycle. - Miquel A. Fiol, Sep 20 2024

John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), Theorem 11.1, p.194.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Hernan de Alba, W. Carballosa, J. Leaños, and L. M. Rivera, Independence and matching numbers of some token graphs, arXiv preprint arXiv:1606.06370 [math.CO], 2016.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
Eric Weisstein's World of Mathematics, Kings Problem.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,-1,1).

Cf. A018807, A085801, A172158, A174558, A179428, A180067.

[1] cat [Floor(n*Floor(n/2)/2): n in [2..50]]; // G. C. Greubel, Jan 13 2018

A189889:=n->`if`(n=1,1,floor(n*floor(n/2)/2)); seq(A189889(k), k=1..100); # Wesley Ivan Hurt, Nov 07 2013

Table[If[n==1,1,Floor[(n*Floor[n/2])/2]],{n,1,50}]
CoefficientList[Series[(- x^7 + x^6 + x^5 + 3 * x^3 - x^2 + 1) / (-x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 02 2013 *)
Join[{1},LinearRecurrence[{1,1,-1,1,-1,-1,1},{1,1,4,5,9,10,16},50]] (* Harvey P. Dale, Aug 07 2013 *)

Vec(x*(-x^7 + x^6 + x^5 + 3*x^3 - x^2 + 1) / (-x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1) + O(x^51)) \\ Indranil Ghosh, Mar 09 2017

a(n) = if(n==1, 1, floor((n*floor(n/2))/2)); \\ Indranil Ghosh, Mar 09 2017

def A189889(n): return 1 if n==1 else (n*(n/2))/2 # Indranil Ghosh, Mar 09 2017

a(n) = floor((n*floor(n/2))/2), n > 1 (Watkins and Ricci, 2004).
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) - a(n-6) + a(n-7).
G.f.: x*(-x^7 +x^6 +x^5 +3*x^3 -x^2 +1) / (-x^7 +x^6 +x^5 -x^4+ x^3 -x^2 -x +1).

A195648 Number of ways to place 9n nonattacking kings on a 18 x 2n chessboard.

Original entry on oeis.org

5120, 1501674, 144605184, 7683664202, 282359109140, 8080813574550, 193194265398240, 4035559337688370, 75925129079783308, 1314578079936797520, 21279238303065874504, 325878859655043000344, 4765036384361599508980, 67005992305769489072298, 911373843678367079288192

Offset: 1

Vaclav Kotesovec, Sep 22 2011

nonn

Alex V. Breger, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Non-attacking chess pieces
Vaclav Kotesovec, Generating function
Index entries for linear recurrences with constant coefficients, order 548.

Column k=9 of A350819.

Cf. A174558, A018807, A195653, A195658.

Recurrence order is 548.

A195652 Number of ways to place 8n nonattacking kings on a 16 X 2n cylindrical chessboard.

Original entry on oeis.org

2304, 9476, 47058, 259372, 1536814, 9643562, 63558566, 437500380, 3130270224, 23174548666, 176740657340, 1382652697282, 11052082053262, 89954475408222, 743275585245898, 6219118726337532, 52583297643941856, 448492643088144992, 3853319870967662784

Offset: 1

Vaclav Kotesovec, Sep 22 2011

nonn

This cylinder is horizontal: a chessboard where it is supposed that rows 1 and 2n are in contact (number of columns = 16, number of rows = 2n).

Alex V. Breger, Table of n, a(n) for n = 1..1000
Artem M. Karavaev, Zealint blog (in Russian)
V. Kotesovec, Non-attacking chess pieces
Vaclav Kotesovec, Generating function
Index entries for linear recurrences with constant coefficients, order 208.

Cf. A137432, A174558, A195657.

Recurrence order is 208.

A195657 Number of ways to place 8n nonattacking kings on a vertical cylinder 16 X 2n.

Original entry on oeis.org

512, 17536, 218052, 1599820, 8500668, 36383284, 133538996, 437500380, 1314748124, 3694894500, 9849731140, 25173962492, 62193359676, 149475988116, 351246183572, 810197361564, 1840289301660, 4126688132548, 9154339355684, 20122502355004, 43888598831484

Offset: 1

Vaclav Kotesovec, Sep 22 2011

nonn

Vertical cylinder: a chessboard where it is supposed that the columns 1 and 16 are in contact (number of columns = 16, number of rows = 2n).

V. Kotesovec, Non-attacking chess pieces
Index entries for linear recurrences with constant coefficients, signature (11, -53, 147, -259, 301, -231, 113, -32, 4).

Cf. A195652, A174558, A137432.

Recurrence: a(n) = 4*a(n-9) - 32*a(n-8) + 113*a(n-7) - 231*a(n-6) + 301*a(n-5) - 259*a(n-4) + 147*a(n-3) - 53*a(n-2) + 11*a(n-1).
G.f.: -(1 + 501*x + 11957*x^2 + 52145*x^3 + 55651*x^4 + 13919*x^5 + 695*x^6 + 27*x^7)/((x-1)^7*(2*x-1)^2).
a(n) = (1751437*n - 15876635)*2^n + 8431/45*n^6 + 22263/5*n^5 + 500633/9*n^4 + 1381699/3*n^3 + 117001024/45*n^2 + 138801256/15*n + 15876636.

cp's OEIS Frontend

A018807 Number of ways to place n^2 nonattacking kings on 2n X 2n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A350819 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the 2m X 2n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A189889 Maximum number of nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A195648 Number of ways to place 9n nonattacking kings on a 18 x 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Formula

A195652 Number of ways to place 8n nonattacking kings on a 16 X 2n cylindrical chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A195657 Number of ways to place 8n nonattacking kings on a vertical cylinder 16 X 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula