|
%I #74 Nov 19 2023 13:55:44
%S 1,1,2,3,6,6,15,30,36,24,105,210,270,240,120,945,1890,2520,2520,1800,
%T 720,10395,20790,28350,30240,25200,15120,5040,135135,270270,374220,
%U 415800,378000,272160,141120,40320,2027025,4054050,5675670,6486480
%N 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).
%C 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).
%C 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
%C 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
%H Michael De Vlieger, <a href="/A102625/b102625.txt">Table of n, a(n) for n = 0..11475</a> (rows 0 <= n <= 150, flattened)
%H Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H M. R. T. Dale, J. W. Moon, <a href="https://dx.doi.org/10.1016/0378-3758(93)90035-5">The permuted analogues of three Catalan sets</a>, J. Stat. Plan. Inf. 34 (1) (1993) 75-87 Table 1
%H S. Lehr, J. Shallit and J. Tromp, <a href="http://dx.doi.org/10.1016/0304-3975(95)00234-0">On the vector space of the automatic reals</a>, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
%H Jiaxi Lu and Yuanzhe Ding, <a href="https://arxiv.org/abs/2106.09471">A skeleton model to enumerate standard puzzle sequences</a>, arXiv:2106.09471 [math.CO]], 2021.
%H Bao-Xuan Zhu, <a href="https://arxiv.org/abs/2006.14485">Total positivity from a generalized cycle index polynomial</a>, arXiv:2006.14485 [math.CO], 2020.
%F T(n,k) = k*(2*n-k+1)!/[2^(n-k+1)*(n-k+1)!] (1 <= k <= n+1).
%F From _Tom Copeland_, Nov 11 2007: (Start)
%F 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.
%F 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.
%F 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)
%F 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
%F From _Peter Bala_, Jul 09 2014: (Start)
%F T(n,k) = k!*A001497(n,k) modulo offset differences.
%F 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)
%F From _Tom Copeland_, Aug 06 2016: (Start)
%F 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.
%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.
%F 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)
%F From _Peter Bala_, Apr 16 2017: (Start)
%F T(n,k) = k*T(n-1,k-1) + (2*n - k)*T(n-1,k).
%F 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)
%e Triangle starts:
%e 1;
%e 1, 2;
%e 3, 6, 6;
%e 15, 30, 36, 24;
%e ...
%e Production matrix begins:
%e 1, 2
%e 1, 2, 3
%e 1, 2, 3, 4
%e 1, 2, 3, 4, 5
%e 1, 2, 3, 4, 5, 6
%e 1, 2, 3, 4, 5, 6, 7
%e 1, 2, 3, 4, 5, 6, 7, 8
%e 1, 2, 3, 4, 5, 6, 7, 8, 9
%e ... - _Philippe Deléham_, Sep 30 2014
%e From _Peter Bala_, Apr 16 2017: (Start)
%e The Catalan tree starts o1
%e / \
%e / \
%e / \
%e / \
%e / \
%e o1 o2
%e / \ /|\
%e / \ / | \
%e / \ / | \
%e o1 o2 o1 o2 o3
%e Level 2:
%e 2 vertices labeled 1: total weight 1x1x1 + 1x2x1 = 3
%e 2 vertices labeled 2: total weight 2x1x1 + 2x2x1 = 6
%e 1 vertex labeled 3: total weight 3x2x1 = 6
%e (End)
%p 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:
%p for n from 0 to 8 do seq(A102625(n,k),k=1..n+1) od; # yields sequence in triangular form
%t 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 *)
%o (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 */
%Y Cf. A001147 (row sums), A001286, A001497, A039683, A132382, A145271, A000108, A033184.
%K nonn,tabl,easy
%O 0,3
%A _Emeric Deutsch_, Jan 31 2005
|
