A201513 -id:A201513 - cp's OEIS frontend

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

1, 1, 2, 5, 35, 314, 6427, 202841, 12727570, 1355115601, 269718819131, 94707789944544, 60711713670028729, 69645620389200894313, 144633664064386054815370, 540156683236043677756331721, 3641548665525780178990584908643, 44222017282082621251230960522832336

Offset: 0

Reiner Martin, Jul 23 2001

a(n) is also the number of ways to populate an n-1 X n-1 chessboard with nonattacking kings (including the case of zero kings). Cf. A193580. - Andrew Woods, Aug 27 2011

Also the number of vertex covers and independent vertex sets of the n-1 X n-1 king graph.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 343

Andrew Woods and Vaclav Kotesovec and Johan Nilsson, Table of n, a(n) for n = 0..40 (terms 0..21 from Andrew Woods, terms 22..24 from Vaclav Kotesovec and terms 25..40 from Johan Nilsson)
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 68-69.
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.
J. 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, Independent Vertex Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A001045, A006506, A054854, A054855, A063650-A063653, A067966, etc.
Cf. A045846, A211348, A247413, A201513.
Cf. A212269, A067958.
a(n) = row sum n-1 of A193580.
Main diagonal of A245013.

Needs["LinearAlgebra`MatrixManipulation`"] Remove[mat] step[sa[rules1_, {dim1_, dim1_}], sa[rules2_, {dim2_, dim2_}]] := sa[Join[rules2, rules1 /. {x_Integer, y_Integer} -> {x + dim2, y}, rules1 /. {x_Integer, y_Integer} -> {x, y + dim2}], {dim1 + dim2, dim1 + dim2}] mat[0] = sa[{{1, 1} -> 1}, {1, 1}]; mat[1] = sa[{{1, 1} -> 1, {1, 2} -> 1, {2, 1} -> 1}, {2, 2}]; mat[n_] := mat[n] = step[mat[n - 2], mat[n - 1]]; A[n_] := mat[n] /. sa -> SparseArray; F[n_] := MatrixPower[A[n], n + 1][[1, 1]]; (* Mark McClure (mcmcclur(AT)bulldog.unca.edu), Mar 19 2006 *)
$RecursionLimit = 1000; Clear[a, b]; b[n_, l_List] := b[n, l] = Module[{m=Min[l], k}, If[m>0, b[n-m, l-m], If[n == 0, 1, k=Position[l, 0, 1, 1][[1, 1]]; b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 2}]], 0]]]]; a[n_] := a[n] = If[n<2, 1, b[n, Table[0, {n}]]]; Table[Print[a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 11 2014, after Alois P. Heinz *)

Lim_{n -> infinity} (a(n))^(1/n^2) = A247413 = 1.342643951124... . - Brendan McKay, 1996

4 more terms from R. H. Hardin, Jan 23 2002
2 more terms from Keith Schneider (kschneid(AT)bulldog.unca.edu), Mar 19 2006
5 more terms from Andrew Woods, Aug 27 2011
a(22)-a(24) in b-file from Vaclav Kotesovec, May 01 2012
a(0) inserted by Alois P. Heinz, Sep 17 2014
a(25)-a(40) in b-file from Johan Nilsson, Mar 10 2016

A137774 Number of ways to place n nonattacking empresses on an n X n board.

Original entry on oeis.org

1, 2, 2, 8, 20, 94, 438, 2766, 19480, 163058, 1546726, 16598282, 197708058, 2586423174, 36769177348, 563504645310, 9248221393974, 161670971937362, 2996936692836754, 58689061747521430, 1210222434323163704, 26204614054454840842, 594313769819021397534, 14086979362268860896282

Offset: 1

Vaclav Kotesovec, Jan 27 2011

An empress moves like a rook and a knight.

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Separators - a new statistic for permutations, arXiv:1905.12364 [math.CO], 2019.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, On the Sparseness of the Downsets of Permutations via Their Number of Separators, Enumerative Combinatorics and Applications (2021) Vol. 1, No. 3, Article #S2R21.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.685 and 636.
W. Schubert, N-Queens page

Cf. A201513, A000170, A002465, A201540.
Cf. A185085, A051223, A244284, A201511, A201861, A137774, A245011.
Cf. A218244, A002464, A110128, A117574, A089222, A002493.

Asymptotics (Vaclav Kotesovec, Jan 26 2011): a(n)/n! -> 1/e^4.
General asymptotic formulas for number of ways to place n nonattacking pieces rook + leaper[r,s] on an n X n board:
a(n)/n! -> 1/e^2 for 0a(n)/n! -> 1/e^4 for 0

Terms a(16)-a(17) from Vaclav Kotesovec, Feb 06 2011
Terms a(18)-a(19) from Wolfram Schubert, Jul 24 2011
Terms a(20)-a(24) (computed by Wolfram Schubert), Vaclav Kotesovec, Aug 25 2012

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

Original entry on oeis.org

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.

A098487 Triangle T(m,k) read by rows, where T(m,k) is the number of ways in which 1<=k<=m positions can be picked in an m X m square array such that all positions are mutually isolated. Two positions (s,t),(u,v) are considered as isolated from each other if min(abs(s-u),abs(t-v))>1.

Original entry on oeis.org

1, 4, 0, 9, 16, 8, 16, 78, 140, 79, 25, 228, 964, 1987, 1974, 36, 520, 3920, 16834, 42368, 62266, 49, 1020, 11860, 85275, 397014, 1220298, 2484382, 64, 1806, 29708, 317471, 2326320, 12033330, 44601420, 119138166, 81, 2968, 65240, 962089, 10087628, 77784658, 450193818, 1979541332, 6655170642

Offset: 1

Hugo Pfoertner, Sep 15 2004

For more information, links, programs see A098485.

			T(3,3) = a(6) = 8 because there are the following 8 ways to pick 3 positions isolated from each other from a 3 X 3 square array:
X0X...X0X...X0X...X00...X00...0X0...00X...00X
000...000...000...00X...000...000...X00...000
X00...0X0...00X...X00...X0X...X0X...00X...X0X
Triangle begins:
:  1;
:  4,    0;
:  9,   16,     8;
: 16,   78,   140,     79;
: 25,  228,   964,   1987,    1974;
: 36,  520,  3920,  16834,   42368,    62266;
: 49, 1020, 11860,  85275,  397014,  1220298,  2484382;
: 64, 1806, 29708, 317471, 2326320, 12033330, 44601420, 119138166;

Alois P. Heinz, Rows n = 1..21, flattened

A098485 gives selections where all marks are connected, A090642 gives total number of possible selections.
Main diagonal gives A201513.
Cf. A291716, A291717, A291718, A292152, A292153, A292154, A292155, A292156.

Fortran
```
! See link in A098485.
```

T(8,8) corrected by Alois P. Heinz, May 11 2017

A201540 Number of ways to place n nonattacking knights on an n X n board.

Original entry on oeis.org

1, 6, 36, 412, 9386, 257318, 8891854, 379978716, 19206532478, 1120204619108, 74113608972922, 5483225594409823, 448414229054798028, 40154319792412218900, 3906519894750904583838

Offset: 1

Vaclav Kotesovec, Dec 02 2011

a(n) = A244081(n,n). - Alois P. Heinz, Jun 19 2014

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 293.

Cf. A172132, A172134, A172135, A172136, A178499, A244081.

Cf. A244284, A201511, A201861, A201513, A141243.

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True&, d]]], True, For[k = 1, ! l[[k]], k++]; g = ReplacePart[l, k -> f];
     If[k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If[k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If[k > 2, g = ReplacePart[g, d - 2 + k -> f]];
     If[k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True&, n*3]]];
