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).
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
Offset: 0
Examples
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)
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.
Programs
-
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 *) -
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 */
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)
Comments