A008315 -id:A008315 - cp's OEIS frontend

A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j).

1, 1, 1, 1, 2, 2, 1, 3, 5, 5, 1, 4, 9, 14, 14, 1, 5, 14, 28, 42, 42, 1, 6, 20, 48, 90, 132, 132, 1, 7, 27, 75, 165, 297, 429, 429, 1, 8, 35, 110, 275, 572, 1001, 1430, 1430, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 4862, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934

Offset: 0

Wouter Meeussen

The entries in this triangle (in its many forms) are often called ballot numbers.
T(n,k) = number of standard tableaux of shape (n,k) (n > 0, 0 <= k <= n). Example: T(3,1) = 3 because we have 134/2, 124/3 and 123/4. - Emeric Deutsch, May 18 2004
T(n,k) is the number of full binary trees with n+1 internal nodes and jump-length k. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length. - Emeric Deutsch, Jan 18 2007
The k-th diagonal from the right (k=1, 2, ...) gives the sequence obtained by asking in how many ways can we toss a fair coin until we first get k more heads than tails. The k-th diagonal has formula k(2m+k-1)!/(m!(m+k)!) and g.f. (C(x))^k where C(x) is the generating function for the Catalan numbers, (1-sqrt(1-4*x))/(2*x). - Anthony C Robin, Jul 12 2007
T(n,k) is also the number of order-decreasing and order-preserving full transformations (of an n-element chain) of waist k (waist (alpha) = max(Im(alpha))). - Abdullahi Umar, Aug 25 2008
Formatted as an upper right triangle (see tables) a(c,r) is the number of different triangulated planar polygons with c+2 vertices, with triangle degree c-r+1 for the same vertex X (c=column number, r=row number, with c >= r >= 1). - Patrick Labarque, Jul 28 2010
The triangle sums, see A180662 for their definitions, link Catalan's triangle, its mirror is A033184, with several sequences, see crossrefs. - Johannes W. Meijer, Sep 22 2010
The m-th row of Catalan's triangle consists of the unique nonnegative differences of the form binomial(m+k,m)-binomial(m+k,m+1) with 0 <= k <= m (See Links). - R. J. Cano, Jul 22 2014
T(n,k) is also the number of nondecreasing parking functions of length n+1 whose maximum element is k+1. For example T(3,2) = 5 because we have (1,1,1,3), (1,1,2,3), (1,2,2,3), (1,1,3,3), (1,2,3,3). - Ran Pan, Nov 16 2015
T(n,k) is the number of Dyck paths from (0,0) to (n+2,n+2) which start with n-k+2 east steps and touch the diagonal y=x only on the last north step. - Felipe Rueda, Sep 18 2019
T(n-1,k) for k < n is number of well-formed strings of n parenthesis pairs with prefix of exactly n-k opening parenthesis; T(n,n) = T(n,n-1). - Hermann Stamm-Wilbrandt, May 02 2021

			Triangle begins in row n=0 with 0 <= k <= n:
  1;
  1, 1;
  1, 2,  2;
  1, 3,  5,   5;
  1, 4,  9,  14,  14;
  1, 5, 14,  28,  42,   42;
  1, 6, 20,  48,  90,  132,  132;
  1, 7, 27,  75, 165,  297,  429,  429;
  1, 8, 35, 110, 275,  572, 1001, 1430, 1430;
  1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 4862;

William Feller, Introduction to Probability Theory and its Applications, vol. I, ed. 2, chap. 3, sect. 1,2.
Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013).
D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Eq. 22, p. 451.
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.
M. Bellon, Query 5467, L'Intermédiaire des Mathématiciens, 4 (1925), 11; H. Ory, 4 (1925), 120. - N. J. A. Sloane, Mar 09 2022
Andrzej Proskurowski and Ekaputra Laiman, Fast enumeration, ranking, and unranking of binary trees. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982). Congr. Numer. 35 (1982), 401-413.MR0725898 (85a:68152).
M. Welsch, Note #371, L'Intermédiaire des Mathématiciens, 2 (1895), pp. 235-237. - N. J. A. Sloane, Mar 02 2022

