A179403 -id:A179403 - cp's OEIS frontend

A193580 Triangle read by rows: T(n,k) = number of ways to place k nonattacking kings on an n X n board.

1, 1, 1, 1, 4, 1, 9, 16, 8, 1, 1, 16, 78, 140, 79, 1, 25, 228, 964, 1987, 1974, 978, 242, 27, 1, 1, 36, 520, 3920, 16834, 42368, 62266, 51504, 21792, 3600, 1, 49, 1020, 11860, 85275, 397014, 1220298, 2484382, 3324193, 2882737, 1601292, 569818, 129657, 18389, 1520, 64, 1

Offset: 0

Andrew Woods, Aug 27 2011

Rows 2n and 2n-1 both contain 1 + n^2 entries. Cf. A008794.
Row n sums to A063443(n+1).
Number of walks of length n-1 on a graph in which each node represents a 11-avoiding n-bit binary sequence B and adjacency of B and B' is determined by B'&(B|(B<<1)|(B>>1))=0 and the total number of nonzero bits in the walk is k.
Row n gives the coefficients of the independence polynomial of the n X n king graph. - Eric W. Weisstein, Jun 20 2017

			The table begins with T(0,0):
  1;
  1,   1;
  1,   4;
  1,   9,  16,   8,   1;
  1,  16,  78, 140,  79;
  ...
T(4,3) = 140 because there are 140 ways to place 3 kings on a 4 X 4 chessboard so that no king threatens any other.

Norman Biggs, Algebraic Graph Theory, Cambridge University Press, New York, NY, second edition, 1993.

Liang Kai, Rows n = 0..26, flattened (Rows n = 0..20 from Andrew Woods, row n = 21 from Alois P. Heinz)
Kai Liang, Independent Set Enumeration in King Graphs by Tensor Network Contractions, arXiv:2505.12776 [math.CO], 2025. See p. 1.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares arXiv:1609.03964 [math.CO], 2016, Section 4.1.
Johan Nilsson, On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, King Graph

Columns 2 to 10: A061995, A061996, A061997, A061998, A172158, A194788, A201369, A201771, A220467.
Diagonal: A201513.
Cf. A179403, etc., for extension to toroidal boards.
Cf. A166540, etc., for extension into three dimensions.
Cf. A098487 for a clipped version.
Row n sums to A063443(n+1).

T(n, 0) = 1;
T(n, 1) = n^2;
T(2n-1, n^2-1) = n^3;
T(2n-1, n^2) = 1.

A179424 Number of ways to place 4 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 12, 575, 9837, 63553, 265008, 853497, 2312925, 5532967, 12037068, 24293243, 46125317, 83243925, 143918272, 239811333, 387002853, 607226187, 929346700, 1391111127, 2041198973, 2941608713, 4170413232, 5824920625, 8025278157, 10918558863, 14683371948, 19535039827, 25731386325

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (9, -36, 84, -126, 126, -84, 36, -9, 1).

Cf. A061997, A179403, A179404.

