A227322 -id:A227322 - cp's OEIS frontend

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

1, 5, 205, 36317, 23679901, 56294206205, 502757743028605, 17309316971673776957, 2333508400614646874734621, 1243000239291173897659593056765, 2629967962392578020413552363565293565, 22170252073745058975210005804934596601690557

Offset: 1

N. J. A. Sloane

nonn

Conjecture: if n > 1, then a(n) is the number of labeled digraphs D (allowing self-loops) with n vertices such that D|D' and D'|D are (strongly) connected (see preliminaries of Broere et al.). - Lorenzo Sauras Altuzarra, Sep 17 2022

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
I. Broere, W. Imrich, R. Kalinowski, and M. Pilsniak, Asymmetric colorings of products of graphs and digraphs, Discrete Applied Mathematics 266 (p. 56-64), 2019.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Main diagonal of A262307 and A227322.

c[0, 1] = c[1, 0] = 1; c[0, ] = c[, 0] = 0; c[n_, m_] := c[n, m] = 2^(n*m) - Sum[If[k < n || j < m, Binomial[n - 1, k - 1]*Binomial[m, j]* 2^((n - k)*(m - j))*c[k, j], 0], {k, 1, n}, {j, 0, m}];
a[n_] := c[n, n];
Array[a, 12] (* Jean-François Alcover, Sep 03 2019 *)

a(n) = c(n,n) where c(0,1) = 1, c(0,m) = 0, c(n,m) = 2^(n*m) - Sum_{1 <= k <= n, 0 <= j <= m, k < n or j < m} C(n-1, k-1) * C(m, j) * 2^((n-k)*(m-j)) * c(k, j). - Sean A. Irvine, May 11 2016

More precise definition by Pavel Irzhavski, Jul 09 2013

More terms from Sean A. Irvine, May 11 2016

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions