cp's OEIS Frontend

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

%I A008315 #114 Aug 15 2025 10:28:28
%S A008315 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,
%T A008315 1,9,35,75,90,42,1,10,44,110,165,132,1,11,54,154,275,297,132,1,12,65,
%U A008315 208,429,572,429,1,13,77,273,637,1001,1001,429,1,14,90,350,910,1638,2002,1430,1,15,104
%N A008315 Catalan triangle read by rows. Also triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).
%C A008315 There are several versions of a Catalan triangle: see A009766, A008315, A028364, A053121.
%C A008315 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
%C A008315 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
%C A008315 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
%C A008315 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
%C A008315 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
%C A008315 T(n,k) are rational multiples of A055151(n,k). - _Peter Luschny_, Oct 16 2015
%C A008315 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
%D A008315 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.
%D A008315 P. J. Larcombe, A question of proof..., Bull. Inst. Math. Applic. (IMA), 30, Nos. 3/4, 1994, 52-54.
%H A008315 T. D. Noe, <a href="/A008315/b008315.txt">Rows n=0..100 of triangle, flattened</a>
%H A008315 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A008315 Tewodros Amdeberhan, Moa Apagodu, and Doron Zeilberger, <a href="http://arxiv.org/abs/1507.07660">Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle</a>, arXiv:1507.07660 [math.CO], 2015.
%H A008315 Nantel Bergeron, Kelvin Chan, Yohana Solomon, Farhad Soltani, and Mike Zabrocki, <a href="https://arxiv.org/abs/2206.02065">Quasisymmetric harmonics of the exterior algebra</a>, arXiv:2206.02065 [math.CO], 2022.
%H A008315 Chassidy Bozeman, Christine Cheng, Pamela E. Harris, Stephen Lasinis, and Shanise Walker, <a href="https://arxiv.org/abs/2406.19562">The Pinnacle Sets of a Graph</a>, arXiv:2406.19562 [math.CO], 2024. See pp. 9-10.
%H A008315 Suyoung Choi and Hanchul Park, <a href="http://arxiv.org/abs/1210.3776">A new graph invariant arises in toric topology</a>, arXiv preprint arXiv:1210.3776 [math.AT], 2012.
%H A008315 Suyuong Choi and Younghan Yoon, <a href="https://arxiv.org/abs/2508.06855">A decomposition of graph a-numbers</a>, arXiv:2508.06855 [math.CO], 2025. See p. 14.
%H A008315 C. Kenneth Fan, <a href="http://dx.doi.org/10.1090/S0894-0347-97-00222-1">Structure of a Hecke algebra quotient</a>, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167.
%H A008315 R. K. Guy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%H A008315 Lin Jiu, Victor H. Moll, and C. Vignat, <a href="https://arxiv.org/abs/1401.8037">Identities for generalized Euler polynomials</a>, arXiv:1401.8037 [math.PR], 2014.
%H A008315 Nik Lygeros and Oliver Rozier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Lygeros/lygeros5.html">A new solution to the equation tau(rho) == 0 (mod p)</a>, J. Int. Seq. 13 (2010) # 10.7.4.
%H A008315 Mustafa A. A. Obaid, S. Khalid Nauman, Wafaa M. Fakieh, and Claus Michael Ringel, <a href="http://www.math.uni-bielefeld.de/~ringel/opus/jeddah.pdf">The numbers of support-tilting modules for a Dynkin algebra</a>, 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Ringel/ringel22.html">J. Int. Seq. 18 (2015) 15.10.6</a>.
%H A008315 Alon Regev, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Regev/regev4.html">The central component of a triangulation</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.1, p. 7.
%H A008315 J. Riordan, <a href="http://www.jstor.org/stable/2005477">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222.
%H A008315 J. Riordan, <a href="/A003480/a003480.pdf">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
%H A008315 L. W. Shapiro, <a href="/A003517/a003517.pdf">A Catalan triangle</a>, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]
%H A008315 Zheng Shi, <a href="https://arxiv.org/abs/1602.00068">Impurity entropy of junctions of multiple quantum wires</a>, arXiv preprint arXiv:1602.00068 [cond-mat.str-el], 2016 (See Appendix A).
%H A008315 <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%F A008315 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
%F A008315 T(n, k) = binomial(n, k) - binomial(n, k-1). - _Michael Somos_, Aug 17 1999
%F A008315 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
%F A008315 T(n,k) = C(n,k)*(n-2*k+1)/(n-k+1). - _Geoffrey Critzer_, Jul 31 2009
%F A008315 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
%e A008315 Triangle begins:
%e A008315   1;
%e A008315   1;
%e A008315   1, 1;
%e A008315   1, 2;
%e A008315   1, 3,  2;
%e A008315   1, 4,  5;
%e A008315   1, 5,  9,  5;
%e A008315   1, 6, 14, 14;
%e A008315   1, 7, 20, 28, 14;
%e A008315   ...
%e A008315 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
%p A008315 b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
%p A008315      `if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
%p A008315     end:
%p A008315 T:= (n, k)-> b(n, n-2*k):
%p A008315 seq(seq(T(n, k), k=0..n/2), n=0..16);  # _Alois P. Heinz_, Oct 14 2022
%t A008315 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 *)
%o A008315 (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 */
%o A008315 (Haskell)
%o A008315 a008315 n k = a008315_tabf !! n !! k
%o A008315 a008315_row n = a008315_tabf !! n
%o A008315 a008315_tabf = map reverse a008313_tabf
%o A008315 -- _Reinhard Zumkeller_, Nov 14 2013
%Y A008315 T(2n, n) = A000108 (Catalan numbers), row sums = A001405 (central binomial coefficients).
%Y A008315 This is also the positive half of the triangle in A008482. - _Michael Somos_
%Y A008315 This is another reading (by shallow diagonals) of the triangle A009766, i.e. A008315[n] = A009766[A056536[n]].
%Y A008315 Cf. A120730, A055151.
%K A008315 nonn,tabf,nice,easy
%O A008315 0,6
%A A008315 _N. J. A. Sloane_
%E A008315 Expanded description from _Clark Kimberling_, Jun 15 1997