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

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.

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1601292, 314949564, 17143061738, 423677826986, 6210264633994, 62831788827614, 481992723228798, 2982908737810114, 15548436178142582, 70420082692285198, 283631426534134042, 1034163399690010346, 3461457325296584554, 10754832937513676198

Offset: 1

Vaclav Kotesovec, Dec 15 2012

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Non-attacking chess pieces

Cf. A061995 (2 kings), A061996 (3 kings), A061997 (4 kings).
Cf. A061998 (5 kings), A172158 (6 kings), A194788 (7 kings).
Cf. A201369 (8 kings), A201771 (9 kings).
Column k=10 of A193580.

Rest[CoefficientList[Series[-2*x^7*(97581*x^22 - 1758956*x^21 + 16320562*x^20 - 100734462*x^19 + 443795293*x^18 - 1471049082*x^17 + 3971393292*x^16 - 9304893422*x^15 + 17917931016*x^14 - 22612415810*x^13 + 6949925614*x^12 + 21430418050*x^11 + 9738010368*x^10 - 153051533038*x^9 + 256884162558*x^8 - 71451647970*x^7 - 265785285277*x^6 + 220345759446*x^5 + 251887022384*x^4 + 63841610284*x^3 + 5432696107*x^2 + 140661216*x + 800646)/(x-1)^21, {x, 0, 20}], x]]

a(n) = n^20/3628800 - n^18/8960 + n^17/6720 + 353*n^16/17280 - 53*n^15/1008 - 29467*n^14/13440 + 11867*n^13/1440 + 25901053*n^12/172800 - 107495*n^11/144 - 8467959*n^10/1280 + 122792641*n^9/2880 + 32499630031*n^8/181440 - 112903333*n^7/72 - 16042907329*n^6/6720 + 36445613711*n^5/1008 - 1784819159*n^4/300 - 9997453897*n^3/21 + 85979117831*n^2/140 + 13635070421*n/5 - 5609601346, for n>=9.

G.f.: -2*x^7*(97581*x^22 - 1758956*x^21 + 16320562*x^20 - 100734462*x^19 + 443795293*x^18 - 1471049082*x^17 + 3971393292*x^16 - 9304893422*x^15 + 17917931016*x^14 - 22612415810*x^13 + 6949925614*x^12 + 21430418050*x^11 + 9738010368*x^10 - 153051533038*x^9 + 256884162558*x^8 - 71451647970*x^7 - 265785285277*x^6 + 220345759446*x^5 + 251887022384*x^4 + 63841610284*x^3 + 5432696107*x^2 + 140661216*x + 800646)/(x-1)^21.

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula