The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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+1-k. 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 Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened) Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48. M. R. T. Dale and J. W. Moon, The permuted analogues of three Catalan sets, J. Stat. Plan. Inf. 34 (1) (1993) 75-87 Table 1 S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210. Jiaxi Lu and Yuanzhe Ding, A skeleton model to enumerate standard puzzle sequences, arXiv:2106.09471 [math.CO], 2021. Bao-Xuan Zhu, Total positivity from a generalized cycle index polynomial, arXiv:2006.14485 [math.CO], 2020. FORMULA T(n,k) = k*(2*n-k+1)!/[2^(n-k+1)*(n-k+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(1-2*x) - 1 and P(n,t) = Sum_{k=0..n} T(n,k) * t^k. Also D_x g(x) = -(1-2*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*(n-1)-1)!! = -A001147(n-1) 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(1-2*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 n-th 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 Dobinski-type 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) [(n-1)/2*t^(n-2) + t^(n-1)]*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-(1-t)*x], then [K(x,t) d/dx]^n x evaluated at x=0 gives the n-th 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(n-1) 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) From Peter Bala, Apr 16 2017: (Start) T(n,k) = k*T(n-1,k-1) + (2*n - k)*T(n-1,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 A102625:=proc(n, k) if k<=n+1 then k*(2*n-k+1)!/2^(n-k+1)/(n-k+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*(2n-k+1)!/(2^(n-k+1)*(n-k+1)!); Table[t[n, k], {n, 0, 8}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Jan 21 2013 *) PROG (PARI) {T(n, k) = my(m = n-k+1); if( k<1 || k>n+1, 0, k * (n+m)! / (2^m * m!))}; /* Michael Somos, Aug 16 2016 */ CROSSREFS Cf. A001147 (row sums), A001286, A001497, A039683, A132382, A145271, A000108, A033184. Sequence in context: A319055 A339546 A007894 * A117777 A371991 A223547 Adjacent sequences: A102622 A102623 A102624 * A102626 A102627 A102628 KEYWORD nonn,tabl,easy AUTHOR Emeric Deutsch, Jan 31 2005 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 15 13:57 EDT 2024. Contains 375938 sequences. (Running on oeis4.)