A290632 -id:A290632 - cp's OEIS frontend

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

1, 3, 3, 7, 11, 7, 15, 51, 51, 15, 31, 227, 421, 227, 31, 63, 963, 3615, 3615, 963, 63, 127, 3971, 30517, 59747, 30517, 3971, 127, 255, 16131, 252231, 989295, 989295, 252231, 16131, 255, 511, 65027, 2054941, 16219187, 32260381, 16219187, 2054941, 65027, 511

Offset: 1

Andrew Howroyd, May 22 2017

A set of vertices can be represented as an m X n binary matrix. If all rows contain at least one 1 then regardless of what is in each row the set will form a dominating set giving (2^n-1)^m solutions. Otherwise if only iA183109(i,n) solutions.

			Array begins:
=============================================================================
m\n|   1     2       3         4           5             6               7
---|-------------------------------------------------------------------------
1  |   1     3       7        15          31            63             127...
2  |   3    11      51       227         963          3971           16131...
3  |   7    51     421      3615       30517        252231         2054941...
4  |  15   227    3615     59747      989295      16219187       263425695...
5  |  31   963   30517    989295    32260381    1048220463     33884452717...
6  |  63  3971  252231  16219187  1048220463   67680006971   4358402146791...
7  | 127 16131 2054941 263425695 33884452717 4358402146791 559876911043381...
...

Andrew Howroyd, Table of n, a(n) for n = 1..780
Stephan Mertens, Domination Polynomial of the Rook Graph, JIS 27 (2024) 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

Main diagonal is A287065.
Row 2 is A191341.
Cf. A183109, A088699 (independent vertex sets), A290632.

b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
a[m_, n_] := (2^n - 1)^m + Sum[ b[i, n]*Binomial[m, i], {i, 1, m - 1}];
Table[a[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 12 2017, adapted from PARI *)

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(m,n)=(2^n-1)^m + sum(i=1,m-1,b(i,n)*binomial(m,i));
for (i=1,7,for(j=1,7, print1(a(i,j), ",")); print);

T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).

A248744 Number of different ways one can attack all squares on an n X n chessboard with n rooks.

Original entry on oeis.org

1, 1, 6, 48, 488, 6130, 92592, 1642046, 33514112, 774478098, 19996371200, 570583424422, 17831721894912, 605743986163706, 22223926472824832, 875786473087350750, 36893467224629215232, 1654480168085245432354, 78692809748219369422848, 3956839189675526769415958

Offset: 0

Stephen Penrice, Apr 09 2017

nonn

Number of minimum (and minimal) dominating sets in the n X n rook graph. - Eric W. Weisstein, Jun 20 2017 and Aug 02 2017

A. M. Yaglom and I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. 1: Combinatorial Analysis and Probability Theory, Dover Publications, 1987, p. 77

Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A290632 and of A368831.

Cf. A000142, A000312.

A248744:=n->2*n^n-n!: seq(A248744(n), n=0..25); # Wesley Ivan Hurt, Nov 30 2017

Mathematica
```
Table[2 n^n - n!, {n, 20}]
```

a(n) = 2*n^n - n!.

A290818 Array read by antidiagonals: T(m,n) = number of irredundant sets in the lattice (rook) graph K_m X K_n.

Original entry on oeis.org

2, 3, 3, 4, 11, 4, 5, 24, 24, 5, 6, 47, 94, 47, 6, 7, 88, 272, 272, 88, 7, 8, 163, 774, 1185, 774, 163, 8, 9, 304, 2230, 4280, 4280, 2230, 304, 9, 10, 575, 6542, 15781, 20106, 15781, 6542, 575, 10, 11, 1104, 19452, 60604, 88512, 88512, 60604, 19452, 1104, 11

Offset: 1

Andrew Howroyd, Aug 11 2017

			Array begins:
===============================================================
m\n| 1   2     3      4       5        6        7         8
---+-----------------------------------------------------------
1  | 2   3     4      5       6        7        8         9 ...
2  | 3  11    24     47      88      163      304       575 ...
3  | 4  24    94    272     774     2230     6542     19452 ...
4  | 5  47   272   1185    4280    15781    60604    240073 ...
5  | 6  88   774   4280   20106    88512   400728   1879744 ...
6  | 7 163  2230  15781   88512   453271  2326534  12363513 ...
7  | 8 304  6542  60604  400728  2326534 13169346  76446456 ...
8  | 9 575 19452 240073 1879744 12363513 76446456 476777153 ...
...

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

Row 2 is A290707 for n > 1.
Main diagonal is A290586.
Cf. A287274, A290632.

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}];
b[m_, n_, x_]:=m^n*x^n + n^m*x^m - If[n<=m, n!*x^m*StirlingS2[m, n], m!*x^n*StirlingS2[n, m]];
T[m_, n_]:= b[m, n, 1] + p[m, n, 1];
Table[T[n, m -n + 1], {m, 10}, {n, m}]//Flatten
(* Indranil Ghosh, Aug 12 2017, after PARI code *)

\\ See A. Howroyd note in A290586 for explanation.
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) ))}
b(m,n,x) = m^n*x^n + n^m*x^m - if(n<=m, n!*x^m*stirling(m, n, 2), m!*x^n*stirling(n, m, 2));
T(m,n) = b(m,n,1) + p(m,n,1);
for(m=1,10,for(n=1,m,print1(T(n,m-n+1),", ")));

T(m,n) = A290632(m, n) + Sum_{k=0..m-1} Sum_{r=2*k..n-1} binomial(m,k) * binomial(n,r) * k! * A008299(r,k) * c(m-k,n-r) where c(m,n) = Sum_{i=0..m-1} binomial(n,i) * (n^i - n!*stirling2(i, n)).

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

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3, 4, 3, 1, 1, 6, 5, 5, 6, 1, 1, 10, 12, 51, 12, 10, 1, 1, 15, 37, 97, 97, 37, 15, 1, 1, 21, 98, 218, 368, 218, 98, 21, 1, 1, 28, 219, 519, 2229, 2229, 519, 219, 28, 1, 1, 36, 430, 1417, 6232, 7310, 6232, 1417, 430, 36, 1

Offset: 0

Andrew Howroyd, May 19 2025

			Array begins:
=====================================================
n\m | 0  1   2    3     4      5       6        7 ...
----+------------------------------------------------
  0 | 1  1   1    1     1      1       1        1 ...
  1 | 1  0   1    3     6     10      15       21 ...
  2 | 1  1   4    5    12     37      98      219 ...
  3 | 1  3   5   51    97    218     519     1417 ...
  4 | 1  6  12   97   368   2229    6232    16013 ...
  5 | 1 10  37  218  2229   7310   44491   172387 ...
  6 | 1 15  98  519  6232  44491  301572  1345693 ...
  7 | 1 21 219 1417 16013 172387 1345693 10893008 ...
  ...

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

Main diagonal is A347921.

Cf. A290632, A384116, A384117.

B(n,m)={ my(M=matrix(n+1,m+1)); for(n=1, n, M[n+1,1]=1; for(m=1, m, M[n+1,m+1] = if(n>2, binomial(n,2)*M[n-1,m]) + sum(i=2, m, binomial(m-1,i-1)*(n*M[n, m-i+1] + if(i>=3&&i<=n, binomial(n,i-1)*i!*M[n-i+2,m-i+1] ) )))); M}
A(n,m)={ my(M=B(m,n) + B(n,m)~); M[1,1]=1; for(i=1, m, for(j=1, n, if((i+j)%3==0 && j<=2*i && i<=2*j, my(t=(i+j)/3); M[i+1,j+1] += binomial(i,j-t)*binomial(j,i-t)*(2*(j-t))!*(2*(i-t))!/2^t ))); M}
{ my(T=A(8,8)); for(i=1, #T, print(T[i, ])) }

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

A291543 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the lattice (rook) graph K_m X K_n.

Original entry on oeis.org

1, 2, 2, 3, 6, 3, 4, 11, 11, 4, 5, 18, 48, 18, 5, 6, 27, 109, 109, 27, 6, 7, 38, 218, 632, 218, 38, 7, 8, 51, 405, 1649, 1649, 405, 51, 8, 9, 66, 724, 4192, 10130, 4192, 724, 66, 9, 10, 83, 1277, 10889, 34801, 34801, 10889, 1277, 83, 10

Offset: 1

Andrew Howroyd, Aug 25 2017

Maximal irredundant sets can be either dominating or not. The dominating maximal irredundant sets are the minimal dominating sets (A290632). The non-dominating maximal irredundant sets are those irredundant sets that have exactly one empty row and one empty column and at least one row and one column with more than one element. See note in A290586 for some additional details.

			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   632   1649    4192    10889     29480...
5  | 5 27  218  1649  10130   34801   116772    402673...
6  | 6 38  405  4192  34801  194292   856225   3804880...
7  | 7 51  724 10889 116772  856225  4730810  24810465...
8  | 8 66 1277 29480 402673 3804880 24810465 145114944...
...

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

Main diagonal is A291104.

Cf. A008299, A290586, A290632, A290818.

T32[n_, k_] := n^k + k^n - Min[n, k]!*StirlingS2[Max[n, k], Min[n, k]];
T99[n_, k_] := Sum[(-1)^i*Binomial[n, i]*Sum[(-1)^j*((k - i - j)^(n - i)/(j!*(k - i - j)!)), {j, 0, k - i}], {i, 0, k}];
T[m_, n_] /; n >= m := T32[m, n] + Sum[Sum[Binomial[m, k]*Binomial[n, j]*k!*T99[n - j, k - 1]*j!*StirlingS2[m - k, j - 1], {j, 2, m - k}], {k, 2, m - 2}]; T[m_, n_] /; n < m := T[n, m];
Table[T[m - n + 1, n], {m, 1, 10}, {n, 1, m}] // Flatten(* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

\\ here s(n,k) is A008299(n,k) and b(m,n,1) is A290632(m,n).
s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
b(m, n, x) = m^n*x^n + n^m*x^m - if(n<=m, n!*x^m*stirling(m, n, 2), m!*x^n*stirling(n, m, 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) ))}
T(m, n) = b(m, n, 1) + p(m, n, 1);

T(m,n) = A290632(m, n) + Sum_{k=2..m-2} Sum_{j=2..m-k} binomial(m,k) * binomial(n,j) * k! * A008299(n-j,k-1) * j! * stirling2(m-k,j-1).

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A248744 Number of different ways one can attack all squares on an n X n chessboard with n rooks.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290818 Array read by antidiagonals: T(m,n) = number of irredundant sets in the lattice (rook) graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A291543 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the lattice (rook) graph K_m X K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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