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

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

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).

Formula

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

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

Example

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A116866 A126280 A170986 * A136214 A067328 A111845

Adjacent sequences: A071204 A071205 A071206 * A071208 A071209 A071210

Keyword

easy,nonn,tabl

Author

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

Extensions

Name edited by Alan Sokal, Jul 22 2022

Status

approved