login
A227322
Triangle read by rows: T(n, m) for 0 <= m <= n is the number of bipartite connected labeled graphs with parts of size n and m.
2
1, 1, 1, 0, 1, 5, 0, 1, 19, 205, 0, 1, 65, 1795, 36317, 0, 1, 211, 14221, 636331, 23679901, 0, 1, 665, 106819, 10365005, 805351531, 56294206205, 0, 1, 2059, 778765, 162470155, 26175881341, 3735873535339, 502757743028605
OFFSET
0,6
LINKS
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
FORMULA
T(n, m) = 2^(n*m) - sum for all (i, j) in ({1, 2, ..., n} X {1, 2, ..., m} UNION (1, 0)) \ (n, m) \ (1 - n, 0) of T(i, j)*C(n - 1, i - 1)*C(m, j)*2^((n - i)*(m - j)), where C(n, m) is the binomial coefficient (A007318). This relation can be obtained considering connected component which contains the first vertex of the largest part. (If the largest part has zero size we get T(0, 0) = 2^0 - 0 = 1 which is true.)
EXAMPLE
Triangle T(n, m) begins:
n\m 0 1 2 3 4 5 6 7
0 1
1 1 1
2 0 1 5
3 0 1 19 205
4 0 1 65 1795 36317
5 0 1 211 14221 636331 23679901
6 0 1 665 106819 10365005 805351531 56294206205
7 0 1 2059 778765 162470155 26175881341 3735873535339 502757743028605
...
Consider labeled bipartite graph with parts of size 2 and 2. To make graph connected it is possible to use all four possible edges or omit any one of them. Thus T(2, 2) = 5.
CROSSREFS
Main diagonal gives: A005333.
Columns m=2, 3, 4 give: A001047, A002501, A002502.
Sequence in context: A345453 A064315 A371994 * A216718 A184180 A256069
KEYWORD
easy,nonn,tabl
AUTHOR
Pavel Irzhavski, Jul 06 2013
STATUS
approved