login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Math Stack Exchange, Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

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

Column k=2 is A006234.

Main diagonal is A297077.

Cf. A072590, A328888.

Sequence in context: A256894 A099594 A255256 * A299906 A117401 A144324

Adjacent sequences:  A328884 A328885 A328886 * A328888 A328889 A328890

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Oct 29 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 30 18:12 EDT 2020. Contains 337440 sequences. (Running on oeis4.)