|
|
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.
|
|
8
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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) 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
|
|
|
FORMULA
|
T(n,k) = binomial(n, k)*n^(n-k).
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|