A014495 -id:A014495 - 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

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

Original entry on oeis.org

0, 1, 1, 4, 5, 16, 22, 64, 93, 256, 386, 1024, 1586, 4096, 6476, 16384, 26333, 65536, 106762, 262144, 431910, 1048576, 1744436, 4194304, 7036530, 16777216, 28354132, 67108864, 114159428, 268435456, 459312152, 1073741824, 1846943453

Offset: 0

Yong Kong (ykong(AT)curagen.com), Dec 29 2000

a(n) is the number of n-digit binary sequences that have more 1's than 0's. - Geoffrey Critzer, Jul 16 2009
Maps to the number of walks that end above 0 on the number line with steps being 1 or -1. - Benjamin Phillabaum, Mar 06 2011
Chris Godsil observes that a(n) is the independence number of the (n+1)-folded cube graph; proof is by a Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even). - Stan Wagon, Jan 29 2013
Also the number of subsets of {1,2,...,n} that contain more odd than even numbers.  For example, for n=4, a(4)=5 and the 5 subsets are {1}, {3}, {1,3}, {1,2,3}, {1,3,4}. See A014495 when same number of even and odd numbers. - Enrique Navarrete, Feb 10 2018
Also half the number of length-n binary sequences with a different number of zeros than ones. This is also the number of integer compositions of n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Also the number of integer compositions of n+1 with alternating sum <= 0, ranked by A345915 (reverse: A345916). - Gus Wiseman, Jul 19 2021

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
From _Gus Wiseman_, Jul 19 2021: (Start)
The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
  (1)  (2)  (3)      (4)      (5)
            (1,2)    (1,3)    (1,4)
            (2,1)    (3,1)    (2,3)
            (1,1,1)  (1,1,2)  (3,2)
                     (2,1,1)  (4,1)
                              (1,1,3)
                              (1,2,2)
                              (1,3,1)
                              (2,1,2)
                              (2,2,1)
                              (3,1,1)
                              (1,1,1,2)
                              (1,1,2,1)
                              (1,2,1,1)
                              (2,1,1,1)
                              (1,1,1,1,1)
(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.7)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Folded Cube Graph
Eric Weisstein's World of Mathematics, Independence Number

The odd bisection is A000302.
The even bisection is A000346.
The following relate to compositions with nonzero alternating sum:
- The complement is counted by A001700 or A138364.
- The version for alternating sum > 0 is A027306.
- The unordered version is A086543 (even bisection: A182616).
- The version for alternating sum < 0 is A294175.
- These compositions are ranked by A345921.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.

[(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // G. C. Greubel, Aug 08 2022

Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* Geoffrey Critzer, Jul 16 2009 *)
a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* Michael Somos, Nov 22 2014 *)
a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* Michael Somos, Nov 22 2014 *)
Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* Eric W. Weisstein, Mar 21 2018 *)
CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* Eric W. Weisstein, Mar 21 2018 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]!=0&]],{n,0,15}] (* Gus Wiseman, Jul 19 2021 *)

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ Michel Marcus, Dec 30 2015

my(x='x+O('x^100)); concat(0, Vec(2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))))) \\ Altug Alkan, Dec 30 2015

from math import comb
def A058622(n): return (1<>1)>>1) if n else 0 # Chai Wah Wu, Aug 25 2025