T. D. Noe, Rows n = 0..100 of triangle, flattened
Erik Aas, Arvind Ayyer, Svante Linusson and Samu Potka, The exact phase diagram for a semipermeable TASEP with nonlocal boundary jumps, arXiv:1902.02019 [cond-mat.stat-mech], 2019.
Ron M. Adin, E. Bagno, and Y. Roichman, Block decomposition of permutations and Schur-positivity, arXiv:1611.06979 [math.CO], 2016-2017.
Kassie Archer, Abigail Bishop, Alexander Diaz-Lopez, Luis David Garcia Puente, Darren Glass, and Joel Louwsma, Arithmetical structures on bidents, arXiv:1903.01393 [math.CO], 2019.
J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906 [math.CO], 2007.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, Discrete Math., 308 (2008), 4660-4669.
Axel Bacher, Antonio Bernini, Luca Ferrari, Benjamin Gunby, Renzo Pinzani, and Julian West, The Dyck pattern poset Discrete Math. 321 (2014), 12--23. MR3154009.
D. F. Bailey, Counting arrangements of 1's and-1's, Mathematics Magazine, 69 (1996): 128-131. See table on p. 129.
Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, A methodology for plane tree enumeration, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). Discrete Math. 180 (1998), no. 1-3, 45--64. MR1603693 (98m:05090).
E. Barcucci and M. C. Verri, Some more properties of Catalan numbers, Discrete Math., 102 (1992), 229-237.
J.-L. Baril, C. Khalil, and V. Vajnovszki, Catalan and Schröder permutations sortable by two restricted stacks, arXiv:2004.01812 [cs.DM], 2020.
Paul Barry, Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms, J. Int. Seq. 14 (2011) # 11.2.2, example 3.
Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.
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, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Paul Barry and A. Hennessy, Meixner-Type Results for Riordan Arrays and Associated Integer Sequences, J. Int. Seq. 13 (2010) # 10.9.4, example 3.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
A. Bernini, L. Ferrari, R. Pinzani, and J. West, The Dyck pattern poset, arXiv:1303.3785 [math.CO], 2013.
N. Borie, Combinatorics of simple marked mesh patterns in 132-avoiding permutations, arXiv:1311.6292 [math.CO], 2013.
M. Bousquet-Mélou and M. Petkovsek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (2000), 51-75.
Jasper Bown, Peter Kagey, Alan Kappler, Michael E. Orrison, and Jayden Thadani, Preference-restricted parking functions, arXiv:2507.11701 [math.CO], 2025. See p. 11.
Benjamin Braun, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, and Carlos E. Valencia, Counting Arithmetical Structures on Paths and Cycles. arXiv:1701.06377 [math.CO], 2017.
E. H. M. Brietzke, An identity of Andrews and a new method for the Riordan array proof of combinatorial identities, Discrete Math., 308 (2008), 4246-4262.
S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
Hong Duc Bui, Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials, arXiv:2504.09615 [cs.CG], 2025. See p. 4.
Steve Butler, R. Graham, and C. H. Yan, Parking distributions on trees, European Journal of Combinatorics 65 (2017), 168-185.
R. J. Cano, Catalan's books
L. Carlitz, Sequences, paths, ballot numbers
Douglas M. Chen, On the Structure of Permutation Invariant Parking, arXiv:2311.15699 [math.CO], 2023. See p. 16.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, On some discrete statistics of parking functions, arXiv:2312.16786 [math.CO], 2023.
Italo J. Dejter, A new approach to the middle levels via a Catalan-number system of numeration, 2015.
Italo J. Dejter, A numeral system for the middle levels, preprint, 2014. [See Section 2. - _N. J. A. Sloane_, Apr 06 2014]
Italo J. Dejter, Dihedral-symmetry middle-levels problem via a Catalan system of numeration, preprint, 2015.
Italo J. Dejter, The role of restricted growth strings in the two middle levels of the Boolean lattice B_(2k+1), University of Puerto Rico, 2018.
Italo J. Dejter, Reinterpreting Mütze's Theorem via Natural Enumeration of Ordered Rooted Trees, arXiv:1911.02100 [math.CO], 2019.
Italo J. Dejter, A numeral system for the middle-levels graphs, Elec. J. Graph Theory and Applications (2021) Vol. 9, No. 1, 137-156. See p. 139.
B. Derrida, E. Domany, and D. Mukamel, An exact solution of a one-dimensional asymmetric exclusion model with open boundaries, J. Stat. Phys. 69, 1992, 667-687; eqs. (20), (21), p. 672. (Y_{N}(K) = A009766(N+1,K-1), 1 <= K <= N+1, N >=0 if alpha = 1 = beta).
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Filippo Disanto, Some Statistics on the Hypercubes of Catalan Permutations, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Classification of uniform flag triangulations of the Legendre polytope, arXiv:1901.07113 [math.CO], 2019.
R. Ehrenborg, S. Kitaev, and E. Steingrimsson, Number of cycles in the graph of 312-avoiding permutations, arXiv:1310.1520 [math.CO], 2013.
W. J. R. Eplett, A note about the Catalan triangle, Discrete Math. 25(1979), no. 3, 289--291. MR0534947 (80i:05007)
Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating Minimal Length Lattice Paths, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.
G. Feinberg and K.-H. Lee, Homogeneous representations of KLR-algebras and fully commutative elements, arXiv:1401.0845 [math.RT], 2014.
I. Fanti, A. Frosini, E. Grazzini, R. Pinzani, and S. Rinaldi, Characterization and enumeration of some classes of permutominoes, PU. M. A., Vol. 18 (2007), No. 3-4, pp. 265-290.
Dominique Foata and Guo-Niu Han, The doubloon polynomial triangle, Ram. J. 23 (2010), 107-126.
Dominique Foata and Guo-Niu Han, Doubloons and new q-tangent numbers, Quart. J. Math. 62 (2) (2011) 417-432.
H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.
C. A. Francisco, J. Mermin, and J. Schweig, Catalan numbers, binary trees, and pointed pseudotriangulations, preprint 2013; European Journal of Combinatorics, Volume 45, April 2015, Pages 85-96.
Shishuo Fu, Zhicong Lin, and Yaling Wang, A combinatorial bijection on di-sk trees, arXiv:2011.11302 [math.CO], 2020.
Ling Gao, Graph assembly for spider and tadpole graphs, Master's Thesis, Cal. State Poly. Univ. (2023). See p. 12.
Ira Gessel, Super ballot numbers.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Claude Godrèche and Jean-Marc Luck, On the first positive position of a random walker, arXiv:2501.17268 [cond-mat.stat-mech], 2025.
Niket Gowravaram, A Variation of the nil-Temperley-Lieb algebras of type A, Preprint, 2015.
J. M. Hammersley, An undergraduate exercise in manipulation, Math. Scientist, 14 (1989), 1-23.
J. M. Hammersley, An undergraduate exercise in manipulation, Math. Scientist, 14 (1989), 1-23. (Annotated scanned copy)
Pamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, and Per Wagenius, A Probabilistic Parking Process and Labeled IDLA, arXiv:2501.11718 [math.PR], 2025. See pp. 8, 28.
David He and Daniel Tubbenhauer, Tensor powers of representations of (diagram) monoids, arXiv:2508.04054 [math.RT], 2025. See p. 7.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
F. Hivert, J.-C. Novelli, and J.-Y. Thibon, The Algebra of Binary Search Trees, Theoretical Computer Science, 339 (2005), 129-165.
R. L. Hudson and Y. Pei, On a causal quantum stochastic double product integral related to Lévy area, Research Gate, 2015.
R. L. Hudson and Y. Pei, On a quantum causal stochastic double product integral related to Levy area, arXiv:1506.04294 [math-ph], 2015.
Brant Jones, Avoiding patterns and making the best choice, arXiv:1812.00963 [math.CO], 2018.
Cemil Karaçam and Alper Vural, Enumerating 2D and 3D lattice paths with arbitrary steps, Mathematica Bohemica, pp. 1-13 (2025). See p. 12.
Antii Karttunen, Some notes on Catalan's Triangle.
Lord C. Kavi and Michael W. Newman, Counting closed walks in infinite regular trees using Catalan and Borel's triangles, arXiv:2212.08795 [math.CO], 2022.
Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, arXiv:1706.07208 [math.CO], 2017.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146. [Annotated scanned copy]
A. Laradji and A. Umar, On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
Jeong-Yup Lee, Dong-il Lee, and Sungsoon Kim, Gröbner-Shirshov bases for Temperley-Lieb algebras of the complex reflection group of type G(d,1,n), arXiv:1808.06523 [math.RA], 2018.
Kyu-Hwan Lee and Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
Shao-Hua Liu, The operators F_i on permutations, 132-avoiding permutations and inversions, Discrete Math., 342 (2019), 2402-2414.
Jiaxi Lu and Yuanzhe Ding, A skeleton model to enumerate standard puzzle sequences, arXiv:2106.09471 [math.CO], 2021.
D. Merlini et al., Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math., 91 (1999), 197-213.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table I).
Andrew Misseldine, Counting Schur Rings over Cyclic Groups, arXiv:1508.03757 [math.RA], 2015.
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.
M. A. A. Obaid, S. K. Nauman, W. M. Fakieh, and C. M. Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014 and J. Int. Seq. 18 (2015) 15.10.6.
P. Pagacz and M. Wojtylak, On the spectral properties of a class of H-selfadjoint random matrices and the underlying combinatorics, arXiv:1310.2122 [math.PR], 2013.
R. Parviainen, Permutations, cycles and the pattern 2-13, arXiv:math/0607793 [math.CO], 2006.
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 261
Planet Math, Lattice Paths and ballot numbers.
L. Pudwell, Avoiding an Ordered Partition of Length 3, 2013.
C. M. Ringel, The Catalan combinatorics of the hereditary artin algebras, arXiv:1502.06553 [math.RT], 2015.
Gabriel Bravo Rios and Agustin Moreno Cañadas, Dyck Paths in Representation Theory of Algebras, National University of Colombia (2020).
A. Robertson, D. Saracino, and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.
T. Sillke, Catalan's numbers
Hermann Stamm-Wilbrandt, Visualization for all well-formed strings of 4 parenthesis pairs and relation to T(n,k).
R. A. Sulanke, Guessing, ballot numbers and refining Pascal's triangle
Yidong Sun, A simple bijection between binary trees and colored ternary trees, El. J. Combinat. 17 (2010) #N20
Paweł J. Szabłowski, Yet another way of calculating moments of the Kesten's distribution and its consequences, arXiv:2106.10461 [math.CO], 2021.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See pp. 9, 29.
Rafael Vazquez and M. Krstic, Boundary control of a singular reaction-diffusion equation on a disk, arXiv:1601.02010 [math.OC], 2016.
Luis Verde-Star, A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
Eric Weisstein's World of Mathematics, Catalan's Triangle
Eric Weisstein's World of Mathematics, Nonnegative Partial Sum
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 17.
Martha Yip, Rook Placements and Jordan Forms of Upper-Triangular Nilpotent Matrices, arXiv:1703.00057 [math.CO], 2017; The Electronic Journal of Combinatorics 25(1) (2018), #P1.68.

The following are all versions of (essentially) the same Catalan triangle: A009766, A008315, A028364, A030237, A047072, A053121, A059365, A062103, A099039, A106566, A130020, A140344.
Cf. A062745, A214292.
Sums of the shallow diagonals give A001405, central binomial coefficients: 1=1, 1=1, 1+1=2, 1+2=3, 1+3+2=6, 1+4+5=10, 1+5+9+5=20, ...
Row sums as well as the sums of the squares of the shallow diagonals give Catalan numbers (A000108).
Reflected version of A033184.
Diagonals give A000108, A000108, A000245, A002057, A000344, A003517, A000588, A003518, A003519, A001392, ...
Triangle sums (see the comments): A000108 (Row1), A000957 (Row2), A001405 (Kn11), A014495 (Kn12), A194124 (Kn13), A030238 (Kn21), A000984 (Kn4), A000958 (Fi2), A165407 (Ca1), A026726 (Ca4), A081696 (Ze2).

Flat(List([0..10],n->List([0..n],m->Binomial(n+m,n)*(n-m+1)/(n+1)))); # Muniru A Asiru, Feb 18 2018

a009766 n k = a009766_tabl !! n !! k
a009766_row n = a009766_tabl !! n
a009766_tabl = iterate (\row -> scanl1 (+) (row ++ [0])) [1]
-- Reinhard Zumkeller, Jul 12 2012

