

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


3



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

Table of n, a(n) for n=0..39.
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.
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 12, 193210.


FORMULA

T(n,k) = k(2nk+1)!/[2^(nk+1)*(nk+1)!] (1 <= k <= n+1).
From Tom Copeland, Nov 11 2007: (Start)
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
From Peter Bala, Jul 09 2014: (Start)
T(n,k) = k!*A001497(n,k) modulo offset differences.
The nth row polynomial R(n,x) = (1)^n/(x  1)*( sum {k = 1..inf} k*(k  2)*...*(k  2*n)*(x/(x  1))^k ). Cf. the Dobinskitype formula for the row polynomials of A001497. (End)
From Tom Copeland, Aug 06 2016: (Start)
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+2t) 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 + 2t^2) + 2 * t * t + t * 1 = 0. (End)
From Peter Bala, Apr 16 2017: (Start)
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
...  Philippe Deléham, Sep 30 2014
From Peter Bala, Apr 16 2017: (Start)
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

T:=proc(n, k) if k<=n+1 then k*(2*nk+1)!/2^(nk+1)/(nk+1)! else 0 fi end: for n from 0 to 8 do seq(T(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

Cf. A001147, A001286, A001497, A039683, A132382, A145271, A000108, A033184.
Sequence in context: A129650 A319055 A007894 * A117777 A223547 A049297
Adjacent sequences: A102622 A102623 A102624 * A102626 A102627 A102628


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jan 31 2005


STATUS

approved



