A248744 -id:A248744 - cp's OEIS frontend

A290632 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the rook graph K_m X K_n.

1, 2, 2, 3, 6, 3, 4, 11, 11, 4, 5, 18, 48, 18, 5, 6, 27, 109, 109, 27, 6, 7, 38, 218, 488, 218, 38, 7, 8, 51, 405, 1409, 1409, 405, 51, 8, 9, 66, 724, 3832, 6130, 3832, 724, 66, 9, 10, 83, 1277, 10385, 21601, 21601, 10385, 1277, 83, 10

Offset: 1

Andrew Howroyd, Aug 07 2017

			Array begins:
========================================================
m\n| 1  2    3     4      5       6       7        8
---|----------------------------------------------------
1  | 1  2    3     4      5       6       7        8 ...
2  | 2  6   11    18     27      38      51       66 ...
3  | 3 11   48   109    218     405     724     1277 ...
4  | 4 18  109   488   1409    3832   10385    28808 ...
5  | 5 27  218  1409   6130   21601   78132   297393 ...
6  | 6 38  405  3832  21601   92592  382465  1750240 ...
7  | 7 51  724 10385  78132  382465 1642046  7720833 ...
8  | 8 66 1277 28808 297393 1750240 7720833 33514112 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A248744.

Cf. A287274.

T[m_, n_] := m^n + n^m - Min[m, n]! StirlingS2[Max[m, n], Min[m, n]] (* Eric W. Weisstein, Aug 10 2017 *)

T(m,n) = m^n + n^m - if(n<=m, n!*stirling(m,n,2), m!*stirling(n,m,2));

T(m, n) = T(n, m).

T(n, k) = k^n + n^k - k! * stirling2(n,k) for k<=n.

A290586 Number of irredundant sets in the n X n rook graph.

Original entry on oeis.org

2, 11, 94, 1185, 20106, 453271, 13169346, 476777153, 20869990066, 1076251513071, 64077661097418, 4337014196039377, 329768528011095642, 27905789218764082151, 2608140451597365915346, 267506385903592339178241, 29943760423790270319833826

Offset: 1

Eric W. Weisstein, Aug 07 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Andrew Howroyd, Irredundant Sets in Rook Graphs
Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A290818.
Row sums of A290823.
Cf. A008299, A248744.

s[n_, k_]:=Sum[(-1)^i*Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}];
c[m_, n_, x_]:=Sum[Binomial[m, i] (n^i - n!*StirlingS2[i, n])*x^i, {i, 0, m - 1}];
p[m_, n_, x_]:=Sum[Sum[Binomial[m, k] Binomial[n, r]* k!*s[r, k]*x^r*c[m - k, n - r, x], {r, 2k, n - 1}], {k,0, m - 1}];
Table[2*n^n - n! + p[n, n, 1], {n, 30}]
(* Indranil Ghosh, Aug 12 2017, after PARI code *)

\\ here s(n,k) is A008299, 2*n^n - n! is A248744.
s(n,k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
c(m,n,x)=sum(i=0, m-1, binomial(m, i) * (n^i - n!*stirling(i, n, 2))*x^i);
p(m,n,x)={sum(k=0, m-1, sum(r=2*k, n-1, binomial(m,k) * binomial(n,r) * k! * s(r,k) * x^r * c(m-k,n-r,x) ))}
a(n) = 2*n^n - n! + p(n,n,1); \\ Andrew Howroyd, Aug 11 2017

a(n) = 2*n^n - n! + Sum_{k=0..n-1} Sum_{r=2*k..n-1} binomial(n,k) * binomial(n,r) * k! * A008299(r,k) * c(n-k,n-r) where c(m,n) = Sum_{i=0..m-1} binomial(n,i) * (n^i - n!*stirling2(i, n)). - Andrew Howroyd, Aug 11 2017

a(4) corrected and a(5) from Andrew Howroyd, Aug 07 2017

Terms a(6) and beyond from Andrew Howroyd, Aug 11 2017

A303211 Number of minimum total dominating sets in the n X n rook graph.

Original entry on oeis.org

0, 4, 6, 80, 410, 5112, 48818, 695424, 9589266, 162327800, 2869193162, 57451559904, 1225220612954, 28560612445848, 709917843398850, 18943086191785472, 536695850359985186, 16151064034012994808, 513345798896635886906, 17206881800061632191200

Offset: 1

Eric W. Weisstein, Apr 19 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal of A384117.

Cf. A248744, A303208, A347921.

Table[(-1)^n n! + Sum[(-1)^k Binomial[n, k]^2 k! (2 (n - k)^(n - k) - (n - k)!), {k, 0, n - 1}], {n, 20}]
2 Table[(-1)^n n! + Sum[(-1)^k Binomial[n, k]^2 k! (n - k)^(n - k), {k, 0, n - 1}], {n, 20}] (* Eric W. Weisstein, Jan 18 2019 *)

a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)^2*k!*(2*(n-k)^(n-k) - (n-k)!))} \\ Andrew Howroyd, Apr 20 2018

a(n) = Sum_{k=0,..n} (-1)^k*binomial(n,k)^2*k!*(2*(n-k)^(n-k) - (n-k)!). - Andrew Howroyd, Apr 20 2018

a(n) ~ 2 * (exp(1) - 1)^(n + 1/2) * n^n / exp(n + 1/2). - Vaclav Kotesovec, Apr 20 2018

Terms a(6) and beyond from Andrew Howroyd, Apr 20 2018

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 >= 0, 0 <= k <= n^2).

Original entry on oeis.org

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

Stephan Mertens, Jan 07 2024

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

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

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

Alois P. Heinz, Rows n = 0..32, flattened
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.

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

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}]]

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

A291104 Number of maximal irredundant sets in the n X n rook graph.

Original entry on oeis.org

1, 6, 48, 632, 10130, 194292, 4730810, 145114944, 5529662802, 256094790500, 14038667879522, 890349688082736, 64160617557387338, 5183023418382933060, 464623151635449639450, 45857185726197195813632, 4951604249874284663582498, 581839639424819461006405956

Offset: 1

Eric W. Weisstein, Aug 17 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A291543.

Cf. A008299, A248744, A290586.

(* Start *)
s[n_, k_] := Sum[(-1)^i Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}]
p[m_, n_, x_] := Sum[Binomial[m, k] Binomial[n, j] k! s[n - j, k - 1] j! StirlingS2[m - k, j - 1] x^(m + n - j - k), {k, 2, m - 2}, {j, 2, m - k}]
a[n_] := 2 n^n - n! + p[n, n, 1]
Array[a, 20]
(* End *)

\\ here s(n, k) is A008299, 2*n^n - n! is A248744.
s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
p(m, n, x)={sum(k=2, m-2, sum(j=2, m-k, binomial(m, k) * binomial(n, j) * k! * s(n-j, k-1) * j! * stirling(m-k, j-1, 2) * x^(m+n-j-k) ))}
a(n) = 2*n^n - n! + p(n,n,1); \\ Andrew Howroyd, Aug 25 2017

a(n) = 2*n^n - n! + Sum_{k=2..n-2} Sum_{j=2..n-k} binomial(n,k) * binomial(n,j) * k! * A008299(n-j,k-1) * j! * stirling2(n-k,j-1). - Andrew Howroyd, Aug 25 2017

Terms a(5) and beyond from Andrew Howroyd, Aug 25 2017

A384119 Array read by antidiagonals: T(n,m) is the number of minimum dominating sets in the n X m rook graph K_n X K_m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 3, 1, 1, 4, 9, 9, 4, 1, 1, 5, 16, 48, 16, 5, 1, 1, 6, 25, 64, 64, 25, 6, 1, 1, 7, 36, 125, 488, 125, 36, 7, 1, 1, 8, 49, 216, 625, 625, 216, 49, 8, 1, 1, 9, 64, 343, 1296, 6130, 1296, 343, 64, 9, 1, 1, 10, 81, 512, 2401, 7776, 7776, 2401, 512, 81, 10, 1

Offset: 0

Andrew Howroyd, May 20 2025

For m <= n, the minimum size of a dominating set is m. When m < n, solutions have exactly one vertex in each column. In the special case of n = m, solutions either have exactly one vertex in each column or have exactly one vertex in each row.

			Array begins:
=======================================================
n\m | 0 1  2   3    4     5      6       7        8 ...
----+--------------------------------------------------
  0 | 1 1  1   1    1     1      1       1        1 ...
  1 | 1 1  2   3    4     5      6       7        8 ...
  2 | 1 2  6   9   16    25     36      49       64 ...
  3 | 1 3  9  48   64   125    216     343      512 ...
  4 | 1 4 16  64  488   625   1296    2401     4096 ...
  5 | 1 5 25 125  625  6130   7776   16807    32768 ...
  6 | 1 6 36 216 1296  7776  92592  117649   262144 ...
  7 | 1 7 49 343 2401 16807 117649 1642046  2097152 ...
  8 | 1 8 64 512 4096 32768 262144 2097152 33514112 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Eric Weisstein's World of Mathematics, Minimum Dominating Set.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A248744.

Cf. A079901, A287274, A290632.

T(n,m) = {if(n<=m, m^n) + if(m<=n, n^m) - if(m==n, n!)}

T(n,m) = T(m,n).

T(n,m) = n^m for m < n.

cp's OEIS Frontend

A290632 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290586 Number of irredundant sets in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A303211 Number of minimum total dominating sets in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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 >= 0, 0 <= k <= n^2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A291104 Number of maximal irredundant sets in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A384119 Array read by antidiagonals: T(n,m) is the number of minimum dominating sets in the n X m rook graph K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula