A072590 Table T(n,k) giving number of spanning trees in complete bipartite graph K(n,k), read by antidiagonals.

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

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

Taylor Brysiewicz and Aida Maraj, Lawrence Lifts, Matroids, and Maximum Likelihood Degrees, arXiv:2310.13064 [math.CO], 2023. See p. 13.

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: A168619 A099759 A350819 * A350745 A111636 A220688

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