A008315 Catalan triangle read by rows. Also triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

1, 1, 1, 1, 1, 2, 1, 3, 2, 1, 4, 5, 1, 5, 9, 5, 1, 6, 14, 14, 1, 7, 20, 28, 14, 1, 8, 27, 48, 42, 1, 9, 35, 75, 90, 42, 1, 10, 44, 110, 165, 132, 1, 11, 54, 154, 275, 297, 132, 1, 12, 65, 208, 429, 572, 429, 1, 13, 77, 273, 637, 1001, 1001, 429, 1, 14, 90, 350, 910, 1638, 2002, 1430, 1, 15, 104

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabf
• nice
• easy

Comments

There are several versions of a Catalan triangle: see A009766, A008315, A028364, A053121.

Number of standard tableaux of shape (n-k,k) (0<=k<=floor(n/2)). Example: T(4,1)=3 because in th top row we can have 124, 134, or 123 (but not 234). - Emeric Deutsch, May 23 2004

T(n,k) is the number of n-digit binary words (length n sequences on {0,1}) containing k 1's such that no initial segment of the sequence has more 1's than 0's. - Geoffrey Critzer, Jul 31 2009

T(n,k) is the number of dispersed Dyck paths (i.e. Motzkin paths with no (1,0) steps at positive heights) of length n and having k (1,1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), H=(1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. - Emeric Deutsch, May 30 2011

T(n,k) is the number of length n left factors of Dyck paths having k (1,-1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), we have UUUUD, UUUDU, UUDUU, and UDUUU. There is a simple bijection between length n left factors of Dyck paths and dispersed Dyck paths of length n, that takes D steps into D steps. - Emeric Deutsch, Jun 19 2011

Triangle, with zeros omitted, given by (1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1, ...) DELTA (0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011

T(n,k) are rational multiples of A055151(n,k). - Peter Luschny, Oct 16 2015

T(2*n,n) = Sum_{k>=0} T(n,k)^2 = A000108(n), T(2*n+1,n) = A000108(n+1). - Michael Somos, Jun 08 2020

Examples

			Triangle begins:
  1;
  1;
  1, 1;
  1, 2;
  1, 3,  2;
  1, 4,  5;
  1, 5,  9,  5;
  1, 6, 14, 14;
  1, 7, 20, 28, 14;
  ...
T(5,2) = 5 because there are 5 such sequences: {0, 0, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 1, 0}. - _Geoffrey Critzer_, Jul 31 2009
		

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.
• P. J. Larcombe, A question of proof..., Bull. Inst. Math. Applic. (IMA), 30, Nos. 3/4, 1994, 52-54.

Links

• T. D. Noe, Rows n=0..100 of triangle, 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].
• Tewodros Amdeberhan, Moa Apagodu, and Doron Zeilberger, Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle, arXiv:1507.07660 [math.CO], 2015.
• Nantel Bergeron, Kelvin Chan, Yohana Solomon, Farhad Soltani, and Mike Zabrocki, Quasisymmetric harmonics of the exterior algebra, arXiv:2206.02065 [math.CO], 2022.
• Chassidy Bozeman, Christine Cheng, Pamela E. Harris, Stephen Lasinis, and Shanise Walker, The Pinnacle Sets of a Graph, arXiv:2406.19562 [math.CO], 2024. See pp. 9-10.
• Suyoung Choi and Hanchul Park, A new graph invariant arises in toric topology, arXiv preprint arXiv:1210.3776 [math.AT], 2012.
• Suyuong Choi and Younghan Yoon, A decomposition of graph a-numbers, arXiv:2508.06855 [math.CO], 2025. See p. 14.
• C. Kenneth Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167.
• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
• Lin Jiu, Victor H. Moll, and C. Vignat, Identities for generalized Euler polynomials, arXiv:1401.8037 [math.PR], 2014.
• Nik Lygeros and Oliver Rozier, A new solution to the equation tau(rho) == 0 (mod p), J. Int. Seq. 13 (2010) # 10.7.4.
• Mustafa A. A. Obaid, S. Khalid Nauman, Wafaa M. Fakieh, and Claus Michael Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014 and J. Int. Seq. 18 (2015) 15.10.6.
• Alon Regev, The central component of a triangulation, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.1, p. 7.
• J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
• J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
• L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]
• Zheng Shi, Impurity entropy of junctions of multiple quantum wires, arXiv preprint arXiv:1602.00068 [cond-mat.str-el], 2016 (See Appendix A).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

T(2n, n) = A000108 (Catalan numbers), row sums = A001405 (central binomial coefficients).

This is also the positive half of the triangle in A008482. - Michael Somos

This is another reading (by shallow diagonals) of the triangle A009766, i.e. A008315[n] = A009766[A056536[n]].

Cf. A120730, A055151.

Programs

Haskell

a008315 n k = a008315_tabf !! n !! k
a008315_row n = a008315_tabf !! n
a008315_tabf = map reverse a008313_tabf
-- Reinhard Zumkeller, Nov 14 2013

Maple

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
    end:
T:= (n, k)-> b(n, n-2*k):
seq(seq(T(n, k), k=0..n/2), n=0..16);  # Alois P. Heinz, Oct 14 2022

Mathematica

Table[Binomial[k, i]*(k - 2 i + 1)/(k - i + 1), {k, 0, 20}, {i, 0, Floor[k/2]}] // Grid (* Geoffrey Critzer, Jul 31 2009 *)

PARI

{T(n, k) = if( k<0 || k>n\2, 0, if( n==0, 1, T(n-1, k-1) + T(n-1, k)))}; /* Michael Somos, Aug 17 1999 */

Formula

T(n, 0) = 1 if n >= 0; T(2*k, k) = T(2*k-1, k-1) if k>0; T(n, k) = T(n-1, k-1) + T(n-1, k) if k=1, 2, ..., floor(n/2). - Michael Somos, Aug 17 1999

T(n, k) = binomial(n, k) - binomial(n, k-1). - Michael Somos, Aug 17 1999

Rows of Catalan triangle A008313 read backwards. Sum_{k>=0} T(n, k)^2 = A000108(n); A000108 : Catalan numbers. - Philippe Deléham, Feb 15 2004

T(n,k) = C(n,k)*(n-2*k+1)/(n-k+1). - Geoffrey Critzer, Jul 31 2009

Sum_{k=0..n} T(n,k)*x^k = A000012(n), A001405(n), A126087(n), A128386(n), A121724(n), A128387(n), A132373(n), A132374(n), A132375(n), A121725(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Dec 12 2011

Extensions

Expanded description from Clark Kimberling, Jun 15 1997