OFFSET
0,2
COMMENTS
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
REFERENCES
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.
LINKS
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).
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.
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.
FORMULA
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
From Philippe Deléham, Feb 14 2004: (Start)
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)
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
Sum_{k=0..n+1} T(n+1,k)*k^2 = A029760(n). - Philippe Deléham, Dec 16 2007
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) )_i,j >= 1 = A172417 read as a square array. See Chamberland, p. 1669. - Peter Bala, Oct 15 2023
EXAMPLE
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)
MAPLE
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
MATHEMATICA
Flatten[Table[Binomial[2n, n-k] - Binomial[2n, n-k-2], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, May 03 2011 *)
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
EXTENSIONS
Typo in one entry corrected by Philippe Deléham, Dec 16 2007
STATUS
approved