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

A098485 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 their adjacency graph consists of a single component. Two positions (s,t), (u,v) are considered as adjacent if max(abs(s-u), abs(t-v)) <= 1.

Original entry on oeis.org

1, 4, 6, 9, 20, 48, 16, 42, 132, 419, 25, 72, 256, 973, 3682, 36, 110, 420, 1747, 7484, 31992, 49, 156, 624, 2741, 12562, 58620, 273556, 64, 210, 868, 3955, 18916, 92912, 462104, 2927505, 81, 272, 1152, 5389, 26546, 134868, 697836, 3644935, 19082018

Offset: 1

Hugo Pfoertner, Sep 14 2004

Number of ways to mark the numbers on a square board on a lottery play slip such that one connected graphic pattern is formed. For the lottery "mark 6 numbers of 49 on a 7 X 7 grid of numbers" that is played in many countries, there are T(7,6)=58620 (out of binomial(49,6)=13983816) different combinations of 6 numbers whose graphic pattern on the board forms one connected component.

			a(5)=T(3,2)=20 because there are 20 ways to mark two positions in a 3 X 3 square grid such that the two picked positions are either row-wise, column-wise or diagonally adjacent:
XX0...X00...X00...0XX...0X0...0X0...0X0...00X...00X...000
000...X00...0X0...000...X00...0X0...00X...0X0...00X...XX0
000...000...000...000...000...000...000...000...000...000
.........................................................
000...000...000...000...000...000...000...000...000...000
000...X00...0X0...000...X00...0X0...00X...0X0...00X...0XX
XX0...X00...X00...0XX...0X0...0X0...0X0...00X...00X...000

John Burkardt, GRAFPACK Graph Computations.
Hugo Pfoertner, Counts of connected components in selected numbers on square lotto boards.
Hugo Pfoertner, Program to analyze the adjacency graph of selections on lotto boards.

Cf. A090642, A098487 (selections where all marks are isolated from each other), A291716, A291717, A291718, A292152, A292153, A292154, A292155, A292156.

Fortran
```
c See link.
```

A291717 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 grid such that the picked positions have a central symmetry.

Original entry on oeis.org

1, 4, 6, 9, 36, 8, 16, 120, 24, 168, 25, 300, 72, 714, 178, 36, 630, 144, 2273, 464, 6576, 49, 1176, 288, 5932, 1476, 24288, 6404, 64, 2016, 480, 13536, 3040, 74560, 15680, 341320, 81, 3240, 800, 27860, 6940, 197600, 50860, 1170466, 314862

Offset: 1

Hugo Pfoertner, Sep 08 2017

			A configuration of 6 picked points from a 7 X 7 grid with a central (point) symmetry w.r.t. point #, but no line (mirror) symmetry and thus only contributing to T(7,6)=a(27), but not to A291718(27), would be:
  o o o X o o o
  o o o o o o o
  o o o o X o o
  o X # X o o o
  X o o o o o o
  o o o o o o o
  o X o o o o o
.
Triangle begins:
   1;
   4,    6;
   9,   36,   8;
  16,  120,  24,   168;
  25,  300,  72,   714,  178;
  36,  630, 144,  2273,  464,  6576;
  49, 1176, 288,  5932, 1476, 24288,  6404;
  64, 2016, 480, 13536, 3040, 74560, 15680, 341320;

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Cf. A090642, A098485, A098487, A291716, A291718, A292152, A292153, A292154, A292155, A292156.