CoefficientList[Series[x^3 (160 x^9 - 963 x^8 + 2054 x^7 - 1308 x^6 - 963 x^5 - 375 x^4 + 5288 x^3 - 5094 x^2 -467 x - 12) / (x - 1)^9, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 01 2013 *)

Explicit formula: a(n) = 1/24*n^2*(n^6-54*n^4+1019*n^2-6798), n>=5.

G.f.: x^4*(160*x^9 - 963*x^8 + 2054*x^7 - 1308*x^6 - 963*x^5 - 375*x^4 + 5288*x^3 - 5094*x^2 - 467*x - 12)/(x-1)^9.

A179404 Number of ways to place 3 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 48, 600, 3108, 10388, 27328, 61668, 124900, 233288, 409008, 681408, 1088388, 1677900, 2509568, 3656428, 5206788, 7266208, 9959600, 13433448, 17858148, 23430468, 30376128, 38952500, 49451428, 62202168, 77574448, 95981648, 117884100

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (7,-21,35,-35,21,-7,1).

Cf. A061996, A179403.

CoefficientList[Series[- 4 x^3 (12 x^6 - 67 x^5 + 140 x^4 - 112 x^3 - 21 x^2 + 66 x + 12) / (x - 1)^7, {x, 0, 40}], x] (* Vincenzo Librandi, Jun 01 2013 *)
LinearRecurrence[{7,-21,35,-35,21,-7,1},{0,0,0,48,600,3108,10388,27328,61668,124900},30] (* Harvey P. Dale, Aug 04 2024 *)

Explicit formula: a(n) = 1/6*n^2*(n^4 -27*n^2 +194), n>=4.

G.f.: -4*x^4*(12*x^6 -67*x^5 +140*x^4 -112*x^3 -21*x^2 +66*x +12)/(x-1)^7.

A179425 Number of ways to place 5 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 10, 14940, 229908, 1678336, 8155404, 30614620, 96011322, 263506752, 652150382, 1485650012, 3161648520, 6355083264, 12167739256, 22339050588, 39536586430, 67748508480, 112804636266, 183057635420, 290261282204, 450688785408, 686540794500, 1027700020828, 1513897376994, 2197363228480, 3146046781446, 4447496831580

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (11, -55, 165, -330, 462, -462, 330, -165, 55, -11, 1).

Cf. A061998, A179403, A179404, A179424.

CoefficientList[Series[- 2 x^4 (260 x^11 - 1932 x^10 + 6567 x^9 - 16223 x^8 + 38507 x^7 - 77869 x^6 + 102208 x^5 - 61576 x^4 - 15301 x^3 + 33059 x^2 + 7415 x + 5) / (x - 1)^11, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 01 2013 *)

Explicit formula: a(n) = 1/120*n^2*(n^8-90n^6+3155n^4-51450n^2+332544), n>=6.

G.f.: -2x^5*(260x^11 - 1932x^10 + 6567x^9 - 16223x^8 + 38507x^7 - 77869x^6 + 102208x^5 - 61576x^4 - 15301x^3 + 33059x^2 + 7415x + 5)/(x-1)^11.

A179426 Number of ways to place 6 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 0, 10596, 486668, 7063520, 55345356, 299491100, 1263811604, 4455716184, 13701863604, 37823872044, 95648273100, 224887404416, 497181121100, 1042609380588, 2088337713332, 4017815773400, 7459198321428, 13414493857116, 23444476061772, 39928736913120, 66425550447500, 108162598959740, 172697249542932, 270794133842456, 417578468928308, 634036069773900

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (13, -78, 286, -715, 1287, -1716, 1716, -1287, 715, -286, 78, -13, 1).

Cf. A172158, A179403, A179404, A179424, A179425.

CoefficientList[Series[4 x^5 (426 x^13 - 4263 x^12 + 22311 x^11 - 82449 x^10 + 220918 x^9 - 391803 x^8 + 369356 x^7 + 10716 x^6 - 382230 x^5 + 163719 x^4 + 387689 x^3 - 390831 x^2 - 87230 x - 2649) / (x - 1)^13, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 01 2013 *)

a(n) = 1/720*n^2*(n^10 -135*n^8 +7525*n^6 -217665*n^4 +3289354*n^2 -20949480), n>=7.

G.f.: 4*x^6*(426*x^13 - 4263*x^12 + 22311*x^11 - 82449*x^10 + 220918*x^9 - 391803*x^8 + 369356*x^7 + 10716*x^6 - 382230*x^5 + 163719*x^4 + 387689*x^3 - 390831*x^2 - 87230*x - 2649)/(x-1)^13.

A194650 Number of ways to place 2 nonattacking kings on an n X n cylindrical chessboard.

Original entry on oeis.org

0, 0, 9, 68, 215, 504, 1001, 1784, 2943, 4580, 6809, 9756, 13559, 18368, 24345, 31664, 40511, 51084, 63593, 78260, 95319, 115016, 137609, 163368, 192575, 225524, 262521, 303884, 349943, 401040, 457529, 519776, 588159, 663068, 744905, 834084, 931031, 1036184

Offset: 1

Vaclav Kotesovec, Aug 31 2011

nonn

V. Kotesovec, Number of ways of placing non-attacking queens, kings, bishops and knights
Index entries for linear recurrences with constant coefficients, signature (5, -10, 10, -5, 1).

Cf. A061995, A179403.

CoefficientList[Series[x^2*(4*x^4 - 19*x^3 + 35*x^2 - 23*x - 9)/(x - 1)^5, {x, 0, 50}], x] (* Wesley Ivan Hurt, Dec 27 2023 *)

a(n) = 1/2*n*(n^3 - 9*n + 6), n>=3.

G.f.: x^3*(4*x^4 - 19*x^3 + 35*x^2 - 23*x - 9)/(x-1)^5.

A179427 Number of ways to place 7 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 0, 3420, 576856, 19760512, 270487188, 2209065700, 12914201256, 59659859232, 231216019632, 781647658596, 2367858314700, 6553746728448, 16815788711212, 40446802230372, 92003239814224, 199311860224800, 413589922308360, 825997764087012, 1594007700404532, 2982430581363072, 5425904270482500, 9622254525739492, 16669554533555832, 28264133502586912, 46982453295836640, 76676963241363300

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (15, -105, 455, -1365, 3003, -5005, 6435, -6435, 5005, -3003, 1365, -455, 105, -15, 1).

Cf. A179403, A179404, A179424, A179425, A179426.

CoefficientList[Series[- 4 x^5 (1379 x^16 - 18219 x^15 + 124755 x^14 - 553765 x^13 + 1657983 x^12 - 3369984 x^11 + 4870575 x^10 - 6400905 x^9 + 10992208 x^8 - 19069951 x^7 + 21246441 x^6 - 8631071 x^5 - 7797385 x^4 + 8273322 x^3 + 2866693 x^2 + 131389 x + 855) / (x - 1)^15, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 01 2013 *)

Explicit formula: a(n) = 1/5040*n^2*(n^12 -189*n^10 +15295*n^8 -681135*n^6 +17692024*n^4 -255655596*n^2 +1617230880), n>=8.

G.f.: -4*x^6*(1379*x^16 - 18219*x^15 + 124755*x^14 - 553765*x^13 + 1657983*x^12 - 3369984*x^11 + 4870575*x^10 - 6400905*x^9 + 10992208*x^8 - 19069951*x^7 + 21246441*x^6 - 8631071*x^5 - 7797385*x^4 + 8273322*x^3 + 2866693*x^2 + 131389*x + 855)/(x-1)^15.

A179428 Number of ways to place 8 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 0, 486, 346381, 36285336, 956078397, 12428297150, 104000525596, 643409498286, 3191250652226, 13361641961066, 48905750870775, 160414160371552, 480243686391743, 1330654487994234, 3449609146025210, 8439769551278350, 19624142987739108, 43616849672119790, 93112709811981557, 191696927842663704, 381920049400830625, 738532765420347014, 1389708580432837752, 2550402748009811870, 4573836436177381798, 8029626473495462850

Offset: 1

Vaclav Kotesovec, Jan 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (17, -136, 680, -2380, 6188, -12376, 19448, -24310, 24310, -19448, 12376, -6188, 2380, -680, 136, -17, 1).

Cf. A179403, A179404, A179424, A179425, A179426, A179427.

CoefficientList[Series[x^5 (17728 x^19 - 301964 x^18 + 2573500 x^17 - 13833040 x^16 + 51521058 x^15 - 143708688 x^14 + 325486412 x^13 - 629393865 x^12 + 996601251 x^11 - 1090603627 x^10 + 426710617 x^9 + 807953488 x^8 - 1328885640 x^7 + 262625618 x^6 + 1106513030 x^5 - 875387697 x^4 - 386005021 x^3 - 30462955 x^2 - 338119 x - 486) / (x - 1)^17, {x, 0, 50}], x] (* Vincenzo Librandi, Jun 01 2013 *)

a(n) = 1/40320*n^2 * (n^14 -252*n^12 +27874*n^10 -1759800*n^8 +68745649*n^6 -1669136028*n^4 +23447322156*n^2 -147931524720), n>=9.

G.f.: x^6*(17728x^19 - 301964x^18 + 2573500x^17 - 13833040x^16 + 51521058x^15 - 143708688x^14 + 325486412x^13 - 629393865x^12 + 996601251x^11 - 1090603627x^10 + 426710617x^9 + 807953488x^8 - 1328885640x^7 + 262625618x^6 + 1106513030x^5 - 875387697x^4 - 386005021x^3 - 30462955x^2 - 338119x - 486)/(x-1)^17.

A180067 Number of ways to place 9 nonattacking kings on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 0, 28, 81095, 42752576, 2436444603, 53633024900, 666519047964, 5655962632720, 36502953719310, 191587564345044, 854990702601025, 3346890268570368, 11756179090049177, 37692541754516628, 111774885566128630, 309788198526691600

Offset: 1

Vaclav Kotesovec, Jan 15 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. 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 (19, -171, 969, -3876, 11628, -27132, 50388, -75582, 92378, -92378, 75582, -50388, 27132, -11628, 3876, -969, 171, -19, 1).

Cf. A179403, A179404, A179424, A179425, A179426, A179427, A179428.

CoefficientList[Series[- x^5 (56520 x^22 - 1215064 x^21 + 12642984 x^20 - 82438064 x^19 + 378510176 x^18 - 1315100032 x^17 + 3593010018 x^16 - 7742517098 x^15 + 12798616135 x^14 - 15614945085 x^13 + 14742135008 x^12 - 17197088896 x^11 + 33440162097 x^10 - 55183782403 x^9 + 50601858342 x^8 - 7249042450 x^7 - 32800069391 x^6 + 23010354469 x^5 + 14572795412 x^4 + 1637985772 x^3 + 41216559 x^2 + 80563 x + 28) / (x - 1)^19, {x, 0, 40}], x] (* Vincenzo Librandi, Jun 01 2013 *)

a(n) = 1/362880*n^2 * (n^16 -324*n^14 +46914*n^12 -3975048*n^10 +216203169*n^8 -7756575876*n^6 +179987135516*n^4 -2481599151792*n^2 +15651056776320), n>=10.
G.f.: -x^6*(56520x^22 - 1215064x^21 + 12642984x^20 - 82438064x^19 + 378510176x^18 - 1315100032x^17 + 3593010018x^16 - 7742517098x^15 + 12798616135x^14 - 15614945085x^13 + 14742135008x^12 - 17197088896x^11 + 33440162097x^10 - 55183782403x^9 + 50601858342x^8 - 7249042450x^7 - 32800069391x^6 + 23010354469x^5 + 14572795412x^4 + 1637985772x^3 + 41216559x^2 + 80563x + 28)/(x-1)^19.
General asymptotic formula for number of ways to place k nonattacking kings on an n X n toroidal board: n^2k/k! - 9/2*n^(2k-2)/(k-2)! + (243k+47)*n^(2k-4)/(24*(k-3)!) - (243k^2+141k+80)*n^(2k-6)/(16*(k-4)!) + (98415k^3+114210k^2+140645k+101762)*n^(2k-8)/(5760*(k-5)!)-...

cp's OEIS Frontend

A193580 Triangle read by rows: T(n,k) = number of ways to place k nonattacking kings on an n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A179424 Number of ways to place 4 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A179404 Number of ways to place 3 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A179425 Number of ways to place 5 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A179426 Number of ways to place 6 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A194650 Number of ways to place 2 nonattacking kings on an n X n cylindrical chessboard.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A179427 Number of ways to place 7 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A179428 Number of ways to place 8 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A180067 Number of ways to place 9 nonattacking kings on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs