A368831 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the n X n rook graph (n >= 1, 0 <= k <= n^2).

1, 0, 1, 0, 0, 6, 4, 1, 0, 0, 0, 48, 117, 126, 84, 36, 9, 1, 0, 0, 0, 0, 488, 2640, 6712, 10864, 12726, 11424, 8008, 4368, 1820, 560, 120, 16, 1, 0, 0, 0, 0, 0, 6130, 58300, 269500, 808325, 1778875, 3075160, 4349400, 5154900, 5186300, 4454400, 3268360, 2042950, 1081575, 480700, 177100, 53130, 12650, 2300, 300, 25, 1

Offset

0,6

Comments

The entries in row n are the coefficients of the domination polynomial of the n X n rook graph.

Sum of entries in row n = A287065 = main diagonal of A287274.

Number of minimum dominating sets T(n,n) = A248744(n)

References

John J. Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2004, chapter 7.

Links

Table of n, a(n) for n=0..60.

Stephan Mertens, Domination Polynomial of the Rook Graph, Journal of Integer Sequences 27 (2024), Article 24.3.7; arXiv:2401.00716 [math.CO], 2024.

Eric Weisstein's World of Mathematics, Dominating Set.

Eric Weisstein's World of Mathematics, Rook Graph.

Formula

G.f.: ((x+1)^n - 1)^m - (-1)^m + Sum_{k=0..m-1} binomial(m,k)*(-1)^k*((1+x)^k - 1)^n (for the rectangular n X m rook graph).

T(n,n) = 2*n^n - n!.

Example

Triangle begins: (first 5 rows)
  1;
  0,1;
  0,0,6,4,1;
  0,0,0,48,117,126,84,36,9,1;
  0,0,0,0,488,2640,6712,10864,12726,11424,8008,4368,1820,560,120,16,1;
  ...

Mathematica

R[n_, m_] := CoefficientList[((x + 1)^n - 1)^m - (-1)^m*Sum[Binomial[m, k]*(-1)^k*((1 + x)^k - 1)^n, {k, 0, m - 1}], x];
Flatten[Table[R[n, n], {n, 1, 5}]

Crossrefs

Cf. A287065 (row sums), A287274, A248744 (leading diagonal).

Sequence in context: A365956 A365953 A365955 * A158567 A215832 A021160

Adjacent sequences: A368828 A368829 A368830 * A368832 A368833 A368834

Keyword

nonn,tabf

Author

Stephan Mertens, Jan 07 2024

Status

approved