decentralize[v_] := 2*Total[v] - Last[v];
T[n_, k_] := decentralize[ Table[ decentralize[ Table[ If[EvenQ[k] || OddQ[a*b], Binomial[ Quotient[a*b, 2], Quotient[k, 2]], 0], {b, 1, n}]], {a, 1, n}]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

decentralize(v) = 2*vecsum(v) - v[length(v)];
T(n,k) = decentralize(vector(n, a, decentralize(vector(n, b, if(k%2==0||a*b%2==1, binomial(a*b\2, k\2))))));
for(n=1,10, for(k=1,n, print1(T(n,k), ", ")); print); \\ Andrew Howroyd, Sep 16 2017

Terms a(37) and beyond from Andrew Howroyd, Sep 16 2017

A291716 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 grid such that the center of gravity of the k picked positions coincides with one of the picked positions.

Original entry on oeis.org

1, 4, 0, 9, 0, 8, 16, 0, 24, 44, 25, 0, 72, 176, 610, 36, 0, 144, 660, 2996, 12092, 49, 0, 288, 1788, 11492, 64648, 323940, 64, 0, 480, 4116, 35676, 269924, 1811696, 10866196

Offset: 1

Hugo Pfoertner, Sep 08 2017

			T(3,3) = a(6) = 8 because there are the following 8 ways to pick 3 positions such that one of them is the center of gravity of the other two.
  XXX...ooo...ooo...Xoo...oXo...ooX...Xoo...ooX
  ooo...XXX...ooo...Xoo...oXo...ooX...oXo...oXo
  ooo...ooo...XXX...Xoo...oXo...ooX...ooX...Xoo
.
An example of one of the T(4,4)=a(10)=44 "balanced" configurations is
  x.o.o.x
  o.o.X.o
  o.o.o.o
  o.o.o.x
X is at the center of gravity of the 3 other picked positions x.
.
Triangle begins:
   1;
   4, 0;
   9, 0,   8;
  16, 0,  24,   44;
  25, 0,  72,  176,   610;
  36, 0, 144,  660,  2996,  12092;
  49, 0, 288, 1788, 11492,  64648,  323940;
  64, 0, 480, 4116, 35676, 269924, 1811696, 10866196;

Cf. A090642, A098485, A098487, A291717, A291718, A292152, A292153, A292154, A292155, A292156.

A291718 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 grid such that the picked positions have a line symmetry.

Original entry on oeis.org

1, 4, 6, 8, 36, 44, 16, 120, 192, 276, 25, 300, 596, 1130, 2010, 36, 630, 1436, 3321, 6880, 16400, 49, 1176, 3024, 8272, 20600, 57564, 120940, 64, 2016, 5568, 17528, 49184, 159784, 380344, 1075344

Offset: 1

Hugo Pfoertner, Sep 08 2017

			A configuration of 6 picked points from a 7 X 7 grid with a line (mirror) symmetry w.r.t. the line indicated by +++, and no point symmetry would be:
  o o o o o o o
  + X o X o o o
  X + o o o X o
  o o + o o o o
  X o o + o o o
  o o o o + o o
  o X o o o + o
So it would not contribute to the count of central symmetric configurations in A291717(27).
.
A configuration
  o o + o o o o
  o o + o o o o
  X o + o X o o
  + X # X + + +
  X o + o X o o
  o o + o o o o
  o o + o o o o
would contribute both to a(27) and to A291717(27), because besides being mirror symmetric w.r.t. the lines indicated by +++, it has also a central symmetry w.r.t the point indicated by #.
.
Triangle begins:
   1;
   4,    6;
   9,   36,   44;
  16,  120,  192,   276;
  25,  300,  596,  1130,  2010;
  36,  630, 1436,  3321,  6880,  16400;
  49, 1176, 3024,  8272, 20600,  57564, 120940;
  64, 2016, 5568, 17528, 49184, 159784, 380344, 1075344;

Cf. A090642, A098485, A098487, A291716, A291717, A292152, A292153, A292154, A292155, A292156.

A292152 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 grid such that the picked positions don't have any symmetry.

Original entry on oeis.org

0, 0, 0, 0, 0, 40, 0, 0, 368, 1432, 0, 0, 1704, 10992, 50992, 0, 0, 5704, 53784, 369776, 1925464, 0, 0, 15400, 198696, 1885128, 13903624, 85773968, 0, 0, 36096, 606264, 7572896, 74743584, 620821688, 4424756040

Offset: 1

Hugo Pfoertner, Sep 17 2017

			The triangle begins:
  0;
  0,  0;
  0,  0,    40;
  0,  0,   368,   1432;
  0,  0,  1704,  10992,  50992;
  0,  0,  5704,  53784,  369776,  1925464;
  0,  0, 15400, 198696, 1885128, 13903624, 85773968;
.
The following configuration of 6 picked points from a 7X7 grid is one of the T(7,6)=a(28)=13903624 configurations without symmetry. It is of some historical interest, because when it was drawn in Germany's "Lotto 6 aus 49", there was only one person with a winning bet receiving a payout of 22 million DM (Deutsche Mark).
.
  o o o o o o o
  o o o o o o o
  o o o o X o o
  o o X o o o o
  o o o o o o X
  X X X o o o o
  o o o o o o o

Walter Krämer, Denkste! Trugschlüsse aus der Welt der Zahlen und des Zufalls. Campus Verlag, Frankfurt/Main, 1996. Chapter 4, pp. 71-82.

Cf. A090642, A098485, A098487, A291716, A291717, A291718, A292153, A292154, A292155, A292156.

a(n) = A090642(n) - A292153(n).

A292153 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 grid such that the picked positions have a point symmetry or a line symmetry.

Original entry on oeis.org

1, 4, 6, 9, 36, 44, 16, 120, 192, 388, 25, 300, 596, 1658, 2138, 36, 630, 1436, 5121, 7216, 22328, 49, 1176, 3024, 13180, 21756, 80192, 126616, 64, 2016, 5568, 29112, 51616, 230784, 394504, 1409328

Offset: 1

Hugo Pfoertner, Sep 17 2017

The "or" is inclusive, i.e. configurations that have both types of symmetry simultaneously (counted separately in A292154) are included.

			The triangle begins:
   1;
   4,    6;
   9,   36,   44;
  16,  120,  192,   388;
  25,  300,  596,  1658,  2138;
  36,  630, 1436,  5121,  7216, 22328;
  49, 1176, 3024, 13180, 21756, 80192, 126616;
.
The following configuration is one of the T(4,3)=a(9)=192 symmetric configurations of 3 points picked from a 4 X 4 grid. It has both types of symmetry.
  0 0 0 0
  X 0 0 0
  0 X 0 0
  0 0 X 0

Cf. A090642, A098485, A098487, A291716, A291717, A291718, A292152, A292154, A292155, A292156.

a(n) = A090642(n) - A292152(n) = A292154(n) + A292155(n) + A292156(n).

A292154 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 grid such that the picked positions have both a point symmetry and a line symmetry.

Original entry on oeis.org

1, 4, 6, 9, 36, 8, 16, 120, 24, 56, 25, 300, 72, 186, 50, 36, 630, 144, 473, 128, 648, 49, 1176, 288, 1024, 320, 1660, 728, 64, 2016, 480, 1952, 608, 3560, 1520, 7326

Offset: 1

Hugo Pfoertner, Sep 17 2017

			The triangle begins:
   1;
   4,    6;
   9,   36,   8;
  16,  120,  24,   56;
  25,  300,  72,  186,  50;
  36,  630, 144,  473, 128,  648;
  49, 1176, 288, 1024, 320, 1660,  728;
  64, 2016, 480, 1952, 608, 3560, 1520, 7326;
.
  o o o o o o
  X o o X o o
  o o o o o o
  X o o X o o
  o o o o o o
  X o o X o o
is one of the T(6,6)=a(21)=648 configurations with both types of symmetry.
.
  o o X o o o
  o X o o o o
  o o o X o o
  o o o o o X
  o o o o X o
  o o o o o o
is one of the T(6,5)=a(20)=128 configurations with both types of symmetry.

Cf. A090642, A098485, A098487, A291716, A291717, A291718, A292152, A292153, A292155, A292156.

a(n) = A292153(n) - A292155(n) - A292156(n).
a(n) = A291717(n) - A292155(n).
a(n) = A291718(n) - A292156(n).

A292155 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 grid such that the picked positions have a point symmetry but no line symmetry.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 112, 0, 0, 0, 528, 128, 0, 0, 0, 1800, 336, 5928, 0, 0, 0, 4908, 1156, 22628, 5676, 0, 0, 0, 11584, 2432, 71000, 14160, 333994

Offset: 1

Hugo Pfoertner, Sep 17 2017

			The triangle begins:
   0;
   0, 0;
   0, 0, 0;
   0, 0, 0,   112;
   0, 0, 0,   528,  128;
   0, 0, 0,  1800,  336,  5928;
   0, 0, 0,  4908, 1156, 22628,  5676;
   0, 0, 0, 11584, 2432, 71000, 14160, 333994;
.
The following configuration of 6 picked points from a 7X7 grid with a point symmetry but no line (mirror) symmetry is one of the T(7,6)=a(28)=22628 configurations with this property. It is of some historical interest, because when it was drawn in Germany's "Lotto 6 aus 49" in January 1988, there were 222 persons instead of typically 5-10 with a winning bet. They only won 31000 DM (Deutsche Mark) instead of the 1 million DM they had hoped for.
.
  o o o o o o o
  o o o o o o o
  o o o o o o o
  o o X X X o o
  o X X X o o o
  o o o o o o o
  o o o o o o o
.
The shown configuration is also in A098485(28) (graph consisting of a single component).

Walter Krämer, Denkste! Trugschlüsse aus der Welt der Zahlen und des Zufalls. Campus Verlag, Frankfurt/Main, 1996.

Cf. A090642, A098485, A098487, A291716, A291717, A291718, A292152, A292153, A292154, A292156.

a(n) = A292153(n) - A291718(n) = A291717(n) - A292154(n).

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

A098485 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 their adjacency graph consists of a single component. Two positions (s,t), (u,v) are considered as adjacent if max(abs(s-u), abs(t-v)) <= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

A291717 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 grid such that the picked positions have a central symmetry.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A291716 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 grid such that the center of gravity of the k picked positions coincides with one of the picked positions.

Views

Author

Keywords

Examples

Crossrefs

A291718 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 grid such that the picked positions have a line symmetry.

Views

Author

Keywords

Examples

Crossrefs

A292152 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 grid such that the picked positions don't have any symmetry.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

A292153 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 grid such that the picked positions have a point symmetry or a line symmetry.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A292154 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 grid such that the picked positions have both a point symmetry and a line symmetry.

Views

Author

Keywords

Examples

Crossrefs

Formula

A292155 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 grid such that the picked positions have a point symmetry but no line symmetry.

Views

Author

Keywords

Examples