A350819 -id:A350819 - 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

A061593 Number of ways to place 2n nonattacking kings on a 4 X 2n chessboard.

Original entry on oeis.org

12, 79, 408, 1847, 7698, 30319, 114606, 419933, 1501674, 5266069, 18174084, 61892669, 208424880, 695179339, 2299608732, 7552444115, 24648046806, 79994460139, 258339007890, 830619734681, 2660070154542, 8488515938929, 27000079296648, 85629004867577

Offset: 1

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001

Bruno Berselli, Table of n, a(n) for n = 1..200
D. E. Knuth, Nonattacking kings on a chessboard, 1994.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 90.
H. S. Wilf, The problem of the kings, Elec. J. Combin. 2, 1995.
Index entries for linear recurrences with constant coefficients, signature (9,-28,33,-9).

Column k=2 of A350819.

Cf. A061594, A001787.

[(17*n-109)*3^n+2*Fibonacci(2*n+10): n in [1..30]]; // Vincenzo Librandi, Jul 12 2011

with(combinat): A061593:=n->(17*n-109)*3^n+2*fibonacci(2*n+10): seq(A061593(n), n=1..30); # Wesley Ivan Hurt, Nov 08 2014

Table[(17 n - 109)*3^n + 2 Fibonacci[2 n + 10], {n, 30}] (* Wesley Ivan Hurt, Nov 08 2014 *)
CoefficientList[Series[x (12-29x+33x^2-9x^3)/((1-3x+x^2)(1-3x)^2),{x,0,30}],x] (* or *) LinearRecurrence[{9,-28,33,-9},{0,12,79,408,1847},30] (* Harvey P. Dale, Dec 20 2021 *)

G.f.: x*(12-29*x+33*x^2-9*x^3)/((1-3*x+x^2)*(1-3*x)^2).
a(n) = 9*a(n-1) - 28*a(n-2) + 33*a(n-3) - 9*a(n-4); a(1)=12, a(2)=79, a(3)=408, a(4)=1847.
a(n) = (17*n-109)*3^n + 2*Fibonacci(2*n+10).
a(n) = 17*A027471(n+2) - 126*A000244(n) + A025169(n+4).

A061594 Number of ways to place 3n nonattacking kings on a 6 X 2n chessboard.

Original entry on oeis.org

1, 32, 408, 3600, 26040, 166368, 976640, 5392704, 28432288, 144605184, 714611200, 3449705600, 16333065216, 76081271168, 349524164224, 1586790140800, 7130144209024, 31752978219904, 140298397039232, 615604372260736

Offset: 0

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. E. Knuth, Nonattacking kings on a chessboard, 1994.
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes [_Vaclav Kotesovec_, Feb 06 2010]
H. S. Wilf, The problem of the kings, Elec. J. Combin. 2, 1995.
Index entries for linear recurrences with constant coefficients, signature (19, -148, 604, -1364, 1644, -928, 192).

Column k=3 of A350819.
Cf. A001787, A061593.
Equals 231*A002697(n+1) - 2608*A000302(n) - 384*A000244(n) + 1103*A007070(n-1) + 780*A006012(n+1) + (n+1)*(17*A048580(n) + 12*A007070(n+1)).

a(n)=polcoeff((1+13*x-52*x^2-20*x^3+60*x^4-20*x^5)/((1-3*x)*(1-4*x)^2*(1-4*x+2*x^2)^2)+x*O(x^n),n)

G.f.: (1+13x-52x^2-20x^3+60x^4-20x^5)/((1-3x)(1-4x)^2(1-4x+2x^2)^2).

Explicit formula: (231n-2377)*4^n - 384*3^n + (1953*sqrt(2)/2+1381+(35*sqrt(2)+99/2)*n)*(2+sqrt(2))^n + (1381-1953*sqrt(2)/2+(99/2-35*sqrt(2))*n)*(2-sqrt(2))^n. - Vaclav Kotesovec, Feb 06 2010

Corrected data by Vincenzo Librandi, Oct 12 2011

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.

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.

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 4, 2, 2, 4, 3, 16, 1, 16, 3, 1, 12, 4, 4, 12, 1, 8, 4, 3, 256, 3, 4, 8, 4, 64, 1, 144, 144, 1, 64, 4, 1, 32, 8, 16, 79, 16, 8, 32, 1, 13, 8, 4, 4096, 9, 9, 4096, 4, 8, 13, 5, 208, 1, 1024, 1656, 1, 1656, 1024, 1, 208, 5, 1, 80, 13, 64, 408, 64, 64, 408, 64, 13, 80, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The minimum size of a dominating set is the domination number which in the case of an m X n king graph is given by (ceiling(m/3) * ceiling(n/3)).

			Table begins:
============================================
m\n | 1  2  3    4    5   6      7     8
----+---------------------------------------
  1 | 1  2  1    4    3   1      8     4 ...
  2 | 2  4  2   16   12   4     64    32 ...
  3 | 1  2  1    4    3   1      8     4 ...
  4 | 4 16  4  256  144  16   4096  1024 ...
  5 | 3 12  3  144   79   9   1656   408 ...
  6 | 1  4  1   16    9   1     64    16 ...
  7 | 8 64  8 4096 1656  64 243856 29744 ...
  8 | 4 32  4 1024  408  16  29744  3600 ...
     ...

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 276 terms from Andrew Howroyd)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Rows 1..3 are A347633, A350816, A347633.
Main diagonal is A347554.
Cf. A075561, A218663 (dominating sets), A286849 (minimal dominating sets), A303335, A350818, A350819.

T(n,m) = T(m,n).
T(3*m, 3*n) = 1; T(3*m+1, 3*n) = (m^2 + 5*m + 2)^n; T(3*m+2, 3*n) = (m+2)^n.
T(3*m-1, 3*n-1) = A350819(m, n).

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.

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

A061593 Number of ways to place 2n nonattacking kings on a 4 X 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A061594 Number of ways to place 3n nonattacking kings on a 6 X 2n chessboard.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.