A287274 -id:A287274 - cp's OEIS frontend

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

1, 1, 1, 1, 5, 1, 1, 19, 19, 1, 1, 65, 205, 65, 1, 1, 211, 1795, 1795, 211, 1, 1, 665, 14221, 36317, 14221, 665, 1, 1, 2059, 106819, 636331, 636331, 106819, 2059, 1, 1, 6305, 778765, 10365005, 23679901, 10365005, 778765, 6305, 1

Offset: 1

N. J. A. Sloane, Oct 04 2015

Two 1's are connected if they are in the same row or column. The requirement is for them to form a single connected set.
The number of m X n binary matrices with no zero rows or columns is given by A183109(m, n). If there are multiple components (not connected) then they cannot share either rows or columns. For i < n and j < m there are T(i,j) ways of creating an i X j component that occupies the first row. Its remaining i-1 rows may be on any of the remaining m-1 rows with its j columns on any of the n columns. The m-i rows and n-j columns not used by this component can be any matrix with no zero rows or columns.
T(m,n) is also the number of bipartite connected labeled graphs with parts of size m and n. (See A005333, A227322.)
This is the array a(m,n) in Kreweras (1969). Kreweras describes this as a symmetric triangle read by rows, giving numbers of connected relations.
The companion array b(m,n) (and the first few of its diagonals) in Kreweras (1969) should also be added to the OEIS if they are not already present.

			Table starts:
==========================================================================
m\n| 1    2      3         4           5             6               7
---|----------------------------------------------------------------------
1  | 1    1      1         1           1             1               1 ...
2  | 1    5     19        65         211           665            2059 ...
3  | 1   19    205      1795       14221        106819          778765 ...
4  | 1   65   1795     36317      636331      10365005       162470155 ...
5  | 1  211  14221    636331    23679901     805351531     26175881341 ...
6  | 1  665 106819  10365005   805351531   56294206205   3735873535339 ...
7  | 1 2059 778765 162470155 26175881341 3735873535339 502757743028605 ...
...
As a triangle, this begins:
  1;
  1,    1;
  1,    5,      1;
  1,   19,     19,      1;
  1,   65,    205,     65,      1;
  1,  211,   1795,   1795,    211,      1;
  1,  665,  14221,  36317,  14221,    665,    1;
  1, 2059, 106819, 636331, 636331, 106819, 2059, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..780
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.

Essentially same table as triangle A227322 (where the antidiagonals only go halfway).
Main diagonal is A005333.
Initial diagonals give A001047, A002501, A002502.
Cf. A226658, A123260, A286189, A183109, A048291, A287274.

