login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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. 24-48.

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.

FORMULA

T(n,k) = k(2n-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..inf} 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+2t) 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 + 2t^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

T:=proc(n, k) if k<=n+1 then k*(2*n-k+1)!/2^(n-k+1)/(n-k+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*(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, 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 05:08 EDT 2018. Contains 316336 sequences. (Running on oeis4.)