A071207 Triangular array T(n,k) read by rows, giving number of rooted trees on the vertex set {1..n+1} where k children of the root have a label smaller than the label of the root.

1, 1, 1, 4, 4, 1, 27, 27, 9, 1, 256, 256, 96, 16, 1, 3125, 3125, 1250, 250, 25, 1, 46656, 46656, 19440, 4320, 540, 36, 1, 823543, 823543, 352947, 84035, 12005, 1029, 49, 1, 16777216, 16777216, 7340032, 1835008, 286720, 28672, 1792, 64, 1, 387420489

Offset: 0

Author

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

Keywords

• easy
• nonn
• tabl

Comments

The n-th term of the n-th binomial transform of a sequence {b} is given by {d} where d(n) = sum(k=0,n,T(n,k)*b(k)) and T(n,k)=binomial(n,k)*n^(n-k); such diagonals are related to the hyperbinomial transform (A088956). - Paul D. Hanna, Nov 04 2003

T(n,k) gives the number of divisors of A181555(n) with (n-k) distinct prime factors. See also A001221, A146289, A146290, A181567. - Matthew Vandermast, Oct 31 2010

T(n,k) is the number of partial functions on {1,2,...,n} leaving exactly k elements undefined. Row sums = A000169. - Geoffrey Critzer, Jan 08 2012

As a triangular matrix, transforms rows into diagonals in the table of coefficients of successive iterations of x/(1-x). - Paul D. Hanna, Jan 19 2014

Also the number of rooted trees on n+1 labeled vertices in which some specified vertex (say, vertex 1) has k children. - Alan Sokal, Jul 22 2022

Examples

			1
1     1
4     4     1
27    27    9     1
256   256   96    16    1
3125  3125  1250  250   25    1
46656 46656 19440 4320  540   36    1
		

Links

• G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
• C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
• Alan D. Sokal, A remark on the enumeration of rooted labeled trees, arXiv:1910.14519 [math.CO], 2019 and Discrete Math. 343, 111865 (2020).

Crossrefs

Cf. A000169, A000312, A089466, A088956, A166900.

Programs

Maple

T:= (n, k)-> binomial(n, k)*n^(n-k): seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

Prepend[Flatten[ Table[Table[Binomial[n, k] n^(n - k), {k, 0, n}], {n, 1, 8}]], 1]  (* Geoffrey Critzer, Jan 08 2012 *)

PARI

T(n,k)=if(k<0 || k>n,0,binomial(n,k)*n^(n-k))

PARI

/* Transforms rows into diagonals in the iterations of x/(1-x): */
{T(n, k)=local(F=x, M, N, P, m=n); M=matrix(m+2, m+2, r, c, F=x; for(i=1, r+c-2, F=subst(F, x, x/(1-x+x*O(x^(m+2))))); polcoeff(F, c)); N=matrix(m+1, m+1, r, c, F=x; for(i=1, r, F=subst(F, x, x/(1-x+x*O(x^(m+2))))); polcoeff(F, c)); P=matrix(m+1, m+1, r, c, M[r+1, c]); (P~*N~^-1)[n+1, k+1]}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print("")) \\ Paul D. Hanna, Jan 19 2014

Formula

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

E.g.f.: (-LambertW(-y)/y)^x/(1+LambertW(-y)). - Vladeta Jovovic

Extensions

Name edited by Alan Sokal, Jul 22 2022