login
A328888
Array read by antidiagonals: T(n,m) is the number of acyclic edge covers of the complete bipartite graph K_{n,m}.
5
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
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.
Sequence in context: A157268 A146959 A157632 * A176125 A168289 A141690
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Oct 29 2019
STATUS
approved