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,8

Comments

Row sums = (n^n-n)/(n-1)^2 = A058128(n).

Column k without leading zeros is the k-th exponential (also called binomial) convolution of the sequence {A000272(n+1)} = {A232006(n+1, 1)}, for n >= 0, with e.g.f. LamberW(-x)/(-x), where LambertW is the principal branch of the Lambert W-function. This is also the row polynomial P(n, x) of the unsigned triangle A137452, evaluated at x = k. - 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

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)

Example

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

Mathematica

Prepend[Table[Table[k n^(n-k-1), {k, 0, n}], {n, 1, 8}], {1}]//Grid

Prog

(PARI) {T(n, k) = if( k<0 || k>n, 0, n^(n-k-1))}; /* Michael Somos, May 15 2017 */

Crossrefs

Cf. A058128, |A137452|.

Columns give A000007, A000272, A007334, A362354, A362355, A362356, ...

Sequence in context: A370419 A321964 A197819 * A202820 A113081 A172184

Adjacent sequences: A232003 A232004 A232005 * A232007 A232008 A232009

Keyword

nonn,tabl,easy

Author

Geoffrey Critzer, Nov 16 2013

Status

approved