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
KEYWORD
AUTHOR
Pavel Irzhavski, Jul 06 2013
STATUS
approved