A183109[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m-j) - 1)^n, {j, 0, m}];
T[m_, n_] := A183109[m, n] - Sum[T[i, j]*A183109[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
Table[T[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

G(N)={my(S=matrix(N,N), T=matrix(N,N));
for(m=1,N,for(n=1,N,
S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
T[m,n]=S[m,n]-sum(i=1, m-1, sum(j=1, n-1, T[i,j]*S[m-i,n-j]*binomial(m-1,i-1)*binomial(n,j)));
));T}
G(7) \\ Andrew Howroyd, May 22 2017

T(m,n) = A183109(m,n) - Sum_{i=1..m-1} Sum_{j=1..n-1} T(i,j)*A183109(m-i, n-j)*binomial(m-1,i-1)*binomial(n,j). - Andrew Howroyd, May 22 2017

Revised by N. J. A. Sloane, May 26 2017, to incorporate material from Andrew Howroyd's May 22 2017 submission (formerly A287297), which was essentially identical to this, although giving an alternative description and more information.

A287065 Number of dominating sets on the n X n rook graph.

Original entry on oeis.org

1, 11, 421, 59747, 32260381, 67680006971, 559876911043381, 18412604442711949187, 2416403019417984915336061, 1267413006543912045144741284411, 2658304092145691708492995820522716981, 22300364428188338185156192161829091442585827

Offset: 1

Eric W. Weisstein, May 19 2017

nonn

Number of {0,1} n X n matrices with no zero rows or no zero columns. - Geoffrey Critzer, Jan 15 2024

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

Main diagonal of A287274.
Row sums of A368831.
Cf. A183109, A002720, A048291, A173403.

Table[(2^n - 1)^n + Sum[Binomial[n, i] Sum[(-1)^j (-1 + 2^(n - j))^i Binomial[n, j], {j, 0, n}], {i, n - 1}], {n, 20}] (* Eric W. Weisstein, May 27 2017 *)

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(n)=(2^n-1)^n + sum(i=1,n-1,b(n,i)*binomial(n,i)); \\ Andrew Howroyd, May 22 2017

a(n) = (2^n-1)^n + Sum_{i=1..n-1} binomial(n,i) * A183109(n,i). - Andrew Howroyd, May 22 2017

a(6)-a(12) from Andrew Howroyd, May 22 2017

A290632 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the 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, 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.

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

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

Original entry on oeis.org

1, 3, 3, 7, 9, 7, 15, 39, 39, 15, 31, 177, 325, 177, 31, 63, 783, 2931, 2931, 783, 63, 127, 3369, 26077, 51465, 26077, 3369, 127, 255, 14199, 225459, 894675, 894675, 225459, 14199, 255, 511, 58977, 1901725, 15195897, 30331861, 15195897, 1901725, 58977, 511

Offset: 1

Andrew Howroyd, Feb 24 2023

			Array begins:
=======================================================
m\n|  1    2      3        4          5           6 ...
---+---------------------------------------------------
1  |  1    3      7       15         31          63 ...
2  |  3    9     39      177        783        3369 ...
3  |  7   39    325     2931      26077      225459 ...
4  | 15  177   2931    51465     894675    15195897 ...
5  | 31  783  26077   894675   30331861  1010163363 ...
6  | 63 3369 225459 15195897 1010163363 66273667449 ...
  ...

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

Main diagonal is A289196.
Rows 1..2 are A000225, A360876.
Cf. A287274, A360873.

\\ S is A183109, T is A262307, U is this sequence.
G(M,N=M)={S=matrix(M, N); T=matrix(M, N); U=matrix(M, N);
for(m=1, M, for(n=1, N,
  S[m, n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
  T[m, n]=S[m, n]-sum(i=1, m-1, sum(j=1, n-1, T[i, j]*S[m-i, n-j]*binomial(m-1, i-1)*binomial(n, j)));
  U[m, n]=sum(i=1, m, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n, j)*T[m, j])-T[m, n] )); U
}
{ my(A=G(7)); for(n=1, #A~, print(A[n,])) }

T(m,n) = (Sum_{i=1..m} binomial(m,i) * A262307(n,i)) + (Sum_{j=1..n} binomial(n,j) * A262307(m,j)) - A262307(m,n).

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

A384116 Array read by antidiagonals: T(n,m) is the number of 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, 4, 9, 4, 1, 1, 11, 39, 39, 11, 1, 1, 26, 183, 334, 183, 26, 1, 1, 57, 833, 3087, 3087, 833, 57, 1, 1, 120, 3629, 27472, 53731, 27472, 3629, 120, 1, 1, 247, 15291, 236127, 922515, 922515, 236127, 15291, 247, 1, 1, 502, 63051, 1975246, 15524639, 30844786, 15524639, 1975246, 63051, 502, 1

Offset: 0

Andrew Howroyd, May 19 2025

			Array begins:
=================================================================
n\m | 0   1     2       3         4           5             6 ...
----+------------------------------------------------------------
  0 | 1   1     1       1         1           1             1 ...
  1 | 1   0     1       4        11          26            57 ...
  2 | 1   1     9      39       183         833          3629 ...
  3 | 1   4    39     334      3087       27472        236127 ...
  4 | 1  11   183    3087     53731      922515      15524639 ...
  5 | 1  26   833   27472    922515    30844786    1019569593 ...
  6 | 1  57  3629  236127  15524639  1019569593   66544564805 ...
  7 | 1 120 15291 1975246 256594143 33329148492 4314985562475 ...
  ...

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

Main diagonal is A303208.
Column 0 is A000012.
Column 1 is A000295(n), n > 0.
Column 2 is A287063(n), n > 1.
Cf. A287274, A384117, A384118.

B(n,m) = {sum(i=0, min(n,m), (-1)^i*binomial(n,i)*binomial(m,i)*i!*(2^(n-i)-1)^(m-i))}
T(n,m) = {B(n,m) - sum(i=1, m, (-1)^i*binomial(m,i)*B(m-i,n))}

T(n,m) = B(n,m) - Sum_{i=1..m} (-1)^i*binomial(m,i)*B(m-i,n), where B(n,m) = Sum_{i=0..m} (-1)^i*binomial(n,i)*binomial(m,i)*i!*(2^(n-i)-1)^(m-i).

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

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

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

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A287065 Number of dominating sets on the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

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