A029760 -id:A029760 - cp's OEIS frontend

A039598 Triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x). Sometimes called Catalan's triangle.

1, 2, 1, 5, 4, 1, 14, 14, 6, 1, 42, 48, 27, 8, 1, 132, 165, 110, 44, 10, 1, 429, 572, 429, 208, 65, 12, 1, 1430, 2002, 1638, 910, 350, 90, 14, 1, 4862, 7072, 6188, 3808, 1700, 544, 119, 16, 1, 16796, 25194, 23256, 15504, 7752, 2907, 798, 152, 18, 1

Offset: 0

N. J. A. Sloane

T(n,k) is the number of leaves at level k+1 in all ordered trees with n+1 edges. - Emeric Deutsch, Jan 15 2005
Riordan array ((1-2x-sqrt(1-4x))/(2x^2),(1-2x-sqrt(1-4x))/(2x)). Inverse array is A053122. - Paul Barry, Mar 17 2005
T(n,k) is the number of walks of n steps, each in direction N, S, W, or E, starting at the origin, remaining in the upper half-plane and ending at height k (see the R. K. Guy reference, p. 5). Example: T(3,2)=6 because we have ENN, WNN, NEN, NWN, NNE and NNW. - Emeric Deutsch, Apr 15 2005
Triangle T(n,k), 0<=k<=n, read by rows given by T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 2*T(n-1,k) + T(n-1,k+1) for k>=1. - Philippe Deléham, Mar 30 2007
Number of (2n+1)-step walks from (0,0) to (2n+1,2k+1) and consisting of steps u=(1,1) and d=(1,-1) in which the path stays in the nonnegative quadrant. Examples: T(2,0)=5 because we have uuudd, uudud, uuddu, uduud, ududu; T(2,1)=4 because we have uuuud, uuudu, uuduu, uduuu; T(2,2)=1 because we have uuuuu. - Philippe Deléham, Apr 16 2007, Apr 18 2007
Triangle read by rows: T(n,k)=number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and two types of steps H=(1,0); example: T(3,1)=14 because we have UDU, UUD, 4 HHU paths, 4 HUH paths and 4 UHH paths. - Philippe Deléham, Sep 25 2007
This triangle belongs to the family of triangles defined by T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k>=1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0) -> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
With offset [1,1] this is the (ordinary) convolution triangle a(n,m) with o.g.f. of column m given by (c(x)-1)^m, where c(x) is the o.g.f. for Catalan numbers A000108. See the Riordan comment by Paul Barry.
T(n, k) is also the number of order-preserving full transformations (of an n-chain) with exactly k fixed points. - Abdullahi Umar, Oct 02 2008
T(n,k)/2^(2n+1) = coefficients of the maximally flat lowpass digital differentiator of the order N=2n+3. - Pavel Holoborodko (pavel(AT)holoborodko.com), Dec 19 2008
The signed triangle S(n,k) := (-1)^(n-k)*T(n,k) provides the transformation matrix between f(n,l) := L(2*l)*5^n*F(2*l)^(2*n+1) (F=Fibonacci numbers A000045, L=Lucas numbers A000032) and F(4*l*(k+1)), k = 0, ..., n, for each l>=0: f(n,l) = Sum_{k=0..n} S(n,k)*F(4*l*(k+1)), n>=0, l>=0. Proof: the o.g.f. of the l.h.s., G(l;x) := Sum_{n>=0} f(n,l)*x^n = F(4*l)/(1 - 5*F(2*l)^2*x) is shown to match the o.g.f. of the r.h.s.: after an interchange of the n- and k-summation, the Riordan property of S = (C(x)/x,C(x)) (compare with the above comments by Paul Barry), with C(x) := 1 - c(-x), with the o.g.f. c(x) of A000108 (Catalan numbers), is used, to obtain, after an index shift, first Sum_{k>=0} F(4*l*(k))*GS(k;x), with the o.g.f of column k of triangle S which is GS(k;x) := Sum_{n>=k} S(n,k)*x^n = C(x)^(k+1)/x. The result is GF(l;C(x))/x with the o.g.f. GF(l,x) := Sum_{k>=0} F(4*l*k)*x^k = x*F(4*l)/(1-L(4*l)*x+x^2) (see a comment on A049670, and A028412). If one uses then the identity L(4*n) - 5*F(2*n)^2 = 2 (in Koshy's book [reference under A065563] this is No. 15, p. 88, attributed to Lucas, 1876), the proof that one recovers the o.g.f. of the l.h.s. from above boils down to a trivial identity on the Catalan o.g.f., namely 1/c^2(-x) = 1 + 2*x - (x*c(-x))^2. - Wolfdieter Lang, Aug 27 2012
O.g.f. for row polynomials R(x) := Sum_{k=0..n} a(n,k)*x^k:
  ((1+x) - C(z))/(x - (1+x)^2*z) with C the o.g.f. of A000108 (Catalan numbers). From Riordan ((C(x)-1)/x,C(x)-1), compare with a Paul Barry comment above. This coincides with the o.g.f. given by Emeric Deutsch in the formula section. - Wolfdieter Lang, Nov 13 2012
The A-sequence for this Riordan triangle is [1,2,1] and the Z-sequence is [2,1]. See a W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 13 2012
From Wolfdieter Lang, Sep 20 2013: (Start)
T(n, k) = A053121(2*n+1, 2*k+1). T(n, k) appears in the formula for the (2*n+1)-th power of the algebraic number rho(N) := 2*cos(Pi/N) = R(N, 2) in terms of the even-indexed diagonal/side length ratios R(N, 2*(k+1)) = S(2*k+1, rho(N)) in the regular N-gon inscribed in the unit circle (length unit 1). S(n, x) are Chebyshev's S polynomials (see A049310): rho(N)^(2*n+1) = Sum_{k=0..n} T(n, k)*R(N, 2*(k+1)), n >= 0, identical in N >= 1. For a proof see the Sep 21 2013 comment under A053121. Note that this is the unreduced version if R(N, j) with j > delta(N), the degree of the algebraic number rho(N) (see A055034), appears. For the even powers of rho(n) see A039599. (End)
The tridiagonal Toeplitz production matrix P in the Example section corresponds to the unsigned Cartan matrix for the simple Lie algebra A_n as n tends to infinity (cf. Damianou ref. in A053122). -  Tom Copeland, Dec 11 2015 (revised Dec 28 2015)
T(n,k) is the number of pairs of non-intersecting walks of n steps, each in direction N or E, starting at the origin, and such that the end points of the two paths are separated by a horizontal distance of k. See Shapiro 1976. - Peter Bala, Apr 12 2017
Also the convolution triangle of the Catalan numbers A000108. - Peter Luschny, Oct 07 2022

			Triangle T(n,k) starts:
n\k     0      1      2      3      4     5    6    7   8  9 10
0:      1
1:      2      1
2:      5      4      1
3:     14     14      6      1
4:     42     48     27      8      1
5:    132    165    110     44     10     1
6:    429    572    429    208     65    12    1
7:   1430   2002   1638    910    350    90   14    1
8:   4862   7072   6188   3808   1700   544  119   16   1
9:  16796  25194  23256  15504   7752  2907  798  152  18  1
10: 58786  90440  87210  62016  33915 14364 4655 1120 189 20  1
... Reformatted and extended by _Wolfdieter Lang_, Nov 13 2012.
Production matrix begins:
2, 1
1, 2, 1
0, 1, 2, 1
0, 0, 1, 2, 1
0, 0, 0, 1, 2, 1
0, 0, 0, 0, 1, 2, 1
0, 0, 0, 0, 0, 1, 2, 1
0, 0, 0, 0, 0, 0, 1, 2, 1
- _Philippe Deléham_, Nov 07 2011
From _Wolfdieter Lang_, Nov 13 2012: (Start)
Recurrence: T(5,1) = 165 = 1*42 + 2*48 +1*27. The Riordan A-sequence is [1,2,1].
Recurrence from Riordan Z-sequence [2,1]: T(5,0) = 132 = 2*42 + 1*48. (End)
From _Wolfdieter Lang_, Sep 20 2013: (Start)
  Example for rho(N) = 2*cos(Pi/N) powers:
  n=2: rho(N)^5 = 5*R(N, 2) + 4*R(N, 4) + 1*R(N, 6) = 5*S(1, rho(N)) + 4*S(3, rho(N)) + 1*S(5, rho(N)), identical in N >= 1. For N=5 (the pentagon with only one distinct diagonal) the degree delta(5) = 2, hence R(5, 4) and R(5, 6) can be reduced, namely to R(5, 1) = 1 and R(5, 6) = -R(5,1) = -1, respectively. Thus rho(5)^5 = 5*R(N, 2) + 4*1  + 1*(-1) = 3 + 5*R(N, 2) = 3 + 5*rho(5), with the golden section rho(5). (End)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 796.
B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
Quang T. Bach and Jeffrey B. Remmel, Generating functions for descents over permutations which avoid sets of consecutive patterns, arXiv:1510.04319 [math.CO], 2015 (see p. 25).
Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion
Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, Counting prefixes of skew Dyck paths, J. Int. Seq., Vol. 24 (2021), Article 21.8.2.
Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
Paul Barry, Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers, arXiv:2011.10827 [math.CO], 2020.
B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 29.
Eduardo H. M. Brietzke, Generalization of an identity of Andrews, Fibonacci Quart. 44 (2006), no. 2, 166-171.
Eduardo H. M. Brietzke, Recurrence Relations for Sums of Binomial Coefficients and Some Generalizations, Journal of Integer Sequences, Vol. 27 (2024), Article 24.3.4.
F. Cai, Q.-H. Hou, Y. Sun, and A. L. B. Yang, Combinatorial identities related to 2x2 submatrices of recursive matrices, arXiv:1808.05736 [math.CO], 2018. See Table 1.1.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 15 Feb. 2013, pp. 1667-1677.
Xi Chen, H. Liang, and Y. Wang, Total positivity of recursive matrices, arXiv:1601.05645 [math.CO], 2016.
Xi Chen, H. Liang, and Y. Wang, Total positivity of recursive matrices, Linear Algebra and its Applications, Volume 471, Apr 15 2015, Pages 383-393.
Johann Cigler, Some elementary observations on Narayana polynomials and related topics, arXiv:1611.05252 [math.CO], 2016. See p. 7.
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin, and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]
Paul Drube, Generalized Path Pairs and Fuss-Catalan Triangles, arXiv:2007.01892 [math.CO], 2020. See Figure 4 p. 8.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See p. 19.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41, example page 32.
Peter M. Higgins, Combinatorial results for semigroups of order-preserving mappings, Math. Proc. Camb. Phil. Soc. 113 (1993), 281-296.
A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving full transformations, Semigroup Forum 72 (2006), 51-62.
Donatella Merlini and Renzo Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Mathematics 340.2 (2017): 160-174. See (1.1).
Pedro J. Miana, Hideyuki Ohtsuka, and Natalia Romero, Sums of powers of Catalan triangle numbers, arXiv:1602.04347 [math.NT], 2016 (see 2.4).
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Article 12.3.3, 2012. - From _N. J. A. Sloane_, Sep 16 2012
A. Nkwanta and A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.
L. W. Shapiro, W.-J. Woan, and S. Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.
L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]
Yidong Sun and Fei Ma, Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths, arXiv preprint arXiv:1305.2015 [math.CO], 2013.
Yidong Sun and Fei Ma, Four transformations on the Catalan triangle, arXiv preprint arXiv:1305.2017 [math.CO], 2013.
Yidong Sun and Fei Ma, Some new binomial sums related to the Catalan triangle, Electronic Journal of Combinatorics 21(1) (2014), #P1.33.
Paweł J. Szabłowski, Yet another way of calculating moments of the Kesten's distribution and its consequences, arXiv:2106.10461 [math.CO], 2021.
Charles Zhao-Chen Wang and Yi Wang, Total positivity of Catalan triangle, Discrete Math. 338 (2015), no. 4, 566--568. MR3300743.
W.-J. Woan, L. Shapiro, and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n-2}, Amer. Math. Monthly, 104 (1997), 926-931.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.

Mirror image of A050166. Row sums are A001700.

Cf. A000108, A008313, A039599, A183134, A094527, A033184, A035324, A053122, A172417.

/* As triangle: */ [[Binomial(2*n,n-k) - Binomial(2*n,n-k-2): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 22 2015

T:=(n,k)->binomial(2*n, n-k) - binomial(2*n, n-k-2); # N. J. A. Sloane, Aug 26 2013
# Uses function PMatrix from A357368. Adds row and column above and to the left.
PMatrix(10, n -> binomial(2*n, n) / (n + 1)); # Peter Luschny, Oct 07 2022

Flatten[Table[Binomial[2n, n-k] - Binomial[2n, n-k-2], {n,0,9}, {k,0,n}]] (* Jean-François Alcover, May 03 2011 *)

T(n,k)=binomial(2*n,n-k) - binomial(2*n,n-k-2) \\ Charles R Greathouse IV, Nov 07 2016

# Algorithm of L. Seidel (1877)
# Prints the first n rows of the triangle.
def A039598_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 1
    for i in range(2*n) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
        if b : print([D[z] for z in (1..h-1) ])
A039598_triangle(10)  # Peter Luschny, May 01 2012

Row n: C(2n, n-k) - C(2n, n-k-2).
a(n, k) = C(2n+1, n-k)*2*(k+1)/(n+k+2) = A050166(n, n-k) = a(n-1, k-1) + 2*a(n-1, k)+ a (n-1, k+1) [with a(0, 0) = 1 and a(n, k) = 0 if n<0 or nHenry Bottomley, Sep 24 2001
From Philippe Deléham, Feb 14 2004: (Start)
T(n, 0) = A000108(n+1), T(n, k) = 0 if n0, T(n, k) = Sum_{j=1..n} T(n-j, k-1)*A000108(j).
G.f. for column k: Sum_{n>=0} T(n, k)*x^n = x^k*C(x)^(2*k+2) where C(x) = Sum_{n>=0} A000108(n)*x^n is g.f. for Catalan numbers, A000108.
Sum_{k>=0} T(m, k)*T(n, k) = A000108(m+n+1). (End)
T(n, k) = A009766(n+k+1, n-k) = A033184(n+k+2, 2k+2). - Philippe Deléham, Feb 14 2004
Sum_{j>=0} T(k, j)*A039599(n-k, j) = A028364(n, k). - Philippe Deléham, Mar 04 2004
Antidiagonal Sum_{k=0..n} T(n-k, k) = A000957(n+3). - Gerald McGarvey, Jun 05 2005
The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super- and subdiagonals and [2,2,2,...] in the main diagonal. - Gary W. Adamson, Dec 17 2006
G.f.: G(t,x) = C^2/(1-txC^2), where C = (1-sqrt(1-4x))/(2x) is the Catalan function. From here G(-1,x)=C, i.e., the alternating row sums are the Catalan numbers (A000108). - Emeric Deutsch, Jan 20 2007
Sum_{k=0..n} T(n,k)*x^k = A000957(n+1), A000108(n), A000108(n+1), A001700(n), A049027(n+1), A076025(n+1), A076026(n+1) for x=-2,-1,0,1,2,3,4 respectively (see square array in A067345). - Philippe Deléham, Mar 21 2007, Nov 04 2011
Sum_{k=0..n} T(n,k)*(k+1) = 4^n. - Philippe Deléham, Mar 30 2007
Sum_{j>=0} T(n,j)*binomial(j,k) = A035324(n,k), A035324 with offset 0 (0 <= k <= n). - Philippe Deléham, Mar 30 2007
T(n,k) = A053121(2*n+1,2*k+1). - Philippe Deléham, Apr 16 2007, Apr 18 2007
T(n,k) = A039599(n,k) + A039599(n,k+1). - Philippe Deléham, Sep 11 2007
Sum_{k=0..n+1} T(n+1,k)*k^2 = A029760(n). - Philippe Deléham, Dec 16 2007
Sum_{k=0..n} T(n,k)*A059841(k) = A000984(n). - Philippe Deléham, Nov 12 2008
G.f.: 1/(1-xy-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction).
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A001700(n), A194723(n+1), A194724(n+1), A194725(n+1), A194726(n+1), A194727(n+1), A194728(n+1), A194729(n+1), A194730(n+1) for x = 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Nov 03 2011
From Peter Bala, Dec 21 2014: (Start)
This triangle factorizes in the Riordan group as ( C(x), x*C(x) ) * ( 1/(1 - x), x/(1 - x) ) = A033184 * A007318, where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for the Catalan numbers A000108.
Let U denote the lower unit triangular array with 1's on or below the main diagonal and zeros elsewhere. For k = 0,1,2,... define U(k) to be the lower unit triangular block array
/I_k 0\
\ 0  U/ having the k X k identity matrix I_k as the upper left block; in particular, U(0) = U. Then this array equals the bi-infinite product (...*U(2)*U(1)*U(0))*(U(0)*U(1)*U(2)*...). (End)
From Peter Bala, Jul 21 2015: (Start)
O.g.f. G(x,t) = (1/x) * series reversion of ( x/f(x,t) ), where f(x,t) = ( 1 + (1 + t)*x )^2/( 1 + t*x ).
1 + x*d/dx(G(x,t))/G(x,t) = 1 + (2 + t)*x + (6 + 4*t + t^2)*x^2 + ... is the o.g.f for A094527. (End)
Conjecture: Sum_{k=0..n} T(n,k)/(k+1)^2 = H(n+1)*A000108(n)*(2*n+1)/(n+1), where H(n+1) = Sum_{k=0..n} 1/(k+1). - Werner Schulte, Jul 23 2015
From Werner Schulte, Jul 25 2015: (Start)
Sum_{k=0..n} T(n,k)*(k+1)^2 = (2*n+1)*binomial(2*n,n). (A002457)
Sum_{k=0..n} T(n,k)*(k+1)^3 = 4^n*(3*n+2)/2.
Sum_{k=0..n} T(n,k)*(k+1)^4 = (2*n+1)^2*binomial(2*n,n).
Sum_{k=0..n} T(n,k)*(k+1)^5 = 4^n*(15*n^2+15*n+4)/4. (End)
The o.g.f. G(x,t) is such that G(x,t+1) is the o.g.f. for A035324, but with an offset of 0, and G(x,t-1) is the o.g.f. for A033184, again with an offset of 0. - Peter Bala, Sep 20 2015
Denote this lower triangular array by L; then L * transpose(L) is the Cholesky factorization of the Hankel matrix ( 1/(i+j)*binomial(2*i+2*j-2, i+j-1) )A172417%20read%20as%20a%20square%20array.%20See%20Chamberland,%20p.%201669.%20-%20_Peter%20Bala">i,j >= 1 = A172417 read as a square array. See Chamberland, p. 1669. - _Peter Bala, Oct 15 2023

Typo in one entry corrected by Philippe Deléham, Dec 16 2007

A129176 Irregular triangle read by rows: T(n,k) is the number of Dyck words of length 2n having k inversions (n >= 0, k >= 0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 3, 1, 1, 1, 2, 3, 5, 5, 7, 7, 6, 4, 1, 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1, 1, 1, 2, 3, 5, 7, 11, 13, 18, 22, 28, 32, 37, 40, 44, 43, 40, 35, 25, 15, 6, 1, 1, 1, 2, 3, 5, 7, 11, 15, 20, 26, 34, 42, 53, 63, 73, 85, 96, 106, 113, 118, 118, 115, 102, 86, 65, 41, 21, 7, 1

Offset: 0

Emeric Deutsch, Apr 11 2007

A Dyck word of length 2n is a word of n 0's and n 1's for which no initial segment contains more 1's than 0's.
Representing a Dyck word p of length 2n as a superdiagonal Dyck path p', the number of inversions of p is equal to the area between p' and the path that corresponds to the Dyck word 0^n 1^n.
Row n has 1+n(n-1)/2 terms. Row sums are the Catalan numbers (A000108). Alternating row sums for n>=1 are the Catalan numbers alternated with 0's (A097331). Sum(k*T(n,k),k>=0) = A029760(n-2).
This triangle is A129182 (area under Dyck paths), reflected and compressed (0's removed). Equivalently, A239927 rotated by Pi/2 clockwise and compressed.
This is also the number of Catalan paths of length n and area k. - N. J. A. Sloane, Nov 28 2011
From Alford Arnold, Jan 29 2008:
This triangle gives the partial sums of the following triangle A136624:
1
.1
....2...1
........2...3...3...1
............2...2...6...7...6...4...1
................2...2...4...8..12..15..17..14..10...5...1
etc.

			T(4,5) = 3 because we have 01010011, 01001101 and 00110101.
Triangle starts:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 1, 2, 1;
[4] 1, 1, 2, 3, 3, 3, 1;
[5] 1, 1, 2, 3, 5, 5, 7,  7,  6,  4,  1;
[6] 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1;
...

Alois P. Heinz, Rows n = 0..40, flattened
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
J. Furlinger and J. Hofbauer, q-Catalan numbers, J. Comb. Theory, A, 40, 248-264, 1985.
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Cf. A000108, A097331, A029760, A129182, A239927.
Cf. A136624, A136625.
Mirror image of A227543.

P[0]:=1: for n from 0 to 8 do
P[n+1]:=sort(expand(sum(t^((i+1)*(n-i))*P[i]*P[n-i],i=0..n))) od:
for n from 1 to 9 do seq(coeff(P[n],t,j),j=0..n*(n-1)/2) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y+1, t)*z^t+b(x-1, y-1, t+1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 10 2014

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, t]*z^t + b[x-1, y-1, t+1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)

P(x, n) =
{
    if ( n<=1, return(1) );
    return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
}
for (n=0, 10, print( Vecrev( P(x,n) ) ) ); \\ Joerg Arndt, Jan 23 2024

\\ faster with memoization:
N=11;
VP=vector(N+1);  VP[1] =VP[2] = 1;  \\ one-based; memoization
P(n) = VP[n+1];
for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
for (n=0, N, print( Vecrev( P(n) ) ) ); \\ Joerg Arndt, Jan 23 2024

from sage.combinat.q_analogues import qt_catalan_number
for n in (0..9): print(qt_catalan_number(n).substitute(q=1).coefficients())
# Peter Luschny, Mar 10 2020

The row generating polynomials P[n] = P[n](t) satisfy P[0] = 1 and

P[n+1] = Sum_{i=0..n} P[i] P[n-i] t^((i+1)*(n-i)).

A139262 Total number of two-element anti-chains over all ordered trees on n edges.

Original entry on oeis.org

0, 0, 1, 8, 47, 244, 1186, 5536, 25147, 112028, 491870, 2135440, 9188406, 39249768, 166656772, 704069248, 2961699667, 12412521388, 51854046982, 216013684528, 897632738722, 3721813363288, 15401045060572, 63616796642368, 262357557683422, 1080387930269464, 4443100381114156

Offset: 0

Lifoma Salaam, Apr 12 2008

nonn

From Miklos Bona, Mar 04 2009: (Start)
This is the same as the total number of inversions in all 132-avoiding permutations of length n by the well-known bijection between ordered trees on n edges and such permutations.
For example, there are five permutations of length three that avoid 132, namely, 123, 213, 231, 312, and 321. Their numbers of inversions are, respectively, 0,1,2,2, and 3, for a total of eight inversions.
(End)
Appears to be a shifted version of A029760. - R. J. Mathar, Mar 30 2014
a(n) is the number of total East steps below y = x-1 of all North-East paths from (0,0) to (n,n). Details can be found in Section 3.1 and Section 5 in Pan and Remmel's link. - Ran Pan, Feb 01 2016

			a(3) = 8 because there are 5 ordered trees on 3 edges and two of the trees have 2 two-element anti-chain each, one of the trees has three two element anti-chains, one of the trees has one two element anti-chain and the last tree does not have any two-element anti-chains. Hence in ordered trees on 3 edges there are a total of (2)(2)+1(3)+1(1) = 8 two element anti-chains.

Robert Israel, Table of n, a(n) for n = 0..1650
Miklós Bóna, Surprising Symmetries in Objects Counted by Catalan Numbers, Electronic J. Combin., 19 (2012), #P62, eq. (2).
Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
Sittipong Thamrongpairoj, Dowling Set Partitions, and Positional Marked Patterns, Ph. D. Dissertation, University of California-San Diego (2019).

Cf. A129182, A139263.

0, seq((n+1)*(2*n-1)!/(n!*(n-1)!) - 2^(2*n-1), n=1..30); # Robert Israel, Feb 02 2016

a[0] = 0; a[n_] := (n+1)(2n-1)!/(n! (n-1)!) - 2^(2n-1);
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 19 2018, from Maple *)

G.f.: (up to offset): A = x^2*(B^3)*(C^2), where B is the generating function for the central binomial coefficients and C is the generating function for the Catalan numbers. Thus A = x^2*(1/sqrt(1-4*x))^3*((1-sqrt(1-4*x))/2*x)^2.
2*a(n) = (n+1)*A000984(n) - 4^n. - J. M. Bergot, Feb 02 2013
Conjecture: n*(n-2)*a(n) +2*(-4*n^2+9*n-3)*a(n-1) +8*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Feb 03 2013
The above conjecture follows easily from the formula by J. M. Bergot. - Robert Israel, Feb 02 2016
a(n) = Sum_{k=0..n^2} (n^2-k)/2 * A129182(n,k). - Alois P. Heinz, Mar 31 2018

Terms beyond a(9) added by Joerg Arndt, Dec 30 2012

A038836 Convolution of Catalan numbers {1,2,5,14,...} with A002802 (5-fold convoluted central binomial coefficients).

Original entry on oeis.org

1, 12, 95, 624, 3682, 20264, 106203, 536840, 2639230, 12692360, 59957846, 279081152, 1282981380, 5835994768, 26305678739, 117635236344, 522394992358, 2305593653960, 10120007354562, 44201842781536, 192208416186716

Offset: 0

Wolfdieter Lang

Convolution of A038806(n+1), n >= 0, with A000984 (central binomial coefficients); also convolution of A029760 with A000302 (powers of 4).

Cf. A000108, A002802, A000302, A000984, A029760, A038806.

a(n) = binomial(n+5, 2)*binomial(2*(n+3), n+2)/6 - (n+3)*2^(2*n+3); G.f. c(x)^2/(1-4*x)^(5/2), where c(x) = g.f. for Catalan numbers A000108;

A041001 Convolution of A000108(n+1), n >= 0, (Catalan numbers) with A038845 (3-fold convolution of powers of 4).

Original entry on oeis.org

1, 14, 125, 906, 5810, 34364, 191901, 1026610, 5312230, 26767940, 131990066, 639210404, 3048892740, 14354652152, 66828135005, 308078809794, 1408022619806, 6385966846580, 28765327498278, 128777533131500

Offset: 0

Wolfdieter Lang

Also convolution of A038836 with A000984 (central binomial coefficients); also convolution of A001791(n+1), n >= 0, with A002802; also convolution of A008549(n+1), n >= 0, with A002697; also convolution of A029760 with A002457; also convolution of A038806(n+1), n >= 0, with A000302 (powers of 4).

a(n) = (n+3)*(3*(n+6)*2^(2*n+3)-(n+4)*binomial(2*n+7, n+3))/12; G.f. (c(x)^2)/(1-4*x)^3, where c(x) = g.f. for Catalan numbers.

A191309 Number of peaks at height >= 2 in all dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights).

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 8, 16, 47, 94, 244, 488, 1186, 2372, 5536, 11072, 25147, 50294, 112028, 224056, 491870, 983740, 2135440, 4270880, 9188406, 18376812, 39249768, 78499536, 166656772, 333313544, 704069248, 1408138496, 2961699667, 5923399334, 12412521388, 24825042776

Offset: 0

Emeric Deutsch, May 30 2011

nonn

Also number of valleys (i.e., DU's) in all dispersed Dyck paths of length n. Example: a(4)=1 because in HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD we have 0+0+0+0+1+0 = 1 valley.

Also number of doublerises (i.e., UU's) in all dispersed Dyck paths of length n. Example: a(4)=1 because in HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD we have 0+0+0+0+0+1 = 1 doublerise.

			a(4)=1 because in HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD we have 0+0+0+0+0+1 =1 peak at height >=2.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A029760, A191308.

q := sqrt(1-4*z^2): g := 2*z^2*(1-q)/(q*(1-2*z+q)^2): gser := series(g, z = 0, 40): seq(coeff(gser, z, n), n = 0 .. 35);

CoefficientList[Series[2*x^2*(1-Sqrt[1-4*x^2])/(Sqrt[1-4*x^2]*(1-2*x+ Sqrt[1-4*x^2])^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

x='x+O('x^50); concat([0,0,0,0], Vec(2*x^2*(1-sqrt(1-4*x^2))/(sqrt(1-4*x^2)*(1-2*x+ sqrt(1-4*x^2))^2))) \\ G. C. Greubel, Mar 26 2017

a(2*n+1) = 2*a(2*n).
a(2*n+4) = A029760(n).
G.f.: g = 2*z^2*(1-q)/(q*(1-2*z+q)^2), where q=sqrt(1-4*z^2).
a(n) ~ 2^(n-3/2)*sqrt(n)/sqrt(Pi) * (1-sqrt(2*Pi/n)). - Vaclav Kotesovec, Mar 20 2014
Conjecture: n*(n-4)*a(n) +(n^2-10*n+15)*a(n-1) +2*(-5*n^2+28*n-27)*a(n-2) -4*(n-3)*(n-8) *a(n-3) +24*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jun 14 2016

A343257 Triangle read by rows: T(n,k) is the number of n+2-sided polygons whose points lie on a circle and with the property that one makes k turns on itself, always in the same direction (right or left) while following its edges, 1 <= k <= ceiling(n/2).

Original entry on oeis.org

1, 1, 1, 1, 1, 8, 1, 29, 1, 1, 80, 47, 1, 193, 513, 1, 1, 432, 3338, 244, 1, 925, 16633, 7305, 1, 1, 1928, 70713, 103616, 1186, 1, 3953, 271441, 990289, 92145, 1, 1, 8024, 972548, 7438204, 2717321, 5536, 1, 16189, 3321009, 47629761, 47637225, 1076409, 1

Offset: 1

Ludovic Schwob, Apr 09 2021

Polygons that differ by rotation or reflection are counted separately.
The polygons considered here are those that can be drawn by connecting n+2 equally spaced points on a circle (possibly self-intersecting).
The number of turns a polygon makes on itself while following its edges is called the turning number. See the Wikipedia article for additional explanation. The condition that the turns are in the same direction means that all the internal angles are less than 180 degrees (stars are allowed, but figure of eights are not).

			Triangle begins:
     1;
     1;
     1,    1;
     1,    8;
     1,   29,    1;
     1,   80,   47;
     1,  193,  513,   1;

Ludovic Schwob, Illustration of T(6,k), 1<=k<=3
Wikipedia, Turning number

Row sums give A295264(n+1).

Cf. A029760, A030110, A342968.

B(n,m,x)={
  local(Cache=Map());
  my(recurse(k,p,q,b) = my(hk=[k,p,q,b], z); if(!mapisdefined(Cache, hk, &z),
  z = if(k==0, q>p && q>m, sum(j=1, n-(q-p)%n, my(r=(q+j)%n); if(!bittest(b,r), if(rAndrew Howroyd, May 15 2021

T(n,1)=1 and T(2*n-1,n)=1 for all n>=1: the only solutions are the polygons with respective Schläfli symbols {n+2} and {2*n+1/n}.
T(n,2) = A030110(n+1) for all n>=1.
T(2*n,n-1) = A029760(n-2) for all n>=2.

a(31)-a(49) from Andrew Howroyd, May 15 2021

A041005 Convolution of Catalan numbers A000108(n+1), n >= 0, with A020918.

Original entry on oeis.org

1, 16, 159, 1260, 8722, 55152, 326811, 1844084, 10015566, 52754624, 270976342, 1362986520, 6734927460, 32775704608, 157408497171, 747269225028, 3511471892470, 16351481223840, 75525932249922, 346305571781224

Offset: 0

Wolfdieter Lang

Also convolution of A001791(n+1), n >= 0, with A038845; also convolution of A008549(n+1), n >= 0, with A002802; also convolution of A029760 with A002697; also convolution of A038806(n+1), n >= 0, with A002457; also convolution of A038836 with A000302 (powers of 4); also convolution of A041001 with A000984 (central binomial coefficients).

a(n)=binomial(n+7, 3)*binomial(2*(n+4), n+2)/20 - (n+4)*(n+3)*4^(n+1); G.f. (c(x)^2)/(1-4*x)^(7/2), where c(x) = g.f. for Catalan numbers.

A143019 Infinite square array read by antidiagonals: a(q,n) is the coefficient of z^n in the series expansion of C(z)^q/(1-4z)^(3/2), where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function (q,n = 0,1,2,...).

Original entry on oeis.org

1, 1, 6, 1, 7, 30, 1, 8, 38, 140, 1, 9, 47, 187, 630, 1, 10, 57, 244, 874, 2772, 1, 11, 68, 312, 1186, 3958, 12012, 1, 12, 80, 392, 1578, 5536, 17548, 51480, 1, 13, 93, 485, 2063, 7599, 25147, 76627, 218790, 1, 14, 107, 592, 2655, 10254, 35401, 112028, 330818

Offset: 0

Emeric Deutsch, Jul 24 2008

a(q,n) = a(q-1,n) + a(q+1,n-1).

Row 0 is A002457; row 1 is A000531; row 2 is A029760; row 3 is A045720.

			Array starts:
  1, 6, 30, 140,  630, ...
  1, 7, 38, 187,  874, ...
  1, 8, 47, 244, 1186, ...
  1, 9, 57, 312, 1578, ...
  ...

Cf. A002457, A000531, A029760, A045720.

a:=proc(q,n) options operator, arrow: sum(4^i*binomial(2*n-2*i+q, n-i), i= 0.. n) end proc: aa:=proc(q,n) options operator, arrow: a(q-1,n-1) end proc: matrix(10,10,aa); # yields sequence in matrix form

a(q,n) = Sum_{i=0..n} 4^i*binomial(2n-2i+q, n-i).

cp's OEIS Frontend

A039598 Triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x). Sometimes called Catalan's triangle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A129176 Irregular triangle read by rows: T(n,k) is the number of Dyck words of length 2n having k inversions (n >= 0, k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

SageMath

Formula

A139262 Total number of two-element anti-chains over all ordered trees on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A038836 Convolution of Catalan numbers {1,2,5,14,...} with A002802 (5-fold convoluted central binomial coefficients).

Views

Author

Keywords

Comments

Crossrefs

Formula

A041001 Convolution of A000108(n+1), n >= 0, (Catalan numbers) with A038845 (3-fold convolution of powers of 4).

Views

Author

Keywords

Comments

Formula

A191309 Number of peaks at height >= 2 in all dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A343257 Triangle read by rows: T(n,k) is the number of n+2-sided polygons whose points lie on a circle and with the property that one makes k turns on itself, always in the same direction (right or left) while following its edges, 1 <= k <= ceiling(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs