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.

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

Table of n, a(n) for n=0..35.

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

Cf. A226658, A123260.

Main diagonal gives: A005333.

Columns m=2, 3, 4 give: A001047, A002501, A002502.

Sequence in context: A222061 A345453 A064315 * A216718 A184180 A256069

Adjacent sequences: A227319 A227320 A227321 * A227323 A227324 A227325

Keyword

easy,nonn,tabl

Author

Pavel Irzhavski, Jul 06 2013

Status

approved