

A102625


Triangle read by rows: T(n,k) is the sum of the weights of all vertices labeled k at depth n in the Catalan tree (1 <= k <= n+1, n >= 0).


4



1, 1, 2, 3, 6, 6, 15, 30, 36, 24, 105, 210, 270, 240, 120, 945, 1890, 2520, 2520, 1800, 720, 10395, 20790, 28350, 30240, 25200, 15120, 5040, 135135, 270270, 374220, 415800, 378000, 272160, 141120, 40320, 2027025, 4054050, 5675670, 6486480
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The Catalan tree is defined as follows: the root is labeled 1 and each vertex labeled i has i+1 children labeled 1,2,...,i+1. The weight of a vertex v is the product of all labels on the path from the root to v. Row n contains n+1 terms. Row sums and column 1 yield the double factorials (A001147). T(n,n+1)=(n+1)!, T(n,n)=n(n+1)!/2 (A001286; Lah numbers).
This table counts permutations of the multiset {1,1,2,2,...,n,n} satisfying the condition "the first appearance of i + 1 follows the first appearance of i" by the position of the first appearance of n. Specifically, T(n+1,k) is the number of such permutations for which n first occurs in position 2n+1k. For example, with n=2 and k=1, T(3,1)=6 counts 121323, 121332, 122313, 122331, 112323, 112332.  David Callan, Nov 29 2007
T(n+1,k) is also the number of rooted complete binary forests with n labeled leaves and k labeled roots. This follows by comparing exponential generating functions; see Example 5.2.6 and Proposition 5.1.3 of Stanley's "Enumerative Combinatorics 2."  Timothy Y. Chow, Mar 28 2017


LINKS

Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.C. Raoult, Springer 1992, pp. 2448.


FORMULA

T(n,k) = k*(2*nk+1)!/[2^(nk+1)*(nk+1)!] (1 <= k <= n+1).
Bivariate G.F.: exp[P(.,t)*x] = D_x {1  [g(x)/(1+t*g(x))]} = 1 / {(1+g(x))*[1+t*g(x)]^2}, where g(x) = sqrt(12*x)  1 and P(n,t) = Sum_{k=0..n} T(n,k) * t^k.
Also D_x g(x) = (12*x)^(1/2) = exp[x*A001147(.)] = exp[x *(2*(.)1)!! ], so the coefficients of x^n/n! in the expansion of g(x) are (2*(n1)1)!! = A001147(n1) for n > 0.
See A132382 for an array which is essentially the revert from which this G.f. may be derived and for connections to other arrays. (End)
E.g.f.: 1/(1  x + x*sqrt(12*z)) = 1 + x*z + (x+2*x^2)*z^2/2! + (3*x+6*x^2+6*x^3)*z^3/3! + .... T(n,k) gives the number of plane recursive trees on n+2 nodes where the root has degree k (Bergeron et al., Corollary 5).  Peter Bala, Jul 09 2012
T(n,k) = k!*A001497(n,k) modulo offset differences.
The nth row polynomial R(n,x) = (1)^n/(x  1)*( Sum_{k = 1..infinity} k*(k  2)*...*(k  2*n)*(x/(x  1))^k ). Cf. the Dobinskitype formula for the row polynomials of A001497. (End)
From the 2007 formulas above, an alternate g.f. for this entry is GF(x,t) = g(x) / [1 + t*g(x)] = x + (1 + 2*t)*x^2/2! + (3 + 6*t + 6*t^2)*x^3/3! + ... with compositional inverse GFinv(x,t) = {1  [1  x / (1+t*x)]^2} / 2 = (1/2)[x / (1+t*x)]^2 + x / (1+t*x) = Sum_{n>0} (1)^(n+1) [(n1)/2*t^(n2) + t^(n1)]*x^n, a series containing the Lah numbers A001286 when expressed as an e.g.f.
From A145271, with K(x,t) = 1 / dGinv(x,t)/dx = 1 + (1+2*t) x + (1+t+t^2) x^2 + x^3 / [1(1t)*x], then [K(x,t) d/dx]^n x evaluated at x=0 gives the nth row polynomial of this entry.
Since the reciprocal of Bala's e.g.f. above generates a shifted, signed A001147, for the polynomials P(n,t) generated by Bala's e.g.f., umbrally (P(.,t) + a.)^n = 0 for n > 0 with a_0 = 1 and a_n = t * A001147(n1) for n > 0. E.g., (P(.,t) + a.)^2 = a_0 * P(2,t) + 2 a_1 * P(1,t) + a_2 * P(0,t) = 1 * (t + 2*t^2) + 2 * t * t + t * 1 = 0. (End)
T(n,k) = k*T(n1,k1) + (2*n  k)*T(n1,k).
E.g.f.: t*x*c(x/2)/(1  t*x*c(x/2)) = t*x + (t + 2*t^2)*x^2/2! + (3*t + 6*t^2 + 6*t^2)*x^3/3! + ..., where c(x) = (1  sqrt(1  4*x))/(2*x) is the g.f. for the Catalan numbers A000108. Note that the related g.f. t*x*c(x)/(1  t*x*c(x)) is the o.g.f. for A033184 (essentially the same as the Riordan array A106566) and enumerates the number of vertices labeled k on the n_th level of the Catalan tree (k >= 1, n >= 0). (End)


EXAMPLE

Triangle starts:
1;
1, 2;
3, 6, 6;
15, 30, 36, 24;
...
Production matrix begins:
1, 2
1, 2, 3
1, 2, 3, 4
1, 2, 3, 4, 5
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8, 9
The Catalan tree starts o1
/ \
/ \
/ \
/ \
/ \
o1 o2
/ \ /\
/ \ /  \
/ \ /  \
o1 o2 o1 o2 o3
Level 2:
2 vertices labeled 1: total weight 1x1x1 + 1x2x1 = 3
2 vertices labeled 2: total weight 2x1x1 + 2x2x1 = 6
1 vertex labeled 3: total weight 3x2x1 = 6
(End)


MAPLE

A102625:=proc(n, k) if k<=n+1 then k*(2*nk+1)!/2^(nk+1)/(nk+1)! else 0 fi end proc:
for n from 0 to 8 do seq(A102625(n, k), k=1..n+1) od; # yields sequence in triangular form


MATHEMATICA

t[n_, k_] := k*(2nk+1)!/(2^(nk+1)*(nk+1)!); Table[t[n, k], {n, 0, 8}, {k, 1, n+1}] // Flatten (* JeanFrançois Alcover, Jan 21 2013 *)


PROG

(PARI) {T(n, k) = my(m = nk+1); if( k<1  k>n+1, 0, k * (n+m)! / (2^m * m!))}; /* Michael Somos, Aug 16 2016 */


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