[(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - Vladeta Jovovic, Apr 27 2003
E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - Benjamin Phillabaum, Mar 06 2011
Logarithmic derivative of the g.f. of A210736 is a(n+1). - Michael Somos, Nov 22 2014
Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - Gus Wiseman, Jul 19 2021
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, Sep 23 2021
a(n) = 2^n-A027306(n). - R. J. Mathar, Sep 23 2021
A027306(n) - a(n) = A126869(n). - R. J. Mathar, Sep 23 2021

A214292 Triangle read by rows: T(n,k) = T(n-1,k-1) + T(n-1,k), 0 < k < n with T(n,0) = n and T(n,n) = -n.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Jul 12 2012

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

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened
Index entries for triangles and arrays related to Pascal's triangle

Cf. A007318, A000004, A000096, A000108, A000245, A000344, A000588, A000589, A000590, A001392, A002057, A003517, A003518, A003519, A005557, A005586, A005587, A008313, A014495, A064059, A064061, A080956, A090749, A097808, A112467, A124087, A124088, A129936, A259525.

a214292 n k = a214292_tabl !! n !! k
a214292_row n = a214292_tabl !! n
a214292_tabl = map diff $ tail a007318_tabl
   where diff row = zipWith (-) (tail row) row

row[n_] := Table[Binomial[n, k], {k, 0, n}] // Differences;
T[n_, k_] := row[n + 1][[k + 1]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 31 2018 *)

T(n,k) = A007318(n+1,k+1) - A007318(n+1,k), 0<=k<=n, i.e. first differences of rows in Pascal's triangle;
T(n,k) = -T(n,k);
row sums and central terms equal 0, cf. A000004;
sum of positive elements of n-th row = A014495(n+1);
T(n,0) = n;
T(n,1) = A000096(n-2) for n > 1; T(n,1) = - A080956(n) for n > 0;
T(n,2) = A005586(n-4) for n > 3; T(n,2) = A129936(n-2);
T(n,3) = A005587(n-6) for n > 5;
T(n,4) = A005557(n-9) for n > 8;
T(n,5) = A064059(n-11) for n > 10;
T(n,6) = A064061(n-13) for n > 12;
T(n,7) = A124087(n) for n > 14;
T(n,8) = A124088(n) for n > 16;
T(2*n+1,n) = T(2*n+2,n) = A000108(n+1), Catalan numbers;
T(2*n+3,n) = A000245(n+2);
T(2*n+4,n) = A002057(n+1);
T(2*n+5,n) = A000344(n+3);
T(2*n+6,n) = A003517(n+3);
T(2*n+7,n) = A000588(n+4);
T(2*n+8,n) = A003518(n+4);
T(2*n+9,n) = A001392(n+5);
T(2*n+10,n) = A003519(n+5);
T(2*n+11,n) = A000589(n+6);
T(2*n+12,n) = A090749(n+6);
T(2*n+13,n) = A000590(n+7).

A037952 a(n) = binomial(n, floor((n-1)/2)).

Original entry on oeis.org

0, 1, 1, 3, 4, 10, 15, 35, 56, 126, 210, 462, 792, 1716, 3003, 6435, 11440, 24310, 43758, 92378, 167960, 352716, 646646, 1352078, 2496144, 5200300, 9657700, 20058300, 37442160, 77558760, 145422675, 300540195, 565722720, 1166803110, 2203961430, 4537567650

Offset: 0

N. J. A. Sloane

nonn

First differences of central binomial coefficients: a(n) = A001405(n+1) - A001405(n).
The maximum size of an intersecting (or proper) antichain on an n-set. - Vladeta Jovovic, Dec 27 2000
Number of ordered trees with n+1 edges, having root of degree at least 2 and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002
a(n)=number of Dyck (n+1)-paths that are symmetric but not prime. A prime Dyck path is one that returns to the x-axis only at its terminal point. For example a(3)=3 counts UDUUDDUD, UUDDUUDD, UDUDUDUD. - David Callan, Dec 09 2004
Number of involutions of [n+2] containing the pattern 132 exactly once. For example, a(3)=3 because we have 1'3'2'45, 42'5'13' and 52'4'3'1 (the entries corresponding to the pattern 132 are "primed"). - Emeric Deutsch, Nov 17 2005
Also number of ways to put n eggs in floor(n/2) baskets where order of the baskets matters and all baskets have at least 1 egg. - Ben Paul Thurston, Sep 30 2006
For n >= 1 the number of standard Young tableaux with shapes corresponding to partitions into at most 2 distinct parts. - Joerg Arndt, Oct 25 2012
It seems that 3, 4, 10, ... are Colbourn's Covering Array Numbers CAN(2,k,2). - Ryan Dougherty, May 27 2015
Essentially the same as A007007. - Georg Fischer, Oct 02 2018
a(n) is the number of subsets of {1,2,...,n} that contain exactly 1 more odd than even elements.  For example, for n = 6, a(6) = 15 and the 15 sets are {1}, {3}, {5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,3,6}, {1,4,5}, {1,5,6}, {2,3,5}, {3,4,5}, {3,5,6}, {1,2,3,4,5}, {1,2,3,5,6}, {1,3,4,5,6}. - Enrique Navarrete, Dec 21 2019
a(n) is the number of lattice paths of n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(3)=3 counts UUU, UUD, UDU, and a(4)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021
For n >= 3, a(n) is also the number of pinnacle sets in the (n-2)-Plummer-Toft graph. - Eric W. Weisstein, Sep 11 2024

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
C. J. Colbourn, Table of CAN(2, k, 2)
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.
O. Guibert and T. Mansour, Restricted 132-involutions, Sem. Lotharingien de Combinatoire, 48, 2002, Article B48a (Corollary 4.2).
M. Miyakawa, A. Nozaki, G. Pogosyan, and I. G. Rosenberg, A map from the lower-half of the n-Cube onto the (n-1)-Cube which preserves intersecting antichains, Discr. Appl. Math. 92 (2-3) (1999) 223-228.
M. van de Vel, Determination of msd(L^n), J. Algebraic Combin., 9 (1999), 161-171.
Eric Weisstein's World of Mathematics, Pinnacle Set.
Eric Weisstein's World of Mathematics, Plummer-Toft Graph.

Cf. A007007, A032263, A014495 (partial sums), A001405 (partial sums + 1).
Cf. A035951, A035953, A035954, A035955, A035956, A035957.
Cf. A051303, A051304, A051305, A051306, A051307.
Cf. A047171, A036256, A051920.
Cf. A265848.

a037952 n = a037952_list !! n
a037952_list = zipWith (-) (tail a001405_list) a001405_list
-- Reinhard Zumkeller, Mar 04 2012

[Binomial(n, Floor((n-1)/2)): n in [0..40]]; // G. C. Greubel, Jun 21 2022

a:= n-> binomial(n, floor((n-1)/2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 19 2017

Table[ Binomial[n, Floor[n/2]], {n, 0, 35}]//Differences (* Jean-François Alcover, Jun 10 2013 *)
f[n_] := Binomial[n, Floor[(n-1)/2]]; Array[f, 35, 0] (* Robert G. Wilson v, Nov 13 2014 *)

a(n) = binomial(n, (n-1)\2); \\ Altug Alkan, Oct 03 2018

[binomial(n, (n-1)//2) for n in (0..40)] # G. C. Greubel, Jun 21 2022

E.g.f.: BesselI(1, 2*x) + BesselI(2, 2*x). - Vladeta Jovovic, Apr 28 2003
O.g.f.: (1-sqrt(1-4x^2))/(x - 2x^2 + x*sqrt(1-4x^2)).
Convolution of A001405 and A126120 shifted right: g001405(x)*g126120(x) = g037952(x)/x. - Philippe Deléham, Mar 17 2007
D-finite with recurrence: (n+2)*a(n) + (-n-2)*a(n-1) + 2*(-2*n+1)*a(n-2) + 4*(n-2)*a(n-3) = 0. - R. J. Mathar, Jan 25 2013. Proved by Robert Israel, Nov 13 2014
For n > 0: a(n) = A265848(n,0). - Reinhard Zumkeller, Dec 24 2015
a(n) = binomial(n, (n-2)/2) = A001791(n/2), n even; a(n) = binomial(n, (n+1)/2) = A001700((n-1)/2), n odd. - Enrique Navarrete, Dec 21 2019
From R. J. Mathar, Sep 23 2021: (Start)
A001405(n) = a(n) + A000108(n/2), where A(.)=0 for non-integer arguments.
a(n) = Sum_{m=1..n} A053121(n,m) [comment Callan-Deutsch].
a(2n+1) = A000984(n+1)/2. (End)
a(n) = Sum_{k=2..n} A143359(n,k). [Callan's 2004 comment]. - R. J. Mathar, Sep 24 2021
From Amiram Eldar, Sep 27 2024: (Start)
Sum_{n>=1} 1/a(n) = 1 + Pi/sqrt(3).
Sum_{n>=1} (-1)^(n+1)/a(n) = (3 - Pi/sqrt(3))/9. (End)

cp's OEIS Frontend

A218008 Sum of successive absolute differences of the binomial coefficients = 2*A014495(n).

Views

Author

Keywords

Crossrefs

Programs

Maxima

Formula

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Python

SageMath

Formula

A214292 Triangle read by rows: T(n,k) = T(n-1,k-1) + T(n-1,k), 0 < k < n with T(n,0) = n and T(n,n) = -n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A037952 a(n) = binomial(n, floor((n-1)/2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A047884 Triangle of numbers a(n,k) = number of Young tableaux with n cells and k rows (1 <= k <= n); also number of self-inverse permutations on n letters in which the length of the longest scattered (i.e., not necessarily contiguous) increasing subsequence is k.

Views

Author

Keywords

Examples

References

Links