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
Examples
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)
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
Crossrefs
Programs
-
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 *) -
PARI
{T(n, k) = if( n<1 || k<1, 0, n^(k-1) * k^(n-1))}
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
Extensions
Scoins reference from Philippe Deléham, Dec 22 2003