The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002054 Binomial coefficient C(2n+1, n-1).
(Formerly M3913 N1607)
1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226, 58343356817424, 229591913401900 (list; graph; refs; listen; history; text; internal format)



Permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1=1 permutations containing exactly one 312 pattern.

Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003

Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003

Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003

Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004

Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004

Number of jumps in all full binary trees with n+1 internal nodes. 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. - Emeric Deutsch, Jan 18 2007

a(n) = total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008

a(n+1) = total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013

Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014

a(n) = number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014

Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015


M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.

G. Gratzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.

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.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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


G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..100 computed by T. D. Noe)

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].

F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994

J.-L. Baril and S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.

D. Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.

A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.

Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.

Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014) #14.1.5

Milan Janjic, Two Enumerative Functions [Broken link]

W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

T. Mansour and A. Vainshtein, Counting occurrences of 123 in a permutation, arXiv:math/0105073 [math.CO], 2001.

Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942 [math.CO], 2015.

Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Article 12.3.3, 2012.

J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns, arXiv:math/9808080 [math.CO], 1998.

O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, arXiv:1209.1355 [math.CO], 2012-2014.

O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, 125 (2014), 357-378.

R. C. Read, On general dissections of a polygon, Preprint (1974)

R. P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76, 175-177, 1996.

Daniel W. Stasiuk, An Enumeration Problem for Sequences of n-ary Trees Arising from Algebraic Operads, Master's Thesis, University of Saskatchewan-Saskatoon (2018).

A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv:1108.2993 [hep-ph], 2011.


a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n -2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000

G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - Emeric Deutsch, Jul 05 2003

From Wolfdieter Lang, Jan 09 2004: (Start)

a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).

G.f.: (1 -2*x -(1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)

G.f.: z*C(z)^3/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015

G.f.: 2F1(5/2, 2; 4; 4*x). - R. J. Mathar, Aug 09 2015

D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - Chai Wah Wu, Jan 26 2016

From Ilya Gutkovskiy, Aug 30 2016: (Start)

E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).

a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)

a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - Taras Goy, Aug 09 2018


G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...


with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # Zerinvary Lajos, May 03 2007


CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x, 0, 22}], x] (* Robert G. Wilson v, Aug 08 2011 *)

a[n_]:= Binomial[2 n + 1, n - 1]; (* Michael Somos, Apr 25 2014 *)


(PARI) {a(n) = binomial( 2*n+1, n-1)};

(MAGMA) [Binomial(2*n+1, n-1): n in [1..30]]; // Vincenzo Librandi, Apr 20 2015


from __future__ import division

A002054_list, b = [], 1

for n in range(1, 10**3):


    b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016

(GAP) List([1..25], n->Binomial(2*n+1, n-1)); # Muniru A Asiru, Aug 09 2018

(Sage) [binomial(2*n+1, n-1) for n in (1..25)] # G. C. Greubel, Mar 22 2019


Diagonal 4 of triangle A100257. Also a diagonal of A033282.

Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.

Cf. A001263.

Column k=1 of A263771.

Sequence in context: A146585 A215008 A026027 * A289797 A246986 A272547

Adjacent sequences:  A002051 A002052 A002053 * A002055 A002056 A002057




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 16 15:55 EDT 2021. Contains 343949 sequences. (Running on oeis4.)