[[Binomial(n+k,n)*(n-k+1)/(n+1): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Mar 07 2019

A009766 := proc(n,k) binomial(n+k,n)*(n-k+1)/(n+1); end proc:
seq(seq(A009766(n,k), k=0..n), n=0..10); # R. J. Mathar, Dec 03 2010

Flatten[NestList[Append[Accumulate[#], Last[Accumulate[#]]] &, {1}, 9]] (* Birkas Gyorgy, May 19 2012 *)
T[n_, k_] := T[n, k] = Which[k == 0, 1, k>n, 0, True, T[n-1, k] + T[n, k-1] ]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 07 2016 *)

{T(n, k) = if( k<0 || k>n, 0, binomial(n+1+k, k) * (n+1-k) / (n+1+k) )}; /* Michael Somos, Oct 17 2006 */

b009766=(n1=0,n2=100)->{my(q=if(!n1,0,binomial(n1+1,2)));for(w=n1,n2,for(k=0,w,write("b009766.txt",1*q" "1*(binomial(w+k,w)-binomial(w+k,w+1)));q++))} \\ R. J. Cano, Jul 22 2014

from math import comb, isqrt
def A009766(n): return comb((a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))+(b:=n-comb(a+1,2)),b)*(a-b+1)//(a+1) # Chai Wah Wu, Nov 12 2024

@CachedFunction
def ballot(p,q):
    if p == 0 and q == 0: return 1
    if p < 0 or p > q: return 0
    S = ballot(p-2, q) + ballot(p, q-2)
    if q % 2 == 1: S += ballot(p-1, q-1)
    return S
A009766 = lambda n, k: ballot(2*k, 2*n)
for n in (0..7): [A009766(n, k) for k in (0..n)]  # Peter Luschny, Mar 05 2014

[[binomial(n+k,n)*(n-k+1)/(n+1) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Mar 07 2019

T(n, m) = binomial(n+m, n)*(n-m+1)/(n+1), 0 <= m <= n.
G.f. for column m: (x^m)*N(2; m-1, x)/(1-x)^(m+1), m >= 0, with the row polynomials from triangle A062991 and N(2; -1, x) := 1.
G.f.: C(t*x)/(1-x*C(t*x)) = 1 + (1+t)*x + (1+2*t+2*t^2)*x^2 + ..., where C(x) = (1-sqrt(1-4*x))/(2*x) is the Catalan function. - Emeric Deutsch, May 18 2004
Another version of triangle T(n, k) given by [1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 1, 1, 1, 1, 1, ...] = 1; 1, 0; 1, 1, 0; 1, 2, 2, 0; 1, 3, 5, 5, 0; 1, 4, 9, 14, 14, 0; ... where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 16 2005
O.g.f. (with offset 1) is the series reversion of x*(1+x*(1-t))/(1+x)^2 = x - x^2*(1+t) + x^3*(1+2*t) - x^4*(1+3*t) + ... . - Peter Bala, Jul 15 2012
Sum_{k=0..floor(n/2)} T(n-k+p-1, k+p-1) = A001405(n+2*p-2) - C(n+2*p-2, p-2), p >= 1. - Johannes W. Meijer, Oct 03 2013
Let A(x,t) denote the o.g.f. Then 1 + x*d/dx(A(x,t))/A(x,t) = 1 + (1 + t)*x + (1 + 2*t + 3*t^2)*x^2 + (1 + 3*t + 6*t^2 + 10*t^3)*x^3 + ... is the o.g.f. for A059481. - Peter Bala, Jul 21 2015
The n-th row polynomial equals the n-th degree Taylor polynomial of the function (1 - 2*x)/(1 - x)^(n+2) about 0. For example, for n = 4, (1 - 2*x)/(1 - x)^6 = 1 + 4*x + 9*x^2 + 14*x^3 + 14*x^4 + O(x^5). - Peter Bala, Feb 18 2018
T(n,k) = binomial(n + k + 1, k) - 2*binomial(n + k, k - 1), for 0 <= k <= n. - David Callan, Jun 15 2022

A053121 Catalan triangle (with 0's) read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 2, 0, 3, 0, 1, 0, 5, 0, 4, 0, 1, 5, 0, 9, 0, 5, 0, 1, 0, 14, 0, 14, 0, 6, 0, 1, 14, 0, 28, 0, 20, 0, 7, 0, 1, 0, 42, 0, 48, 0, 27, 0, 8, 0, 1, 42, 0, 90, 0, 75, 0, 35, 0, 9, 0, 1, 0, 132, 0, 165, 0, 110, 0, 44, 0, 10, 0, 1, 132, 0, 297, 0, 275, 0, 154, 0, 54, 0, 11, 0

Offset: 0

Wolfdieter Lang

Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).
Walks with a wall: triangle of number of n-step walks from (0,0) to (n,m) where each step goes from (a,b) to (a+1,b+1) or (a+1,b-1) and the path stays in the nonnegative quadrant.
T(n,m) is the number of left factors of Dyck paths of length n ending at height m. Example: T(4,2)=3 because we have UDUU, UUDU, and UUUD, where U=(1,1) and D=(1,-1). (This is basically a different formulation of the previous - walks with a wall - property.) - Emeric Deutsch, Jun 16 2011
"The Catalan triangle is formed in the same manner as Pascal's triangle, except that no number may appear on the left of the vertical bar." [Conway and Smith]
G.f. for row polynomials p(n,x) := Sum_{m=0..n} (a(n,m)*x^m): c(z^2)/(1-x*z*c(z^2)). Row sums (x=1): A001405 (central binomial).
In the language of the Shapiro et al. reference such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group. The g.f. Ginv(x) of the m=0 column of the inverse of a given Bell-matrix (here A049310) is obtained from its g.f. of the m=0 column (here G(x)=1/(1+x^2)) by Ginv(x)=(f^{(-1)}(x))/x, with f(x) := x*G(x) and f^{(-1)}is the compositional inverse function of f (here one finds, with Ginv(0)=1, c(x^2)). See the Shapiro et al. reference.
Number of involutions of {1,2,...,n} that avoid the patterns 132 and have exactly k fixed points. Example: T(4,2)=3 because we have 2134, 4231 and 3214. Number of involutions of {1,2,...,n} that avoid the patterns 321 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. Number of involutions of {1,2,...,n} that avoid the patterns 213 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1432 and 4231. - Emeric Deutsch, Oct 12 2006
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
Riordan array (c(x^2),xc(x^2)), where c(x) is the g.f. of Catalan numbers A000108. - Philippe Deléham, Nov 25 2007
A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. - Gary W. Adamson, Dec 28 2008
By columns without the zeros, n-th row = A000108 convolved with itself n times; equivalent to A = (1 + x + 2x^2 + 5x^3 + 14x^4 + ...), then n-th row = coefficients of A^(n+1). - Gary W. Adamson, May 13 2009
Triangle read by rows,product of A130595 and A064189 considered as infinite lower triangular arrays; A053121 = A130595*A064189 = B^(-1)*A097609*B where B = A007318. - Philippe Deléham, Dec 07 2009
From Mark Dols, Aug 17 2010: (Start)
As an upper right triangle, rows represent powers of 5-sqrt(24):
  5 - sqrt(24)^1 = 0.101020514...
  5 - sqrt(24)^2 = 0.010205144...
  5 - sqrt(24)^3 = 0.001030928...
(Divided by sqrt(96) these powers give a decimal representation of the columns of A007318, with 1/sqrt(96) being the middle column.) (End)
T(n,k) is the number of dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights) having k (1,0)-steps. Example: T(5,3)=4 because, denoting U=(1,1), D=(1,-1), H=(1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. - Emeric Deutsch, Jun 01 2011
Let S(N,x) denote the N-th Chebyshev S-polynomial in x (see A049310, cf. [W. Lang]). Then x^n = sum_{k=0..n} T(n,k)*S(k,x). - L. Edson Jeffery, Sep 06 2012
This triangle a(n,m) appears also in the (unreduced) formula for the powers rho(N)^n for the algebraic number over the rationals rho(N) = 2*cos(Pi/N) = R(N, 2), the smallest diagonal/side ratio R in the regular N-gon:
  rho(N)^n = sum(a(n,m)*R(N,m+1),m=0..n), n>=0, identical in N >= 1. R(N,j) = S(j-1, x=rho(N)) (Chebyshev S (A049310)). See a comment on this under A039599 (even powers) and A039598 (odd powers). Proof: see the Sep 06 2012 comment by L. Edson Jeffery, which follows from T(n,k) (called here a(n,k)) being the inverse of the Riordan triangle A049310. - Wolfdieter Lang, Sep 21 2013
The so-called A-sequence for this Riordan triangle of the Bell type (c(x^2), x*c(x^2)) (see comments above) is A(x) = 1 + x^2. This proves the recurrence given in the formula section by Henry Bottomley for a(n, m) = a(n-1, m-1) + a(n-1, m+1) for n>=1 and m>=1, with inputs. The Z-sequence for this Riordan triangle is Z(x) = x which proves the recurrence a(n,0) = a(n-1,1), n>=1, a(0,0) = 1. For A- and Z-sequences for Riordan triangles see the W. Lang link under A006232. - Wolfdieter Lang, Sep 22 2013
Rows of the triangle describe decompositions of tensor powers of the standard (2-dimensional) representation of the Lie algebra sl(2) into irreducibles. Thus a(n,m) is the multiplicity of the m-th ((m+1)-dimensional) irreducible representation in the n-th tensor power of the standard one. - Mamuka Jibladze, May 26 2015
The Riordan row polynomials p(n, x) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*p(n, x) = (E_x + 1)*Sum_{j=0..n-1} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)*p(n-1-j, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle a(n, m) this entails a recurrence for the sequence of column m, given in the formula section. - Wolfdieter Lang, Aug 11 2017
From Roger Ford, Jan 22 2018: (Start)
For row n, the nonzero values represent the odd components (loops) formed by n+1 nonintersecting arches above and below the x-axis with the following constraints:  The top has floor((n+3)/2) starting arches at position 1 and the next consecutive odd positions. All other starting top arches are in even positions. The bottom arches are a rainbow of arches.  If the component=1 then the arch configuration is a semimeander solution.
Examples: For row 3 {0, 2, 0, 1} there are 3 arch configurations: 2 arch configurations have a component=1; 1 has a component=3.  c=components, U=top arch starting in odd position, u=top arch starting in an even position, d=ending top arch:
.
  top UuUdUddd c=3   top UdUuUddd c=1     top UdUdUudd c=1
       /\                    /\
      //\\                  /  \
     //  \\                / /\ \                    /\
    //    \\              / /  \ \                  /  \
   ///\  /\\\        /\  / / /\ \ \        /\  /\  / /\ \
   \\\ \/ ///        \ \ \ \/ / / /        \ \ \ \/ / / /
    \\\  ///          \ \ \  / / /          \ \ \  / / /
     \\\///            \ \ \/ / /            \ \ \/ / /
      \\//              \ \  / /              \ \  / /
       \/                \ \/ /                \ \/ /
                          \  /                  \  /
                           \/                    \/
For row 4 {2, 0, 3, 0, 1} there are 6 arch configurations: 2 have a component=1; 3 have a component=3: 1 has a component=1. (End)

			Triangle a(n,m) begins:
  n\m  0   1   2   3   4   5   6  7  8  9 10 ...
  0:   1
  1:   0   1
  2:   1   0   1
  3:   0   2   0   1
  4:   2   0   3   0   1
  5:   0   5   0   4   0   1
  6:   5   0   9   0   5   0   1
  7:   0  14   0  14   0   6   0  1
  8:  14   0  28   0  20   0   7  0  1
  9:   0  42   0  48   0  27   0  8  0  1
  10: 42   0  90   0  75   0  35  0  9  0  1
  ... (Reformatted by _Wolfdieter Lang_, Sep 20 2013)
E.g., the fourth row corresponds to the polynomial p(3,x)= 2*x + x^3.
From _Paul Barry_, May 29 2009: (Start)
Production matrix is
  0, 1,
  1, 0, 1,
  0, 1, 0, 1,
  0, 0, 1, 0, 1,
  0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 0, 1, 0, 1,
  0, 0, 0, 0, 0, 0, 0, 1, 0, 1 (End)
Boas-Buck recurrence for column k = 2, n = 6: a(6, 2) = (3/4)*(0 + 2*a(4 ,2) + 0 + 6*a(2, 2)) = (3/4)*(2*3 + 6) = 9. - _Wolfdieter Lang_, Aug 11 2017

J. H. Conway and D. A. Smith, On Quaternions and Octonions, A K Peters, Ltd., Natick, MA, 2003. See p. 60. MR1957212 (2004a:17002)
A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened
I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps
Paul Barry, Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms, J. Int. Seq. 14 (2011) # 11.2.2, example 3.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Paul Barry and A. Hennessy, Meixner-Type Results for Riordan Arrays and Associated Integer Sequences, J. Int. Seq. 13 (2010) # 10.9.4, example 3.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
J. Cigler, Some q-analogues of Fibonacci, Lucas and Chebyshev polynomials with nice moments, 2013.
J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, 2013.
J. Cigler, Some notes on q-Gould polynomials, 2013.
Emeric Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 486 and 498).
J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014
D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986 (see |F_{l,p}| on page 114). - _N. J. A. Sloane_, Jan 29 2011
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.
W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.
Wolfdieter Lang, Chebyshev S-polynomials: ten applications.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Note 4, pp. 414-415.
MathOverflow, Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?
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.
Karim Ritter von Merkl, Computing colored Khovanov homology, arXiv:2505.03916 [math.QA], 2025. See p. 2.
Frank Ruskey and Mark Weston, Spherical Venn Diagrams with Involutory Isometries, Electronic Journal of Combinatorics, 18 (2011), #P191.
L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, The Riordan Group, Discrete Appl. Maths. 34 (1991) 229-239.
Yidong Sun and Luping Ma, Minors of a class of Riordan arrays related to weighted partial Motzkin paths. Eur. J. Comb. 39, 157-169 (2014).
Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes.
W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.
Index entries for sequences related to Chebyshev polynomials.

Cf. A008315, A049310, A000108, A001405 (row sums), A145973, A153585, A108786, A037952. Another version: A008313. A039598 and A039599 without zeros, and odd and even numbered rows.

Variant without zero-diagonals: A033184 and with rows reversed: A009766.

a053121 n k = a053121_tabl !! n !! k
a053121_row n = a053121_tabl !! n
a053121_tabl = iterate
   (\row -> zipWith (+) ([0] ++ row) (tail row ++ [0,0])) [1]
-- Reinhard Zumkeller, Feb 24 2012

T:=proc(n,k): if n+k mod 2 = 0 then (k+1)*binomial(n+1,(n-k)/2)/(n+1) else 0 fi end: for n from 0 to 13 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form; Emeric Deutsch, Oct 12 2006
F:=proc(l,p) if ((l-p) mod 2) = 1 then 0 else (p+1)*l!/( ( (l-p)/2 )! * ( (l+p)/2 +1)! ); fi; end;
r:=n->[seq( F(n,p),p=0..n)]; [seq(r(n),n=0..15)]; # N. J. A. Sloane, Jan 29 2011
A053121 := proc(n,k) option remember; `if`(k>n or k<0,0,`if`(n=k,1,
procname(n-1,k-1)+procname(n-1,k+1))) end proc:
seq(print(seq(A053121(n,k), k=0..n)),n=0..12); # Peter Luschny, May 01 2011

a[n_, m_] /; n < m || OddQ[n-m] = 0; a[n_, m_] = (m+1) Binomial[n+1, (n-m)/2]/(n+1); Flatten[Table[a[n, m], {n, 0, 12}, {m, 0, n}]] [[1 ;; 90]] (* Jean-François Alcover, May 18 2011 *)
T[0, 0] := 1; T[n_, k_]/;0<=k<=n := T[n, k] = T[n-1, k-1]+T[n-1, k+1]; T[n_, k_] := 0; Flatten@Table[T[n, k], {n, 0, 12}, {k, 0, n}] (* Oliver Seipel, Dec 31 2024 *)

T(n, m)=if(nCharles R Greathouse IV, Mar 09 2016

def A053121_triangle(dim):
    M = matrix(ZZ,dim,dim)
    for n in (0..dim-1): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1] + M[n-1,k+1]
    return M
A053121_triangle(13) # Peter Luschny, Sep 19 2012

a(n, m) := 0 if n

a(n, m) = (4*(n-1)*a(n-2, m) + 2*(m+1)*a(n-1, m-1))/(n+m+2), a(n, m)=0 if n

G.f. for m-th column: c(x^2)*(x*c(x^2))^m, where c(x) = g.f. for Catalan numbers A000108.

G.f.: G(t,z) = c(z^2)/(1 - t*z*c(z^2)), where c(z) = (1 - sqrt(1-4*z))/(2*z) is the g.f. for the Catalan numbers (A000108). - Emeric Deutsch, Jun 16 2011

a(n, m) = a(n-1, m-1) + a(n-1, m+1) if n > 0 and m >= 0, a(0, 0)=1, a(0, m)=0 if m > 0, a(n, m)=0 if m < 0. - Henry Bottomley, Jan 25 2001

Sum_{k>=0} T(m,k)^2 = A000108(m). - Paul D. Hanna, Apr 23 2005

Sum_{k>=0} T(m, k)*T(n, k) = 0 if m+n is odd; Sum_{k>=0} T(m, k)*T(n, k) = A000108((m+n)/2) if m+n is even. - Philippe Deléham, May 26 2005

T(n,k)=sum{i=0..n, (-1)^(n-i)*C(n,i)*sum{j=0..i, C(i,j)*(C(i-j,j+k)-C(i-j,j+k+2))}}; Column k has e.g.f. BesselI(k,2x)-BesselI(k+2,2x). - Paul Barry, Feb 16 2006

Sum_{k=0..n} T(n,k)*(k+1) = 2^n. - Philippe Deléham, Mar 22 2007

Sum_{j>=0} T(n,j)*binomial(j,k) = A054336(n,k). - Philippe Deléham, Mar 30 2007

T(2*n+1,2*k+1) = A039598(n,k), T(2*n,2*k) = A039599(n,k). - Philippe Deléham, Apr 16 2007

Sum_{k=0..n} T(n,k)^x = A000027(n+1), A001405(n), A000108(n), A003161(n), A129123(n) for x = 0,1,2,3,4 respectively. - Philippe Deléham, Nov 22 2009

Sum_{k=0..n} T(n,k)*x^k = A126930(n), A126120(n), A001405(n), A054341(n), A126931(n) for x = -1, 0, 1, 2, 3 respectively. - Philippe Deléham, Nov 28 2009

Sum_{k=0..n} T(n,k)*A000045(k+1) = A098615(n). - Philippe Deléham, Feb 03 2012

Recurrence for row polynomials C(n, x) := Sum_{m=0..n} a(n, m)*x^m = x*Sum_{k=0..n} Chat(k)*C(n-1-k, x), n >= 0, with C(-1, 1/x) = 1/x and Chat(k) = A000108(k/2) if n is even and 0 otherwise. From the o.g.f. of the row polynomials: G(z; x) := Sum_{n >= 0} C(n, x)*z^n = c(z^2)*(1 + x*z*G(z, x)), with the o.g.f. c of A000108. - Ahmet Zahid KÜÇÜK and Wolfdieter Lang, Aug 23 2015

The Boas-Buck recurrence (see a comment above) for the sequence of column m is: a(n, m) = ((m+1)/(n-m))*Sum_{j=0..n-1-m} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)* a(n-1-j, k), for n > m >= 0 and input a(m, m) = 1. - Wolfdieter Lang, Aug 11 2017

Sum_{m=1..n} a(n,m) = A037952(n). - R. J. Mathar, Sep 23 2021

Edited by N. J. A. Sloane, Jan 29 2011

A027306 a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2).

Original entry on oeis.org

1, 1, 3, 4, 11, 16, 42, 64, 163, 256, 638, 1024, 2510, 4096, 9908, 16384, 39203, 65536, 155382, 262144, 616666, 1048576, 2449868, 4194304, 9740686, 16777216, 38754732, 67108864, 154276028, 268435456, 614429672, 1073741824, 2448023843

Offset: 0

Clark Kimberling

Inverse binomial transform of A027914. Hankel transform (see A001906 for definition) is {1, 2, 3, 4, ..., n, ...}. - Philippe Deléham, Jul 21 2005
Number of walks of length n on a line that starts at the origin and ends at or above 0. - Benjamin Phillabaum, Mar 05 2011
Number of binary integers (i.e., with a leading 1 bit) of length n+1 which have a majority of 1-bits. E.g., for n+1=4: (1011, 1101, 1110, 1111) a(3)=4. - Toby Gottfried, Dec 11 2011
Number of distinct symmetric staircase walks connecting opposite corners of a square grid of side n > 1. - Christian Barrientos, Nov 25 2018
From Gus Wiseman, Aug 20 2021: (Start)
Also the number of integer compositions of n + 1 with alternating sum > 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A345917. For example, the a(0) = 1 through a(4) = 11 compositions are:
  (1)  (2)  (3)    (4)    (5)
            (21)   (31)   (32)
            (111)  (112)  (41)
                   (211)  (113)
                          (122)
                          (212)
                          (221)
                          (311)
                          (1121)
                          (2111)
                          (11111)
The following relate to these compositions:
- The unordered version is A027193.
- The complement is counted by A058622.
- The reverse unordered version is A086543.
- The version for alternating sum >= 0 is A116406.
- The version for alternating sum < 0 is A294175.
- Ranked by A345917. (End)
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 07 2022

			From _Gus Wiseman_, Aug 20 2021: (Start)
The a(0) = 1 through a(4) = 11 binary numbers with a majority of 1-bits (Gottfried's comment) are:
  1   11   101   1011   10011
           110   1101   10101
           111   1110   10110
                 1111   10111
                        11001
                        11010
                        11011
                        11100
                        11101
                        11110
                        11111
The version allowing an initial zero is A058622.
(End)

A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.6)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.
Zachary Hamaker and Eric Marberg, Atoms for signed permutations, arXiv:1802.09805 [math.CO], 2018.
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

a(n) = Sum{(k+1)T(n, m-k)}, 0<=k<=[ (n+1)/2 ], T given by A008315.
Column k=2 of A226873. - Alois P. Heinz, Jun 21 2013
Cf. A008949, A248574, A001405, A246437.
The even bisection is A000302.
The odd bisection appears to be A032443.
Cf. A000984, A001700, A001791, A008549, A011782, A088218, A097805, A163493, A182616, A345197.

List([0..35],n->Sum([0..Int(n/2)],k->Binomial(n,k))); # Muniru A Asiru, Nov 27 2018

a027306 n = a008949 n (n `div` 2)  -- Reinhard Zumkeller, Nov 14 2014

[2^(n-1)+(1+(-1)^n)/4*Binomial(n, n div 2): n in [0..40]]; // Vincenzo Librandi, Jun 19 2016

a:= proc(n) add(binomial(n, j), j=0..n/2) end:
seq(a(n), n=0..32); # Zerinvary Lajos, Mar 29 2009

Table[Sum[Binomial[n, k], {k, 0, Floor[n/2]}], {n, 1, 35}]
(* Second program: *)
a[0] = a[1] = 1; a[2] = 3; a[n_] := a[n] = (2(n-1)(2a[n-2] + a[n-1]) - 8(n-2) a[n-3])/n; Array[a, 33, 0] (* Jean-François Alcover, Sep 04 2016 *)

a(n)=if(n<0,0,(2^n+if(n%2,0,binomial(n, n/2)))/2)

a(n) = Sum_{k=0..floor(n/2)} binomial(n,k).
Odd terms are 2^(n-1). Also a(2n) - 2^(2n-1) is given by A001700. a(n) = 2^n + (n mod 2)*binomial(n, (n-1)/2).
E.g.f.: (exp(2x) + I_0(2x))/2.
O.g.f.: 2*x/(1-2*x)/(1+2*x-((1+2*x)*(1-2*x))^(1/2)). - Vladeta Jovovic, Apr 27 2003
a(n) = A008949(n, floor(n/2)); a(n) + a(n-1) = A248574(n), n > 0. - Reinhard Zumkeller, Nov 14 2014
From Peter Bala, Jul 21 2015: (Start)
a(n) = [x^n]( 2*x - 1/(1 - x) )^n.
O.g.f.: (1/2)*( 1/sqrt(1 - 4*x^2) + 1/(1 - 2*x) ).
Inverse binomial transform is (-1)^n*A246437(n).
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + ... is the o.g.f. for A001405. (End)
a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n-1,(2n+1-(-1)^n)/4 -k). - Anthony Browne, Jun 18 2016
D-finite with recurrence: n*a(n) + 2*(-n+1)*a(n-1) + 4*(-n+1)*a(n-2) + 8*(n-2)*a(n-3) = 0. - R. J. Mathar, Aug 09 2017

Better description from Robert G. Wilson v, Aug 30 2000 and from Yong Kong (ykong(AT)curagen.com), Dec 28 2000

A028364 Triangle T(n,m) = Sum_{k=0..m} Catalan(n-k)*Catalan(k).

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 5, 7, 9, 14, 14, 19, 23, 28, 42, 42, 56, 66, 76, 90, 132, 132, 174, 202, 227, 255, 297, 429, 429, 561, 645, 715, 785, 869, 1001, 1430, 1430, 1859, 2123, 2333, 2529, 2739, 3003, 3432, 4862, 4862, 6292, 7150, 7810, 8398, 8986, 9646, 10504, 11934, 16796

Offset: 0

Wouter Meeussen

There are several versions of a Catalan triangle: see A009766, A008315, A028364.
The subtriangle [1], [2, 3], [5, 7, 9], ..., namely T(N,M-1), for N >= 1, M=1..N, appears as one-point function in the totally asymmetric exclusion process for the parameters alpha=1=beta. See the Derrida et al. and Liggett references given under A067323, where these triangle entries are called T_{N,N+M-1} for the given alpha and beta values. See the row reversed triangle A067323.
Consider a Dyck path as a path with steps N=(0,1) and E=(1,0) from (0,0) to (n,n) that stays weakly above y=x. T(n,m) is the number of Dyck paths of semilength n+1 where the (m+1)st north step is followed by an east step. - Lara Pudwell, Apr 12 2023

			Triangle begins
   1;
   1,  2;
   2,  3,  5;
   5,  7,  9, 14;
  14, 19, 23, 28, 42;

Alois P. Heinz, Rows n = 0..140, flattened
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
G. Chatel and V. Pilaud, Cambrian Hopf Algebras, arXiv:1411.3704 [math.CO], 2014-2015.
A. Sapounakis et al., Ordered trees and the inorder transversal, Disc. Math., 306 (2006), 1732-1741.

Cf. A000108 (column 0 and main diagonal), A001700 (row sums), A065097 (T(2*n-1, n-1)), A201205 (central terms).

Cf. A067323, A009766, A039598, A039599, A028377, A028378, A028376.

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      expand(b(n-1, j)*`if`(i>n, x, 1)), j=1..i))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b((n+1)$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Nov 28 2015

t[n_, k_] = Sum[CatalanNumber[n-j]*CatalanNumber[j], {j, 0, k}]; Flatten[Table[t[n, k], {n, 0, 8}, {k, 0, n}]] (* Jean-François Alcover, Jul 22 2011 *)

T(n,k) = Sum_{j>=0} A039598(k,j)*A039599(n-k,j). - Philippe Deléham, Feb 18 2004
Sum_{k>=0} T(n,k) = A001700(n). T(n,k) = A067323(n,n-k), n >= k >= 0, otherwise 0. - Philippe Deléham, May 26 2005
G.f. for column sequences m >= 0: (-(c(m,x)-1)/x+c(m,x)*c(x))/x^m with the g.f. c(x) of A000108 (Catalan) and c(m,x):=sum(C(k)*x^k,k=0..m) with C(n):=A000108(n). - Wolfdieter Lang, Mar 24 2006
G.f. for column sequences m >= 0 (without leading zeros): c(x)*Sum_{k=0..m} C(m,k)*c(x)^k with the g.f. c(x) of A000108 (Catalan) and C(n,m) is the Catalan triangle A033184(n,m). - Wolfdieter Lang, Mar 24 2006
T(n,n) = T(n,k) + T(n,n-1-k) = A000108(n+1), n > 0, k = 0..floor((n+1)/2). - Yuchun Ji, Jan 09 2019
G.f. for triangle: Sum_{n>=0, m>=0} T(n, m)*x^n*y^m = (c(x)-c(xy))/(x(1-y)c(x)) with the g.f. c(x) of A000108 (Catalan). - Lara Pudwell, Apr 12 2023

A100100 Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 10, 6, 3, 1, 35, 20, 10, 4, 1, 126, 70, 35, 15, 5, 1, 462, 252, 126, 56, 21, 6, 1, 1716, 924, 462, 210, 84, 28, 7, 1, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1, 92378, 48620, 24310, 11440, 5005, 2002

Offset: 0

Paul Barry, Nov 08 2004

Sometimes called a Catalan triangle, although there are many other triangles that carry that name - see A009766, A008315, A028364, A033184, A053121, A059365, A062103.
Number of nodes of outdegree k in all ordered trees with n edges. Equivalently, number of ascents of length k in all Dyck paths of semilength n. Example: T(3,2) = 3 because the Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U = (1,1), D = (1,-1), the ascents of length 2 being shown between parentheses. - Emeric Deutsch, Nov 19 2006
Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A088218 and g(x) is the g.f. of A000108. - Philippe Deléham, Jan 23 2010
T(n,k) is the number of nonnegative paths of upsteps U = (1,1) and downsteps D = (1,-1) of length 2*n with k returns to  ground level, the horizontal line through the initial vertex. Example: T(2,1) = 2 counts UDUU, UUDD. Also, T(n,k) = number of these paths whose last descent has length k, that is, k downsteps follow the last upstep. Example: T(2,1) = 2 counts UUUD, UDUD. - David Callan, Nov 21 2011
Belongs to the hitting-time subgroup of the Riordan group. Multiplying this triangle by the square Pascal matrix gives A092392 read as a square array. See the example below. - Peter Bala, Nov 03 2015

			From _Paul Barry_, Mar 15 2010: (Start)
Triangle begins in row n=0 with columns 0<=k<=n as:
    1;
    1,   1;
    3,   2,   1;
   10,   6,   3,  1;
   35,  20,  10,  4,  1;
  126,  70,  35, 15,  5, 1;
  462, 252, 126, 56, 21, 6, 1;
Production matrix begins
  1, 1;
  2, 1, 1;
  3, 1, 1, 1;
  4, 1, 1, 1, 1;
  5, 1, 1, 1, 1, 1;
  6, 1, 1, 1, 1, 1, 1;
  7, 1, 1, 1, 1, 1, 1, 1;
(End)
A092392 as a square array = A100100 * square Pascal matrix:
/1   1  1  1 ...\   / 1          \/1 1  1  1 ...\
|2   3  4  5 ...|   | 1 1        ||1 2  3  4 ...|
|6  10 15 21 ...| = | 3 2 1      ||1 3  6 10 ...|
|20 35 56 84 ...|   |10 6 3 1    ||1 4 10 20 ...|
|70 ...         |   |35 ...      ||1 ...        |
- _Peter Bala_, Nov 03 2015

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
Peter Bala, Notes on logarithmic differentiation, the binomial transform and series reversion
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro, An algebraic structure for Faber polynomials, Lin. Alg. Applic. 433 (2010) 1170-1179.
Tian-Xiao He and Renzo Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), no. 12, 3962-3974.

