|
| |
|
|
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.
|
|
12
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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;
...
|
|
|
MATHEMATICA
|
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}];
|
|
|
PROG
|
(PARI)
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}
|
|
|
CROSSREFS
|
Essentially same table as triangle A227322 (where the antidiagonals only go halfway).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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.
|
|
|
STATUS
|
approved
|
| |
|
|