a[n_] := T[n][[n + 1]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

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

a(11) from Alois P. Heinz, Jun 19 2014
a(12)-a(13) from Vaclav Kotesovec, Jun 21 2014
a(14) from Vaclav Kotesovec, Aug 26 2016
a(15) from Vaclav Kotesovec, May 26 2021

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

Original entry on oeis.org

1, 0, 2, 14, 273, 7855, 311552, 14895797, 831959075, 52959962415

Offset: 1

Heinrich Ludwig, Dec 10 2016

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

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

Cf. A201513, A279111 (2 kings), A279112 (3 kings), A279113 (4 kings), A279114 (5 kings), A279115 (6 kings), A279116 (7 kings), A236679.

A244284 Number of ways to place n nonattacking zebras on an n X n chessboard.

Original entry on oeis.org

1, 6, 84, 1168, 20502, 525796, 18939708, 802444170, 38934305898, 2170312156170

Offset: 1

Vaclav Kotesovec, Jun 25 2014

Zebra is a (fairy chess) leaper [2,3].

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.363
Wikipedia, Fairy chess piece

Cf. A172137, A172138, A172139, A172140.

Cf. A201540, A201511, A201861, A201513.

a(n) ~ n^(2*n)/n! * exp(-9/2).

A182563 Number of ways to place n non-attacking semi-knights on an n x n chessboard.

Original entry on oeis.org

1, 6, 70, 1289, 33864, 1148760, 47700972, 2344465830, 133055587660, 8559364525414, 615266768106190, 48861588247978827, 4247584874013608724, 401107335066453376830, 40880928693752664368224, 4472281486633326131737868

Offset: 1

Vaclav Kotesovec, May 05 2012

Semi-knight is a semi-leaper [1,2]. Moves of a semi-knight are allowed only in [2,1] and [-2,-1]. See also semi-bishops (A187235).

V. Kotesovec, Non-attacking chess pieces, 6ed, p.289

Cf. A182562, A201540, A201513, A002465, A201511, A197989, A201861.

Asymptotic: a(n) ~ n^(2n)/n!*exp(-3/2).

a(16) from Vaclav Kotesovec, May 24 2021

A244288 Number of binary arrangements of total n 1's, without adjacent 1's on n X n array connected nw-se.

Original entry on oeis.org

1, 1, 5, 57, 1084, 29003, 999717, 42125233, 2096106904, 120194547233, 7799803041491, 564856080384900, 45146219773912540, 3946445378386791157, 374482268128153003615, 38330653031858936914329, 4209191997519328986666624, 493575737047609363968826907

Offset: 0

Vaclav Kotesovec, Jun 25 2014

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.422

Cf. A197989, A201540, A201511, A201861, A201513, A244284.

P(m,n) = sum(k=0, (m+1)\2, binomial(m-k+1,k)*x^k, O(x*x^n))
a(n) = polcoef(P(n,n)*prod(m=1, n-1, P(m,n))^2, n) \\ Andrew Howroyd, Mar 27 2023

a(n) ~ n^(2*n)/n! * exp(-3/2).

a(16) from Vaclav Kotesovec, Sep 04 2016
a(17) from Vaclav Kotesovec, Jun 15 2021
a(0)=1 prepended by Andrew Howroyd, Mar 27 2023

A245011 Number of ways to place n nonattacking princesses on an n X n board.

Original entry on oeis.org

1, 4, 6, 86, 854, 9556, 146168, 2660326, 56083228, 1349544632, 36786865968, 1117327217782

Offset: 1

Vaclav Kotesovec, Sep 16 2014

A princess moves like a bishop and a knight.

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 744.
Wikipedia, Fairy chess piece

Cf. A201513, A000170, A002465, A201540.
Cf. A185085, A051223, A244284, A201511, A201861, A137774.
Cf. A225555.

Showing 1-10 of 10 results.

cp's OEIS Frontend

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A137774 Number of ways to place n nonattacking empresses on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

A098487 Triangle T(m,k) read by rows, where T(m,k) is the number of ways in which 1<=k<=m positions can be picked in an m X m square array such that all positions are mutually isolated. Two positions (s,t),(u,v) are considered as isolated from each other if min(abs(s-u),abs(t-v))>1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

Extensions

A201540 Number of ways to place n nonattacking knights on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

A244284 Number of ways to place n nonattacking zebras on an n X n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A182563 Number of ways to place n non-attacking semi-knights on an n x n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A244288 Number of binary arrangements of total n 1's, without adjacent 1's on n X n array connected nw-se.

Views