Row sums are A000984. Equivalent to A092392, to which A088218 has been added as a first column. Columns include A088218, A000984, A001700, A001791, A002054, A002694. Diagonal sums are A100217. Matrix inverse is A100218.

Cf. A059481 (mirrored). Cf. A033184, A094527, A113955.

a100100 n k = a100100_tabl !! n !! n
a100100_row n = a100100_tabl !! n
a100100_tabl = [1] : f a092392_tabl where
   f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'
-- Reinhard Zumkeller, Jan 15 2014

/* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Nov 21 2018

A100100 := proc(n,k)
    binomial(2*n-k-1,n-1) ;
end proc:
seq(seq(A100100(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Feb 06 2015

Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* Vincenzo Librandi, Nov 21 2018 *)

T(n,k)=binomial(2*n-k-1,n-k) \\ Charles R Greathouse IV, Jan 16 2012

From Peter Bala, Sep 06 2015: (Start)
Matrix product A094527 * P^(-1) = A113955 * P^(-2), where P denotes Pascal's triangle A007318.
Essentially, the logarithmic derivative of A033184. (End)
Let column(k) = [T(n, k), n >= k], then the generating function for column(k) is (2/(sqrt(1-4*x)+1))^(k-1)/sqrt(1-4*x). - Peter Luschny, Mar 19 2021
O.g.f. row polynomials R(n, x) := Sum_{k=0..n} T(n, k)*x^k, i.e. o.g.f. of the triangle, G(z,x) = 1/((2 - c(z))*(1 - x*z*c(z))), with c the o.g.f. of A000108 (Catalan). See the Riordan coomment by Philippe Deléham above. - Wolfdieter Lang, Apr 06 2021

A055151 Triangular array of Motzkin polynomial coefficients.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 6, 2, 1, 10, 10, 1, 15, 30, 5, 1, 21, 70, 35, 1, 28, 140, 140, 14, 1, 36, 252, 420, 126, 1, 45, 420, 1050, 630, 42, 1, 55, 660, 2310, 2310, 462, 1, 66, 990, 4620, 6930, 2772, 132, 1, 78, 1430, 8580, 18018, 12012, 1716, 1, 91, 2002, 15015, 42042

Offset: 0

Michael Somos, Jun 14 2000

T(n,k) = number of Motzkin paths of length n with k up steps. T(n,k)=number of 0-1-2 trees with n edges and k+1 leaves, n>0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) E.g., T(4,1)=6 because we have UDHH, UHDH, UHHD, HHUD, HUHD, HUDH, where U=(1,1), D(1,-1), H(1,0). - Emeric Deutsch, Nov 30 2003
Coefficients in series reversion of x/(1+H*x+U*D*x^2) corresponding to Motzkin paths with H colors for H(1,0), U colors for U(1,1) and D colors for D(1,-1). - Paul Barry, May 16 2005
Eigenvector equals A119020, so that A119020(n) = Sum_{k=0..[n/2]} T(n,k)*A119020(k). - Paul D. Hanna, May 09 2006
Row reverse of A107131. - Peter Bala, May 07 2012
Also equals the number of 231-avoiding permutations of n+1 for which descents(w) = peaks(w) = k, where descents(w) is the number of positions i such that w[i]>w[i+1], and peaks(w) is the number of positions i such that w[i-1]w[i+1]. For example, T(4,1) = 6 because 13245, 12435, 14235, 12354, 12534, 15234 are the only 231-avoiding permutations of 5 elements with descents(w) = peaks(w) = 1. - Kyle Petersen, Aug 02 2013
Apparently, a refined irregular triangle related to this triangle (and A097610) is given in the Alexeev et al. link on p. 12. This entry's triangle is also related through Barry's comment to A125181 and A134264. The diagonals of this entry are the rows of A088617. - Tom Copeland, Jun 17 2015
The row length sequence of this irregular triangle is A008619(n) = 1 + floor(n/2). - Wolfdieter Lang, Aug 24 2015

			The irregular triangle T(n,k) begins:
n\k 0  1   2    3   4  5 ...
0:  1
1:  1
2:  1  1
3:  1  3
4:  1  6   2
5:  1 10  10
6:  1 15  30    5
7:  1 21  70   35
8:  1 28 140  140  14
9:  1 36 252  420 126
10: 1 45 420 1050 630 42
... reformatted. - _Wolfdieter Lang_, Aug 24 2015

Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press (2015), page 617, Corollary 10.8.2
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.

Alois P. Heinz, Rows n = 0..200, flattened
N. Alexeev, J. Andersen, R. Penner, and P. Zograf, Enumeration of chord diagrams on many intervals and their non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014.
Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017.
Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.
Paul W. Lapey and Aaron Williams, A Shift Gray Code for Fixed-Content Łukasiewicz Words, Williams College, 2022.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
E. Marberg, Actions and identities on set partitions, arXiv preprint arXiv:1107.4173 [math.CO], 2011-2012.
MathOverflow, Motzkin polynomials and enumeration of chord diagrams.
Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022. See p. 32.
A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
Claude Zeller and Robert Cordery, Light scattering as a Poisson process and first passage probability, arXiv:1906.11131 [cond-mat.stat-mech], 2019.

A107131 (row reversed), A080159 (with trailing zeros), A001006 = row sums, A000108(n) = T(2n, n), A001700(n) = T(2n+1, n), A119020 (eigenvector), A001263 (Narayana numbers), A089627 (gamma vectors of type B associahedra), A101280 (gamma vectors of type A permutohedra).
Cf. A125181, A134264, A088617, A161642, A258820, A003989, A008315, A091156, A011973, A097610, A126120.
Cf. A014531.

b:= proc(x, y) option remember;
      `if`(y>x or y<0, 0, `if`(x=0, 1, expand(
       b(x-1, y) +b(x-1, y+1) +b(x-1, y-1)*t)))
    end:
T:= n-> (p-> seq(coeff(p, t, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Feb 05 2014

m=(1-x-(1-2x+x^2-4x^2y)^(1/2))/(2x^2 y); Map[Select[#,#>0&]&, CoefficientList[ Series[m,{x,0,15}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 05 2014 *)
p[n_] := Hypergeometric2F1[(1-n)/2, -n/2, 2, 4 x]; Table[CoefficientList[p[n], x], {n, 0, 13}] // Flatten (* Peter Luschny, Jan 23 2018 *)

{T(n, k) = if( k<0 || 2*k>n, 0, n! / ((n-2*k)! * k! * (k+1)!))}

{T(n, k) = if( k<0 || 2*k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt((1 - x)^2 - 4*y*x^2 + x * O(x^n))), n), k))} /* Michael Somos, Feb 14 2006 */

{T(n, k) = n++; if( k<0 || 2*k>n, 0, polcoeff( polcoeff( serreverse( x / (1 + x + y*x^2) + x * O(x^n)), n), k))} /* Michael Somos, Feb 14 2006 */

T(n,k) = n!/((n-2k)! k! (k+1)!) = A007318(n, 2k)*A000108(k). - Henry Bottomley, Jan 31 2003
E.g.f. row polynomials R(n,y): exp(x)*BesselI(1, 2*x*sqrt(y))/(x*sqrt(y)). - Vladeta Jovovic, Aug 20 2003
G.f. row polynomials R(n,y): 2 / (1 - x + sqrt((1 - x)^2 - 4 *y * x^2)).
From Peter Bala, Oct 28 2008: (Start)
The rows of this triangle are the gamma vectors of the n-dimensional (type A) associahedra (Postnikov et al., p. 38). Cf. A089627 and A101280.
The row polynomials R(n,x) = Sum_{k = 0..n} T(n,k)*x^k begin R(0,x) = 1, R(1,x) = 1, R(2,x) = 1 + x, R(3,x) = 1 + 3*x. They are related to the Narayana polynomials N(n,x) := Sum_{k = 1..n} (1/n)*C(n,k)*C(n,k-1)*x^k through x*(1 + x)^n*R(n, x/(1 + x)^2) = N(n+1,x). For example, for n = 3, x*(1 + x)^3*(1 + 3*x/(1 + x)^2) = x + 6*x^2 + 6*x^3 + x^4, the 4th Narayana polynomial.
Recursion relation: (n + 2)*R(n,x) = (2*n + 1)*R(n-1,x) - (n - 1)*(1 - 4*x)*R(n-2,x), R(0,x) = 1, R(1,x) = 1. (End)
G.f.: M(x,y) satisfies: M(x,y)= 1 + x M(x,y) + y*x^2*M(x,y)^2. - Geoffrey Critzer, Feb 05 2014
T(n,k) = A161642(n,k)*A258820(n,k) = (binomial(n,k)/A003989(n+1, k+1))* A258820(n,k). - Tom Copeland, Jun 18 2015
Let T(n,k;q) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],q) then T(n,k;0) = A055151(n,k), T(n,k;1) = A008315(n,k) and T(n,k;-1) = A091156(n,k). - Peter Luschny, Oct 16 2015
From Tom Copeland, Jan 21 2016: (Start)
Reversed rows of A107131 are rows of this entry, and the diagonals of A107131 are the columns of this entry. The diagonals of this entry are the rows of A088617. The antidiagonals (bottom to top) of A088617 are the rows of this entry.
O.g.f.: [1-x-sqrt[(1-x)^2-4tx^2]]/(2tx^2), from the relation to A107131.
Re-indexed and signed, this triangle gives the row polynomials of the compositional inverse of the shifted o.g.f. for the Fibonacci polynomials of A011973, x / [1-x-tx^2] = x + x^2 + (1+t) x^3 + (1+2t) x^4 + ... . (End)
Row polynomials are P(n,x) = (1 + b.y)^n = Sum{k=0 to n} binomial(n,k) b(k) y^k = y^n M(n,1/y), where b(k) = A126120(k), y = sqrt(x), and M(n,y) are the Motzkin polynomials of A097610. - Tom Copeland, Jan 29 2016
Coefficients of the polynomials p(n,x) = hypergeom([(1-n)/2, -n/2], [2], 4x). - Peter Luschny, Jan 23 2018
Sum_{k=1..floor(n/2)} k * T(n,k) = A014531(n-1) for n>1. - Alois P. Heinz, Mar 29 2020

A128099 Triangle read by rows: T(n,k) is the number of ways to tile a 3 X n rectangle with k pieces of 2 X 2 tiles and 3n-4k pieces of 1 X 1 tiles (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 6, 4, 1, 8, 12, 1, 10, 24, 8, 1, 12, 40, 32, 1, 14, 60, 80, 16, 1, 16, 84, 160, 80, 1, 18, 112, 280, 240, 32, 1, 20, 144, 448, 560, 192, 1, 22, 180, 672, 1120, 672, 64, 1, 24, 220, 960, 2016, 1792, 448, 1, 26, 264, 1320, 3360, 4032, 1792, 128, 1, 28

Offset: 0

Emeric Deutsch, Feb 18 2007

Row sums are the Jacobsthal numbers (A001045).
Apparently, T(n,k)/2^n equals the probability P that n will occur as a partial sum in a randomly-generated infinite sequence of 1s and 2s with n compositions (ordered partitions) into (n-2k) 1s and k 2s. Example: T(6,2)=24; P = 3/8 (24/2^6) that 6 will occur as a partial sum in the sequence with 2 (6-2*2) 1s and 2 2s. - Bob Selcoe, Jul 06 2013
From Johannes W. Meijer, Aug 28 2013: (Start)
The antidiagonal sums are A077949 and the backwards antidiagonal sums are A052947.
Moving the terms in each column of this triangle, see the example, upwards to row 0 gives the Pell-Jacobsthal triangle A013609 as a square array. (End)
The numbers in rows of the triangle are along "first layer" skew diagonals pointing top-right in center-justified triangle given in A013609 ((1+2*x)^n) and along (first layer) skew diagonals pointing top-left in center-justified triangle given in A038207 ((2+x)^n), see links. - Zagros Lalo, Jul 31 2018
If s(n) is the row sum at n, then the ratio s(n)/s(n-1) is approximately 2.000..., when n approaches infinity. - Zagros Lalo, Jul 31 2018
It appears that the rows of this array are the coefficients of the Jacobsthal polynomials (see MathWorld link). - Michel Marcus, Jun 15 2019

			Triangle starts:
  1;
  1;
  1,  2;
  1,  4;
  1,  6,  4;
  1,  8, 12;
  1, 10, 24,  8;
  1, 12, 40, 32;

Shara Lalo and Zagros Lalo, Polynomial Expansion Theorems and Number Triangles, Zana Publishing, 2018, ISBN: 978-1-9995914-0-3, pp. 80-83, 357-358

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Intrinsic Properties of a Non-Symmetric Number Triangle, J. Int. Seq., Vol. 26 (2023), Article 23.4.8.
Richard Fors, Independence Complexes of Certain Families of Graphs, Master's thesis in Mathematics at KTH, presented Aug 19 2011.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares arXiv:1609.03964 [math.CO] (2016).
Zagros Lalo, First layer skew diagonals in center-justified triangle of coefficients in expansion of (1 + 2x)^n
Zagros Lalo, First layer skew diagonals in center-justified triangle of coefficients in expansion of (2 + x)^n
Eric Weisstein's World of Mathematics, Jacobsthal Polynomial

Cf. (Triangle sums) A001045, A095977, A077949, A052947, A113726, A052942, A077909.
Cf. (Similar triangles) A008315, A011973, A102541.
Cf. A013609, A038207
Cf. A207538

T := proc(n,k) if k<=n/2 then 2^k*binomial(n-k,k) else 0 fi end: for n from 0 to 16 do seq(T(n,k),k=0..floor(n/2)) od; # yields sequence in triangular form
T := proc(n, k) option remember: if k<0 or k > floor(n/2) then return(0) fi: if k = 0 then return(1) fi: 2*procname(n-2, k-1) + procname(n-1, k): end: seq(seq(T(n, k), k=0..floor(n/2)), n=0..13); # Johannes W. Meijer, Aug 28 2013

Table[2^k*Binomial[n - k, k] , {n,0,25}, {k,0,Floor[n/2]}] // Flatten  (* G. C. Greubel, Dec 28 2016 *)
t[0, 0] = 1; t[n_, k_] := t[n, k] = If[n < 0 || k < 0, 0, t[n - 1, k] + 2 t[n - 2, k - 1]]; Table[t[n, k], {n, 0, 15}, {k, 0, Floor[n/2]}] // Flatten (* Zagros Lalo, Jul 31 2018 *)

T(n, k) = 2^k*binomial(n-k,k) = 2^k*A011973(n,k).
G.f.: 1/(1-z-2*t*z^2).
Sum_{k=0..floor(n/2)} k*T(n,k) = A095977(n-1).
From Johannes W. Meijer, Aug 28 2013: (Start)
T(n, k) = 2*T(n-2, k-1) + T(n-1, k) with T(n, 0) = 1 and T(n, k) = 0 for k < 0 and k > floor(n/2).
T(n, k) = A013609(n-k, k), n >= 0 and 0 <= k <= floor(n/2). (End)

A003161 A binomial coefficient sum.

Original entry on oeis.org

1, 1, 2, 9, 36, 190, 980, 5705, 33040, 204876, 1268568, 8209278, 53105976, 354331692, 2364239592, 16140234825, 110206067400, 765868074400, 5323547715200, 37525317999884, 264576141331216, 1886768082651816, 13458185494436592, 96906387191038334, 697931136204820336

Offset: 0

N. J. A. Sloane

The number of triples of standard tableaux of the same shape of height less than or equal to 2. - Mike Zabrocki, Mar 29 2007
From Peter Bala, Mar 20 2023: (Start)
For r a positive integer define S(r,n) = Sum_{k = 0..floor(n/2)} ( binomial(n,k) - binomial(n,k-1) )^r. The present sequence is {S(3,n)}. For other cases see A361887 ({S(5,n)}) and A361890 ({S(7,n)}).
Gould (1974) proposed the problem of showing that S(3,n) was always divisible by S(1,n). See A183069 for {S(3,n)/S(1,n)}. In fact, calculation suggests that if r is odd then S(r,n) is always divisible by S(1,n).
Conjecture: Let b(n) = a(2*n-1). Then the supercongruence b(n*p^k) == b(n*p^(k-1)) (mod p^(3*k)) holds for positive integers n and k and all primes p >= 5. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1116
F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.
H. W. Gould, Problem E2384, Amer. Math. Monthly, 81 (1974), 170-171.

Cf. A003162, A008315.
Cf. A001405, A000108, A129123, A183069.
Column k=3 of A357824.
Cf. A361887, A361890.

ogf := ((8*x-1)*(8*x+1)*hypergeom([1/4, 1/4],[1],64*x^2)^2/(x+1)-3*Int((16*x-5)*hypergeom([1/4, 1/4],[1],64*x^2)^2/(x+1)^2,x)+1)/(16*x);
series(ogf,x=0,30); # Mark van Hoeij, May 06 2013

Table[Sum[(Binomial[n, k]-Binomial[n, k-1])^3,{k,0,Floor[n/2]}],{n,0,20}] (* Vaclav Kotesovec, Mar 06 2014 *)

a(n)=sum(k=0,n\2, (binomial(n,k)-binomial(n,k-1))^3) /* Michael Somos, Jun 02 2005 */

a(n) = Sum_{k=0..n} A120730(n,k)^3. - Philippe Deléham, Oct 18 2008
G.f.: hypergeometric expression with an anti-derivative, see Maple program. - Mark van Hoeij, May 06 2013
Recurrence: n*(n+1)^3*(7*n^2 - 14*n + 3)*a(n) = - n*(7*n^5 - 112*n^4 + 206*n^3 + 8*n^2 - 125*n + 48)*a(n-1) + 16*(n-1)*(28*n^5 - 133*n^4 + 194*n^3 - 33*n^2 - 120*n + 61)*a(n-2) + 64*(n-2)^3*(n-1)*(7*n^2 - 4)*a(n-3). - Vaclav Kotesovec, Mar 06 2014
a(n) ~ 2^(3*n+9/2) / (9 * Pi^(3/2) * n^(5/2)). - Vaclav Kotesovec, Mar 06 2014
a(n) = Sum_{j=0..floor(n/2)} A008315(n,j)^3. - Alois P. Heinz, Oct 17 2022

A008313 Triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

This is another reading (by shallow diagonals) of the triangle A009766; rows of Catalan triangle A008315 read backwards. - Philippe Deléham, Feb 15 2004

"The Catalan triangle is formed in the same manner as Pascal's triangle, except that no number may appear on the left of the vertical bar." [Conway and Smith]

			.|...1
.|.......1
.|...1.......1
.|.......2.......1
.|...2.......3.......1
.|.......5.......4.......1
.|...5.......9.......5.......1
.|......14......14.......6.......1
.|..14......28......20.......7.......1
.|......42......48......27.......8.......1

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.
J. H. Conway and D. A. Smith, On Quaternions and Octonions, A K Peters, Ltd., Natick, MA, 2003. See p. 60. MR1957212 (2004a:17002)
P. J. Larcombe, A question of proof..., Bull. Inst. Math. Applic. (IMA), 30, Nos. 3/4, 1994, 52-54.

Reinhard Zumkeller, Rows n=0..150 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].
I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015-2018.
Tom Halverson, Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
Vaughan F. R. Jones, The Jones Polynomial, 18 August 2005, see the diagram on page 7. - Paul Curtz, Jun 22 2011
P. Mongelli, Kazhdan-Lusztig polynomials of Boolean elements, arXiv preprint arXiv:1111.2945 [math.CO], 2011.
Index entries for sequences related to Chebyshev polynomials.

Cf. A039598, A039599. A053121 is essentially the same triangle.

Row sums = A001405 (central binomial coefficients).

a008313 n k = a008313_tabf !! n !! k
a008313_row n = a008313_tabf !! n
a008313_tabf = map (filter (> 0)) a053121_tabl
-- Reinhard Zumkeller, Feb 24 2012

T := proc(n, k): if n=0 then 1 else binomial(n-1, floor(n/2 )-k) -binomial(n-1, floor(n/2) -k-2) fi: end: seq(seq(T(n, k), k = 0..floor(n/2)), n = 0..14); # Johannes W. Meijer, Jul 10 2011, revised Nov 22 2012

t[n_, k_] /; n < k || OddQ[n - k] = 0; t[n_, k_] := (k+1)*Binomial[n+1, (n-k)/2]/(n+1); Flatten[ Table[ t[n, k], {n, 0, 15}, {k, Mod[n, 2], n + Mod[n, 2], 2}]] (* Jean-François Alcover, Jan 12 2012 *)

{T(n, k) = if( k<0 || 2*k>n, 0, polcoeff((1 - x) * (1 + x)^n, n\2 - k))}; /* Michael Somos, May 28 2005 */

T(n, k) = binomial(n-1, n\2-k)-binomial(n-1, n\2-k-2);
for(n=0, 14, for(k=0, n\2, print1(T(n,k),", "))); \\ Seiichi Manyama, Mar 24 2025

# Algorithm of L. Seidel (1877)
# Prints the first n rows of the triangle.
def A008313_triangle(n) :
    D = [0]*((n+5)//2); D[1] = 1
    b = True; h = 1
    for i in range(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
        print([D[z] for z in (1..h-1)])
A008313_triangle(13) # Peter Luschny, May 01 2012

Row n: C(n-1, [n/2]-k) - C(n-1, [n/2]-k-2) for k=0, 1, ..., n.

Sum_{k>=0} T(n, k)^2 = A000108(n); A000108: Catalan numbers. - Philippe Deléham, Feb 14 2004

Previous Showing 11-20 of 32 results. Next

cp's OEIS Frontend

A049280 Essentially same as A008315.

Views

Author

Keywords

A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Sage

Formula

A053121 Catalan triangle (with 0's) read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A027306 a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A028364 Triangle T(n,m) = Sum_{k=0..m} Catalan(n-k)*Catalan(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A100100 Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.

Views

Author

Keywords

Comments

Examples

Links