login
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

%I #47 Jan 09 2023 11:51:09

%S 1,1,1,4,4,1,27,27,9,1,256,256,96,16,1,3125,3125,1250,250,25,1,46656,

%T 46656,19440,4320,540,36,1,823543,823543,352947,84035,12005,1029,49,1,

%U 16777216,16777216,7340032,1835008,286720,28672,1792,64,1,387420489

%N 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.

%C 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

%C 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

%C 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

%C 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

%C 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

%H G. C. Greubel, <a href="/A071207/b071207.txt">Table of n, a(n) for the first 50 rows, flattened</a>

%H C. Chauve, S. Dulucq and O. Guibert, <a href="http://www.cecm.sfu.ca/~cchauve/Publications/SFCA00.ps">Enumeration of some labeled trees</a>, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

%H Alan D. Sokal, <a href="https://arxiv.org/abs/1910.14519">A remark on the enumeration of rooted labeled trees</a>, arXiv:1910.14519 [math.CO], 2019 and Discrete Math. 343, 111865 (2020).

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

%F E.g.f.: (-LambertW(-y)/y)^x/(1+LambertW(-y)). - _Vladeta Jovovic_

%e 1

%e 1 1

%e 4 4 1

%e 27 27 9 1

%e 256 256 96 16 1

%e 3125 3125 1250 250 25 1

%e 46656 46656 19440 4320 540 36 1

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

%t Prepend[Flatten[ Table[Table[Binomial[n, k] n^(n - k), {k, 0, n}], {n, 1, 8}]], 1] (* _Geoffrey Critzer_, Jan 08 2012 *)

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

%o (PARI) /* Transforms rows into diagonals in the iterations of x/(1-x): */

%o {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]}

%o for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print("")) \\ _Paul D. Hanna_, Jan 19 2014

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

%K easy,nonn,tabl

%O 0,4

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

%E Name edited by _Alan Sokal_, Jul 22 2022