A328888 Array read by antidiagonals: T(n,m) is the number of acyclic edge covers of the complete bipartite graph K_{n,m}.

1, 1, 1, 1, 6, 1, 1, 18, 18, 1, 1, 46, 132, 46, 1, 1, 110, 696, 696, 110, 1, 1, 254, 3150, 6728, 3150, 254, 1, 1, 574, 13086, 51760, 51760, 13086, 574, 1, 1, 1278, 51492, 348048, 632970, 348048, 51492, 1278, 1, 1, 2814, 195180, 2143736, 6466980, 6466980, 2143736, 195180, 2814, 1

Offset

1,5

Comments

In other words, the number of spanning forests of the complete bipartite graph K_{n,m} without isolated vertices.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Formula

T(n,m) = A072590(n, m) + Sum_{i=1..n-1} Sum_{j=1, m-1} binomial(n-1, i-1) * binomial(m, j) * A072590(i, j) * T(n-i, m-j).

Example

Array begins:
=============================================================
n\m | 1   2     3       4        5          6           7
----+--------------------------------------------------------
  1 | 1   1     1       1        1          1           1 ...
  2 | 1   6    18      46      110        254         574 ...
  3 | 1  18   132     696     3150      13086       51492 ...
  4 | 1  46   696    6728    51760     348048     2143736 ...
  5 | 1 110  3150   51760   632970    6466980    58620030 ...
  6 | 1 254 13086  348048  6466980   96208632  1231832364 ...
  7 | 1 574 51492 2143736 58620030 1231832364 21634786586 ...
...

Prog

(PARI)
T(n, m=n)={my(M=matrix(n, m), N=matrix(n, m, n, m, n^(m-1) * m^(n-1))); for(n=1, n, for(m=1, m, M[n, m] = N[n, m] + sum(i=1, n-1, sum(j=1, m-1, binomial(n-1, i-1)*binomial(m, j)*N[i, j]*M[n-i, m-j])))); M}
{ my(A=T(7)); for(i=1, #A, print(A[i, ])) }

Crossrefs

Column 2 is A328890.

Main diagonal is A328889.

Cf. A072590, A328887.

Sequence in context: A157268 A146959 A157632 * A176125 A168289 A141690

Adjacent sequences: A328885 A328886 A328887 * A328889 A328890 A328891

Keyword

nonn,tabl

Author

Andrew Howroyd, Oct 29 2019

Status

approved