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!)
A072590 Table T(n,k) giving number of spanning trees in complete bipartite graph K(n,k), read by antidiagonals. 9
1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 81, 32, 1, 1, 80, 432, 432, 80, 1, 1, 192, 2025, 4096, 2025, 192, 1, 1, 448, 8748, 32000, 32000, 8748, 448, 1, 1, 1024, 35721, 221184, 390625, 221184, 35721, 1024, 1, 1, 2304, 139968, 1404928, 4050000, 4050000 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

REFERENCES

J. W. Moon, Counting Labeled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Exercise 5.66.

LINKS

T. D. Noe, Antidiagonals d=1..50, flattened

H. I. Scoins, The number of trees with nodes of alternate parity, Proc. Cambridge Philos. Soc. 58 (1962) 12-16.

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Eric Weisstein's World of Mathematics, Spanning Tree

FORMULA

T(n, k) = n^(k-1) * k^(n-1).

E.g.f.: A(x,y) - 1, where: A(x,y) = exp( x*exp( y*A(x,y) ) ) = Sum_{n>=0} Sum_{k=0..n} (n-k)^k * (k+1)^(n-k-1) * x^(n-k)/(n-k)! * y^k/k!. - Paul D. Hanna, Jan 22 2019

EXAMPLE

From Andrew Howroyd, Oct 29 2019: (Start)

Array begins:

============================================================

n\k | 1   2     3       4        5         6           7

----+-------------------------------------------------------

  1 | 1   1     1       1        1         1           1 ...

  2 | 1   4    12      32       80       192         448 ...

  3 | 1  12    81     432     2025      8748       35721 ...

  4 | 1  32   432    4096    32000    221184     1404928 ...

  5 | 1  80  2025   32000   390625   4050000    37515625 ...

  6 | 1 192  8748  221184  4050000  60466176   784147392 ...

  7 | 1 448 35721 1404928 37515625 784147392 13841287201 ...

  ...

(End)

MATHEMATICA

t[n_, k_] := n^(k-1) * k^(n-1); Table[ t[n-k+1, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 21 2013 *)

PROG

(PARI) {T(n, k) = if( n<1 || k<1, 0, n^(k-1) * k^(n-1))}

CROSSREFS

Columns 2..3 are A001787, A069996.

Main diagonal is A068087.

Antidiagonal sums are A132609.

Cf. A070285, A328887, A328888.

Sequence in context: A213166 A168619 A099759 * A111636 A220688 A146990

Adjacent sequences:  A072587 A072588 A072589 * A072591 A072592 A072593

KEYWORD

nonn,tabl,easy,nice

AUTHOR

Michael Somos, Jun 23 2002

EXTENSIONS

Scoins reference from Philippe Deléham, Dec 22 2003

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 July 10 05:51 EDT 2020. Contains 335572 sequences. (Running on oeis4.)