A232006 Triangular array read by rows: T(n,k) is the number of simple labeled graphs on vertex set {1,2,...,n} with exactly k components (all of which are trees) such that the labels {1,2,...,k} are all in distinct components (trees), n >= 0, 0 <= k <= n.
1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 16, 8, 3, 1, 0, 125, 50, 15, 4, 1, 0, 1296, 432, 108, 24, 5, 1, 0, 16807, 4802, 1029, 196, 35, 6, 1, 0, 262144, 65536, 12288, 2048, 320, 48, 7, 1, 0, 4782969, 1062882, 177147, 26244, 3645, 486, 63, 8, 1, 0, 100000000, 20000000, 3000000, 400000, 50000, 6000, 700, 80, 9, 1
Offset: 0
Examples
The triangle begins: n\k 0 1 2 3 4 5 6 7 8 9 10 ... 0: 1 1: 0 1 2: 0 1 1 3: 0 3 2 1 4: 0 16 8 3 1 5: 0 125 50 15 4 1 6: 0 1296 432 108 24 5 1 7: 0 16807 4802 1029 196 35 6 1 8: 0 262144 65536 12288 2048 320 48 7 1 9: 0 4782969 1062882 177147 26244 3645 486 63 8 1 10: 0 100000000 20000000 3000000 400000 50000 6000 700 80 9 1 ... Reformatted by _Wolfdieter Lang_, Apr 24 2023
References
- R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Proposition 5.3.2.
Links
- G. C. Greubel, Rows n=0..75 of triangle, flattened
- Chad Casarotto, Graph Theory and Cayley's Formula, 2006
- Alan D. Sokal, A remark on the enumeration of rooted labeled trees, arXiv:1910.14519 [math.CO], 2019.
- Marc van Leeuwen, I am stuck with a combinatoric problem... Math Stackexchange, Answer May 14 2017.
- Eric Weisstein's World of Mathematics, Lambert W-function
- Wikipedia, Lambert W function
Crossrefs
Programs
-
Mathematica
Prepend[Table[Table[k n^(n-k-1),{k,0,n}],{n,1,8}],{1}]//Grid -
PARI
{T(n, k) = if( k<0 || k>n, 0, n^(n-k-1))}; /* Michael Somos, May 15 2017 */
Formula
T(n, k) = k*n^(n-k-1).
T(n, k) = Sum_{i=0..n-k} T(n-1, k-1+i)*C(n-k,i), T(0, 0) = 1, T(n, 0) = 0 when n >= 1.
From Wolfdieter Lang, Apr 24 2023: (Start)
E.g.f. for {T(n+k, k)}_{n>=0} is (LambertW(-x)/(-x))^k, for k >= 0.
T(n, k) = Sum_{m=0..n-k} |A137452(n-k, m)|*k^m, for n >= 0 and k = 0..n. That is, T(n, n) = 1, for n >= 0, and T(n, k) = Sum_{m=1..n-k} binomial(n-k-1, m-1)*(n-k)^(n-k-m)*k^m, for k = 0..n-1 and n >= k+1. (End)
Comments