|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
In other words, the number of spanning forests of the complete bipartite graph K_{n,m} without isolated vertices.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
