0,2

T(n,k) = 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) = 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(S(n,k)*F(4*l*(k+1)),k=0..n), n>=0, l>=0. Proof: the o.g.f. of the l.h.s., G(l;x) := sum(f(n,l)*x^n, n=0..infty) = 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(F(4*l*(k))*GS(k;x), k= 0 .. infty), with the o.g.f of column k of triangle S which is GS(k;x) := sum(S(n,k)*x^n,n=k..infty) = C(x)^{k+1}/x. The result is GF(l;C(x))/x with the o.g.f. GF(l,x):= sum(F(4*l*k)*x^k, k=0..infty) = 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(a(n,k)*x^k,k=0..n):

  ((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(T(n, k)*R(N, 2*(k+1)), k = 0..n), 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) = 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

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.

Yang, Sheng-Liang, Yan-Ni Dong, and Tian-Xiao He. "Some matrix identities on colored Motzkin paths." Discrete Mathematics 340.12 (2017): 3081-3091.

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, Jeffrey B. Remmel, Generating functions for descents over permutations which avoid sets of consecutive patterns, arXiv:1510.04319 [math.CO], 2015 (see p. 25).

P. Bala, Notes on logarithmic differentiation, the binomial transform and series reversion

Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.

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.

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.

Xi Chen, H. Liang, Y. Wang, Total positivity of recursive matrices, arXiv:1601.05645 [math.CO], 2016.

Xi Chen, H. Liang, 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]

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

T.-X. He, 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, 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, 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

Charles Zhao-Chen Wang, 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.

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 n<k]. - Henry Bottomley, Sep 24 2001

T(n, 0) = A000108(n+1), T(n, k) = 0 if n<k; for k>0, 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). - Philippe Deléham, Feb 14 2004

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<=k<=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<=k<=n}T(n,k)*(k+1) = 4^n. - Philippe Deléham, Mar 30 2007

Sum_{j, 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<=k<=n+1}T(n+1,k)*k^2 = A029760(n). - Philippe Deléham, Dec 16 2007

Sum_{k, 0<=k<=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<=k<=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

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)

T:=(n, k)->binomial(2*n, n-k) - binomial(2*n, n-k-2); # N. J. A. Sloane, Aug 26 2013

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

(Sage) # 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

(MAGMA) /* 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

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

Mirror image of A050166. Row sums are A001700.

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

Sequence in context: A171488 A171651 A104710 * A128738 A193673 A126181

Adjacent sequences:  A039595 A039596 A039597 * A039599 A039600 A039601

nonn,tabl,easy,nice

N. J. A. Sloane

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

approved