A172158 -id:A172158 - 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.

A201513 Number of ways to place n nonattacking kings on an n X n board.

Original entry on oeis.org

1, 1, 0, 8, 79, 1974, 62266, 2484382, 119138166, 6655170642, 423677826986, 30242576462856, 2390359529372724, 207127434998494421, 19516867860507198208, 1986288643031862123264, 217094567491104327256049, 25357029929230564723578520, 3151672341378566296926684684

Offset: 0

Vaclav Kotesovec, Dec 02 2011

Alois P. Heinz, Table of n, a(n) for n = 0..21 (terms n=1..20 from Andrew Woods)
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 77.

Cf. A061995, A061996, A061997, A061998, A172158, A194788, A201369.
Cf. A063443.
Main diagonal of A098487, A193580.

Asymptotics (Vaclav Kotesovec, Nov 29 2011): n^(2n)/n!*exp(-9/2).

a(0)=1 prepended by Alois P. Heinz, May 11 2017

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

A279115 Number of non-equivalent ways to place 6 non-attacking kings on an n X n board.

Original entry on oeis.org

0, 0, 0, 0, 143, 7855, 153311, 1505465, 9729830, 47235703, 186615092, 630338668, 1882894541, 5092130575, 12686490993, 29498296651, 64664954532, 134715649055, 268438970166, 514318521438, 951646716171, 1706721390223, 2976056379875, 5058962536429, 8402677784738, 13663807273607

Offset: 1

Heinrich Ludwig, Dec 09 2016

Rotations and reflections of placements are not counted. If they are to be counted, see A172158.

			There are 143 non-equivalent ways to place 6 non-attacking kings on a 5 X 5 board, e.g., this one:
   K...K
   .....
   K...K
   .....
   K...K

Heinrich Ludwig, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-8,-22,69,-8,-176,168,182,-364,0,364,-182,-168,176,8,-69,22,8,-6,1).

Cf. A172158, A279111 (2 kings), A279112 (3 kings), A279113 (4 kings), A279114 (5 kings), A279116 (7 kings), A279117, A236679.

concat(vector(4), Vec(x^5*(143 +6997*x +107325*x^2 +651585*x^3 +2086471*x^4 +3732434*x^5 +3669293*x^6 +1297859*x^7 -708745*x^8 -592136*x^9 +247421*x^10 +258649*x^11 -53671*x^12 -77714*x^13 +4451*x^14 +14969*x^15 +1018*x^16 -1741*x^17 -234*x^18 +106*x^19) / ((1 -x)^13*(1 +x)^7) + O(x^30))) \\ Colin Barker, Dec 09 2016

a(n) = (n^12 - 135*n^10 + 180*n^9 + 7465*n^8 - 18840*n^7 - 202468*n^6 + 749880*n^5 + 2446764*n^4 - 13439400*n^3 - 3570352*n^2 + 89413920*n - 107694720 + IF(MOD(n, 2) = 1, 122*n^6 - 1020*n^5 + 1955*n^4 + 840*n^3 + 5753*n^2 - 42840*n + 132975))/5760 for n>=5.
a(n) = 6*a(n-1) - 8*a(n-2) - 22*a(n-3) + 69*a(n-4) - 8*a(n-5) - 176*a(n-6) + 168*a(n-7) + 182*a(n-8) - 364*a(n-9) + 364*a(n-11) - 182*a(n-12) - 168*a(n-13) + 176*a(n-14) + 8*a(n-15) - 69*a(n-16) + 22*a(n-17) + 8*a(n-18) - 6*a(n-19) + a(n-20) for n>=25.
G.f.: x^5*(143 +6997*x +107325*x^2 +651585*x^3 +2086471*x^4 +3732434*x^5 +3669293*x^6 +1297859*x^7 -708745*x^8 -592136*x^9 +247421*x^10 +258649*x^11 -53671*x^12 -77714*x^13 +4451*x^14 +14969*x^15 +1018*x^16 -1741*x^17 -234*x^18 +106*x^19) / ((1 -x)^13*(1 +x)^7). - Colin Barker, Dec 09 2016

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

Original entry on oeis.org

0, 0, 0, 0, 242, 51504, 2484382, 44601420, 450193818, 3112919712, 16471667554, 71393226972, 265069706646, 869583076752, 2577681275622, 7020477731884, 17794428237522, 42397762374912, 95726217156906, 206149749502012, 425731784898894, 846919172059632

Offset: 1

Andrew Woods, Sep 02 2011

nonn

V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes

Cf. A061995, A061996, A061997, A061998, A172158.

a(n) = (n^14 - 189n^12 + 252n^11 + 15211n^10 - 38640n^9 - 649215n^8 + 2408700n^7 + 14771764n^6 - 75856200n^5 - 144099396n^4 + 1198867488n^3 - 255900576n^2 - 7543005120n + 10617929280)/5040, n>=6. - Andrew Woods, Sep 02 2011

G.f.: 2*x^5*(1930*x^15 - 20052*x^14 + 87663*x^13 - 265681*x^12 + 816798*x^11 - 2117376*x^10 + 2865281*x^9 + 557737*x^8 - 6577818*x^7 + 3848604*x^6 + 8828017*x^5 - 9464319*x^4 - 6316750*x^3 - 868616*x^2 - 23937*x - 121)/ (x-1)^15. - Vaclav Kotesovec, Nov 06 2011

A286441 Number of ways to tile an n X n X n triangular area with six 2 X 2 X 2 triangular tiles and an appropriate number (= n^2-24) of 1 X 1 X 1 tiles.

Original entry on oeis.org

0, 219, 15160, 369787, 4366982, 32450843, 175628996, 755759531, 2734928266, 8643796747, 24503068784, 63522668395, 152816062222, 345005930315, 737473609532, 1503178571195, 2938515130514, 5535661080283, 10089397100584, 17851538034587, 30750030827926, 51694565135803

Offset: 5

Heinrich Ludwig, May 12 2017

Rotations and reflections of tilings are counted. Tiles of the same size are not distinguishable.

For an analogous problem concerning square tiles, see A172158.

			There are 219 ways of tiling a triangular area of side 6 with 6 tiles of side 2 and an appropriate number (= 12) of tiles of side 1. See illustration in links section.

Heinrich Ludwig, Table of n, a(n) for n = 5..100
Heinrich Ludwig, Illustration of tiling a 6X6X6 area
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Cf. A172158, A286436, A286437, A286438, A286439, A286440, A286442.

concat(0, Vec( x^6*(219 + 12313*x + 189789*x^2 + 679597*x^3 + 344288*x^4 - 808902*x^5 + 54074*x^6 + 289970*x^7 - 51453*x^8 - 71891*x^9 + 27785*x^10 - 255*x^11 + 98*x^12 - 352*x^13) / (1 - x)^13 + O(x^60))) \\ Colin Barker, May 13 2017

a(n) = (n^12 - 18*n^11 + 3*n^10 + 1710*n^9 - 7175*n^8 - 60078*n^7 + 401649*n^6 + 884466*n^5 - 9521846*n^4 - 3238224*n^3 + 107453448*n^2 - 25651296*n - 483140880)/720 for n >= 7.

G.f.: x^6*(219 + 12313*x + 189789*x^2 + 679597*x^3 + 344288*x^4 - 808902*x^5 + 54074*x^6 + 289970*x^7 - 51453*x^8 - 71891*x^9 + 27785*x^10 - 255*x^11 + 98*x^12 - 352*x^13) / (1 - x)^13. - Colin Barker, May 13 2017

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.

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

Original entry on oeis.org

0, 0, 0, 0, 27, 21792, 3324193, 119138166, 1979541332, 20142680752, 145977165234, 824771174978, 3850985758339, 15461577137802, 54912339921707, 176153338628674, 518569625849418, 1418340918023792, 3639736652346172, 8833161922947702, 20405252721413369

Offset: 1

Vaclav Kotesovec, Nov 30 2011

nonn

V. Kotesovec, Non-attacking chess pieces

Cf. A061995, A061996, A061997, A061998, A172158, A193580, A194788.

Explicit formula (Vaclav Kotesovec, after values computed by Andrew Woods, Nov 30 2011): (n^16 - 252*n^14 + 336*n^13 + 27762*n^12 - 70896*n^11 - 1699656*n^10 + 6330240*n^9 + 60677169*n^8 - 304864560*n^7 - 1181816748*n^6 + 8314366704*n^5 + 8495481308*n^4 - 121101870624*n^3 + 74007948336*n^2 + 730891869120*n - 1180990460160)/40320, n>=7.

G.f.: -x^5*(14882*x^18 - 180784*x^17 + 1061244*x^16 - 4500406*x^15 + 15038864*x^14 - 34328850*x^13 + 40903004*x^12 - 8667835*x^11 + 23857551*x^10 - 260744627*x^9 + 545801251*x^8 - 276255996*x^7 - 467674682*x^6 + 484515328*x^5 + 391528458*x^4 + 65572237*x^3 + 2957401*x^2 + 21333*x + 27)/(x-1)^17.

A172205 Number of ways to place 6 nonattacking kings on a 6 X n board.

Original entry on oeis.org

0, 0, 16, 408, 8544, 62266, 291908, 1021254, 2916232, 7179314, 15790572, 31795390, 59638832, 105546666, 177953044, 287974838, 449932632, 681918370, 1006409660, 1450930734, 2048760064, 2839684634, 3870800868, 5197362214, 6883673384

Offset: 1

Vaclav Kotesovec, Jan 29 2010

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

Cf. A172158, A061992, A172202, A172203, A172204.

CoefficientList[Series[-2 x^2 (475 x^8 - 1015 x^7 + 4398 x^6 + 194 x^5 + 10875 x^4 + 5233 x^3 + 3012 x^2 + 148 x + 8) / (x - 1)^7, {x, 0, 50}], x] (* Vincenzo Librandi, May 27 2013 *)

a(n) = 2*(162n^6-3240n^5+29160n^4-151830n^3+483798n^2-895085n+749335)/5, n>=5.

G.f.: -2*x^3*(475*x^8-1015*x^7+4398*x^6+194*x^5+10875*x^4+5233*x^3+3012*x^2 +148*x+8)/(x-1)^7. - Vaclav Kotesovec, Mar 24 2010

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

Original entry on oeis.org

0, 0, 0, 0, 1, 3600, 2882737, 229095676, 6655170642, 103395053720, 1051588999820, 7878155295948, 46838274976147, 232322652402464, 995789500001315, 3784235129731708, 12999197522073908, 40969826999523768, 119876498636101786, 328726265508168780, 851369417500529061

Offset: 1

Vaclav Kotesovec, Dec 04 2011

nonn

V. Kotesovec, Non-attacking chess pieces

Cf. A061995, A061996, A061997, A061998, A172158, A193580, A194788, A201369.

Explicit formula (Vaclav Kotesovec, after values computed by Andrew Woods, Dec 04 2011): n^18/362880 - n^16/1120 + n^15/840 + 1559*n^14/12096 - 119*n^13/360 - 7681*n^12/720 + 479*n^11/12 + 9383677*n^10/17280 - 195031*n^9/72 - 24176483*n^8/1440 + 4447749*n^7/40 + 5032857271*n^6/18144 - 495178813*n^5/180 - 2551293629*n^4/2520 + 1588223225*n^3/42 - 11469403819*n^2/315 - 664490248*n/3 + 405670140, n>=8.

G.f.: x^5*(54764*x^21 - 805588*x^20 + 6061268*x^19 - 31485512*x^18 + 117971558*x^17 - 312791986*x^16 + 620038858*x^15 - 1193322246*x^14 + 2685590901*x^13 - 4918483903*x^12 + 3824558880*x^11 + 5110355848*x^10 - 13987162841*x^9 + 5213745395*x^8 + 15789867458*x^7 - 14255103822*x^6 - 13342741937*x^5 - 2791816301*x^4 - 174938304*x^3 - 2814508*x^2 - 3581*x - 1)/(x-1)^19.

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

A201513 Number of ways to place n nonattacking kings on an n X n board.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

A279115 Number of non-equivalent ways to place 6 non-attacking kings on an n X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A286441 Number of ways to tile an n X n X n triangular area with six 2 X 2 X 2 triangular tiles and an appropriate number (= n^2-24) of 1 X 1 X 1 tiles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

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

Views

Author

Keywords

Links

Crossrefs

Formula