A018807 -id:A018807 - cp's OEIS frontend

A137432 Number of ways to place n^2 nonattacking kings on a 2n X 2n cylindrical chessboard.

1, 4, 32, 344, 4460, 66532, 1118398, 20984924, 437500380, 10105541204, 257860425672, 7241521734020, 222770819826574, 7466859257161488, 271156951835070930, 10609740515840572076, 444982726973034212924, 19911203110764903275188, 946564783226311159219150

Offset: 0

Vaclav Kotesovec, Aug 31 2011

Rintaro Matsuo, Table of n, a(n) for n = 0..384 (terms 1..31 from Alex V. Breger)
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 209-210.
Artem M. Karavaev, Zealint blog (in Russian)
Rintaro Matsuo, Polynomial-time algorithm
Rintaro Matsuo, a(1)..a(800)

Cf. A018807, A173033.

Conjecture: limit of a(n+1)/(n*a(n)) as n->infinity is e.

a(n) ~ c * n^n, where c = 2*exp(1)*(exp(1) - 1)^2 / (exp(1) - 2)^2 = 31.1116835720490503682643922791052352237386275089... - Vaclav Kotesovec, Jul 29 2023, updated Mar 18 2024

a(11)-a(12) from Vaclav Kotesovec, Sep 08 2011
a(13)-a(27) from Alex V. Breger, Sep 10 2011
a(28)-a(31) from Alex V. Breger, Sep 12 2011
a(0)=1 prepended by Andrew Howroyd, Mar 26 2023

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).

A173782 Number of ways to place 4n nonattacking kings on an 8 X 2n chessboard.

Original entry on oeis.org

80, 1847, 26040, 281571, 2580754, 21137959, 159636030, 1134127305, 7683664202, 50123713793, 317076250136, 1955475353217, 11806000507544, 70004699407151, 408747986045656, 2355077855615435, 13413115039118042, 75623103424916527

Offset: 1

Vaclav Kotesovec, Feb 24 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (44, -887, 10855, -90083, 536398, -2365292, 7860674, -19852652, 38152568, -55523880, 60518766, -48502595, 27783210, -10888525, 2721025, -382125, 22500).

Column k=4 of A350819.

Cf. A061594, A061593, A018807.

CoefficientList[Series[(22500 x^16 - 382125 x^15 + 2723005 x^14 - 10917322 x^13 + 27938661 x^12 - 48873227 x^11 + 60780149 x^10 - 54895129 x^9 + 36368733 x^8 - 17776175 x^7 + 6499001 x^6 - 1854479 x^5 + 446565 x^4 - 94300 x^3 + 15732 x^2 - 1673 x + 80) / ((1 - x) (x^2 - 4 x + 1) (x^3 - 6 x^2 + 5 x - 1) (4 x - 1) (5 x - 1)^2 (3 x^2 - 5 x + 1)^2 (5 x^2 - 5 x + 1)^2),{x, 0, 50}], x] (* Vincenzo Librandi, May 30 2013 *)

G.f.: x*(22500*x^16 -382125*x^15 +2723005*x^14 -10917322*x^13 +27938661*x^12 -48873227*x^11 +60780149*x^10 -54895129*x^9 +36368733*x^8 -17776175*x^7 +6499001*x^6 -1854479*x^5+446565*x^4 -94300*x^3 +15732*x^2 -1673*x+80) / ((1-x) *(x^2-4*x+1) *(x^3-6*x^2+5*x-1) *(4*x-1) *(5*x-1)^2 *(3*x^2-5*x+1)^2 *(5*x^2-5*x+1)^2).
Recurrence: a(n) = 44a(n-1) -887a(n-2) +10855a(n-3) -90083a(n-4) +536398a(n-5) -2365292a(n-6) +7860674a(n-7) -19852652a(n-8) +38152568a(n-9) -55523880a(n-10) +60518766a(n-11) -48502595a(n-12) +27783210a(n-13) -10888525a(n-14) +2721025a(n-15) -382125a(n-16) +22500a(n-17), n>17.
a(n) = (-12505804889/302760 +7963567/2610*n)*5^n +3872/3*4^n -1/24 +(135343*sqrt(3)/18 -234421/18)*(2 -sqrt(3))^n -(135343*sqrt(3)/18 +234421/18)*(2 +sqrt(3))^n +(33301/5 -74461*sqrt(5)/25 +(141*sqrt(5)/25 -63/5)*n)*((5 -sqrt(5))/2)^n +(74461*sqrt(5)/25 +33301/5 - (141*sqrt(5)/25 + 63/5)*n)*((5 +sqrt(5))/2)^n + (4306740/169 - 1194474*sqrt(13)/169 + (139103/117 - 501541*sqrt(13)/1521)*n)*((5 -sqrt(13))/2)^n +(1194474*sqrt(13)/169 +4306740/169 +(501541*sqrt(13)/1521 +139103/117)*n)*((5 +sqrt(13))/2)^n +72*(b*(3504697*c - 11380560) -11380560*c +36953816)/(142129*(a - b)*(a - c))*a^n +72*(a*(3504697*c - 11380560) - 8*(1422570*c - 4619227))/(142129*(a - b)*(c - b))*b^n +72*(a*(3504697*b - 11380560) -8*(1422570*b - 4619227))/(142129*(a - c)*(b - c))*c^n, where: a=2-2*sin(Pi/14), b=2+2*sin(3*Pi/14), c=2-2*cos(Pi/7). - Vaclav Kotesovec, added Mar 01 2010, updated Mar 29 2010.

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).

A173783 Number of ways to place 5n nonattacking kings on a 10 X 2n chessboard.

Original entry on oeis.org

192, 7698, 166368, 2580754, 32572756, 357365350, 3544192112, 32580145116, 282359109140, 2335042206624, 18589546217696, 143422674213726, 1077891352444220, 7923134615854816, 57146364209686016, 405497952834408698

Offset: 1

Vaclav Kotesovec, Feb 24 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (85, -3441, 88303, -1613002, 22327010, -243429637, 2145452227, -15565947848, 94202823084, -480152808502, 2075863416838, -7651361422835, 24128330540449, -65240466585284, 151411770874148, -301613628545814, 515173613407544, -753006145475828, 939001403456656, -994821988961592, 890558910282768, -668920434927504, 417832289937792, -214574645977920, 89258591798784, -29486236792320, 7526493775872, -1426182018048, 188221833216, -15390756864, 585252864).

Column k=5 of A350819.

Cf. A173782, A061594, A061593, A018807.

CoefficientList[Series[2 (292626432 x^30 - 7695378432 x^29 + 94084706304 x^28 - 712519981056 x^27 + 3757888797696 x^26 - 14715718076160 x^25 + 44556058968960 x^24 - 107273952716256 x^23 + 209645023363168 x^22 - 337824014576768 x^21 + 454329405135504 x^20 - 514643686425920 x^19 + 494203416082160 x^18 - 403847150294172 x^17 + 281135354205764 x^16 - 166453721883480 x^15 + 83456844800670 x^14 - 35182845104124 x^13 + 12345883162136 x^12 - 3557728594620 x^11 + 827346101101 x^10 - 152042822189 x^9 + 21726065190 x^8 - 2499103126 x^7 + 289877178 x^6 - 45817212 x^5 + 7810422 x^4 - 1012942 x^3 + 86355 x^2 - 4311 x + 96) / ((1 - 2 x) (x^2 - 4 x + 1) (4 x - 1) (6 x - 1)^2 (2 x^2 - 4 x + 1) (2 x^2 - 5 x + 1) (4 x^2 - 6 x + 1)^2 (6 x^2 - 6 x + 1)^2 (7 x^2 - 6 x + 1)^2 (2 x^3 - 8 x^2 + 6 x - 1) (3 x^3 - 9 x^2 + 6 x - 1)^2), {x, 0, 50}], x] (* Vincenzo Librandi, May 30 2013 *)

G.f.: 2*x*(292626432*x^30 -7695378432*x^29 +94084706304*x^28 -712519981056*x^27 +3757888797696*x^26 -14715718076160*x^25 +44556058968960*x^24 -107273952716256*x^23 +209645023363168*x^22 -337824014576768*x^21 +454329405135504*x^20 -514643686425920*x^19 +494203416082160*x^18 -403847150294172*x^17 +281135354205764*x^16 -166453721883480*x^15 +83456844800670*x^14 -35182845104124*x^13 +12345883162136*x^12 -3557728594620*x^11 +827346101101*x^10 -152042822189*x^9 +21726065190*x^8 -2499103126*x^7 +289877178*x^6 -45817212*x^5 +7810422*x^4 -1012942*x^3 +86355*x^2 -4311*x+96) / ((1-2*x) *(x^2-4*x+1) *(4*x-1) *(6*x-1)^2 *(2*x^2-4*x+1) *(2*x^2-5*x+1) *(4*x^2-6*x+1)^2 *(6*x^2-6*x+1)^2 *(7*x^2-6*x+1)^2 *(2*x^3-8*x^2+6*x-1) *(3*x^3-9*x^2+6*x-1)^2).

Recurrence: a(n) = 85a(n-1) -3441a(n-2) +88303a(n-3) -1613002a(n-4) +22327010a(n-5) -243429637a(n-6) +2145452227a(n-7) -15565947848a(n-8) +94202823084a(n-9) -480152808502a(n-10) +2075863416838a(n-11) -7651361422835a(n-12) +24128330540449a(n-13) -65240466585284a(n-14) +151411770874148a(n-15) -301613628545814a(n-16) +515173613407544a(n-17) -753006145475828a(n-18) +939001403456656a(n-19) -994821988961592a(n-20) +890558910282768a(n-21) -668920434927504a(n-22) +417832289937792a(n-23) -214574645977920a(n-24) +89258591798784a(n-25) -29486236792320a(n-26) +7526493775872a(n-27) -1426182018048a(n-28) +188221833216a(n-29) -15390756864a(n-30) +585252864a(n-31), n>31.

A174154 Number of ways to place 6n nonattacking kings on a 12 x 2n chessboard.

Original entry on oeis.org

1, 448, 30319, 976640, 21137959, 357365350, 5109144543, 64737165162, 749160010737, 8080813574550, 82425144219429, 803491953235264, 7545414941610145, 68680800264413920, 608889093898882615, 5278006575696293456, 44873569636443901967, 375159494582050088590, 3090799708762482416287

Offset: 0

Vaclav Kotesovec, Mar 10 2010

nonn

Ray Chandler, Table of n, a(n) for n = 0..1172
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Vaclav Kotesovec, G.f.
Index entries for linear recurrences with constant coefficients, order 75.

Column k=6 of A350819.

Cf. A061594, A061593, A018807, A173782, A173783.

More terms from Jinyuan Wang, Feb 26 2020

a(0)=1 prepended by Andrew Howroyd, Mar 26 2023

A174558 Number of ways to place 8n nonattacking kings on a 16 x 2n chessboard.

Original entry on oeis.org

2304, 419933, 28432288, 1134127305, 32580145116, 749160010737, 14677177838054, 254977173389319, 4035559337688370, 59315924213143597, 821112680030028632, 10819171744710664383, 136800806311499633208, 1670597119210336446533, 19804685547188544317522, 228865023358344707514899, 2586924156960003793687130, 28681715460054576813151389, 312656761422008821513384848, 3357651442822195404605813501

Offset: 1

Vaclav Kotesovec, Nov 29 2010

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013
Vaclav Kotesovec, G.f.
Index entries for linear recurrences with constant coefficients, order 307.

Column k=8 of A350819.

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

Asymptotic formula for number of ways to place m x n nonattacking kings on a 2m x 2n chessboard (this case is m=8): f(m,n) ~ k(m)*n*(m+1)^n
First values of k(m):
k(1)=1,
k(2)=17,
k(3)=231,
k(4)=3051.17509,
k(5)=40881.99638,
k(6)=563050.92363,
k(7)=8008508.28858,
k(8)=117833087.45133
k(9)=1794306724.77472
k(10)=28276454469.76459
k(11)=461049875818.05305
k(12)=7775513990776.97046
k(13)=135589372611110.17367
k(14)=2443990803097108.58764
k(15)=45522076785406201.22572
k(16)=875939597341977670.66777
k(17)=17407856624734801679.11613
k(18)=357216046100723515478.42809
k(19)=7567101689641721175327.80272

A174155 Number of ways to place 7n nonattacking kings on a 14 x 2n chessboard.

Original entry on oeis.org

1, 1024, 114606, 5392704, 159636030, 3544192112, 64737165162, 1027533353168, 14677177838054, 193194265398240, 2383116363555182, 27889602664055396, 312546900470579954, 3378090945290324892, 35412239480510055916, 361670315347336810428, 3611858972942315054336, 35375586671457852212944

Offset: 0

Vaclav Kotesovec, Mar 10 2010

nonn

Ray Chandler, Table of n, a(n) for n = 0..1096
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Vaclav Kotesovec, G.f.
Index entries for linear recurrences with constant coefficients, order 124.

Column k=7 of A350819.

Cf. A018807, A061594, A061593, A173782, A173783, A174154.

More terms from Jinyuan Wang, Feb 26 2020

a(0)=1 prepended by Andrew Howroyd, Mar 26 2023

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.

A195649 Number of ways to place 10n nonattacking kings on a 20 x 2n chessboard.

Original entry on oeis.org

11264, 5266069, 714611200, 50123713793, 2335042206624, 82425144219429, 2383116363555182, 59315924213143597, 1314578079936797520, 26568150968269086211, 498306336520679626558, 8788579757709800395287, 147246060712874767006100, 2362334876238883501403023

Offset: 1

Vaclav Kotesovec, Sep 22 2011

nonn

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

Column k=10 of A350819.

Cf. A018807, A195654, A195659.

Recurrence order is 1318.

cp's OEIS Frontend

A137432 Number of ways to place n^2 nonattacking kings on a 2n X 2n cylindrical chessboard.

Views

Author

Keywords

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

A173782 Number of ways to place 4n nonattacking kings on an 8 X 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

A173783 Number of ways to place 5n nonattacking kings on a 10 X 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A174154 Number of ways to place 6n nonattacking kings on a 12 x 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Extensions

A174558 Number of ways to place 8n nonattacking kings on a 16 x 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Formula

A174155 Number of ways to place 7n nonattacking kings on a 14 x 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula