|
| |
|
|
A328887
|
|
Array read by antidiagonals: T(n,m) is the number of acyclic edge sets in the complete bipartite graph K_{n,m}.
|
|
6
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 15, 8, 1, 1, 16, 54, 54, 16, 1, 1, 32, 189, 328, 189, 32, 1, 1, 64, 648, 1856, 1856, 648, 64, 1, 1, 128, 2187, 9984, 16145, 9984, 2187, 128, 1, 1, 256, 7290, 51712, 129000, 129000, 51712, 7290, 256, 1, 1, 512, 24057, 260096, 968125, 1475856, 968125, 260096, 24057, 512, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
In other words, the number of spanning forests of the complete bipartite graph K_{n,m} with isolated vertices allowed.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,m) = 1 + Sum_{i=1..n} Sum_{j=1..m} binomial(n,i)*binomial(m,j)*A328888(i,j).
|
|
|
EXAMPLE
|
Array begins:
====================================================================
n\m | 0 1 2 3 4 5 6 7
----+---------------------------------------------------------------
0 | 1 1 1 1 1 1 1 1 ...
1 | 1 2 4 8 16 32 64 128 ...
2 | 1 4 15 54 189 648 2187 7290 ...
3 | 1 8 54 328 1856 9984 51712 260096 ...
4 | 1 16 189 1856 16145 129000 968125 6925000 ...
5 | 1 32 648 9984 129000 1475856 15450912 151201728 ...
6 | 1 64 2187 51712 968125 15450912 219682183 2862173104 ...
7 | 1 128 7290 260096 6925000 151201728 2862173104 48658878080 ...
...
|
|
|
PROG
|
(PARI) \\ here U is A328888 as matrix.
U(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}
T(n, m=n)={my(M=U(n, m)); matrix(n+1, m+1, n, m, 1 + sum(i=1, n-1, sum(j=1, m-1, binomial(n-1, i)*binomial(m-1, j)*M[i, j])))}
{ my(A=T(7)); for(i=1, #A, print(A[i, ])) }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
