

A002054


Binomial coefficient C(2n+1, n1).
(Formerly M3913 N1607)


47



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)



OFFSET

1,2


COMMENTS

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 n1 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 18 (the entire path), 23, 27, 47, 56 and so contributes 5 to a(4).  David Callan, Jul 25 2008
a(n+1) = total number of ascents in the set of all npermutations 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 n1 blocks of size 2 and 1 block of size 3.  Oliver Pechenik, May 02 2014
Number of paths in the halfplane 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


REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 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, 19861992.
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).


LINKS

G. C. Greubel, Table of n, a(n) for n = 1..1000[Terms 1 to 100 computed by T. D. Noe; terms 101 to 1000 by G. C. Greubel, Jan 14 2017]
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, AprilMay 1994
J.L. Baril, S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.
D. Callan, A recursive bijective approach to counting permutations containing 3letter patterns, arXiv:math/0211380 [math.CO], 2002.
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237262 = Collected Mathematical Papers. Vols. 113, Cambridge Univ. Press, London, 18891897, Vol. 13, pp. 93ff.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167202.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012.  From N. J. A. Sloane, Oct 03 2012
Milan Janjic, Two Enumerative Functions [Broken link]
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 5155.
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 Catalantype 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], 20122014.
O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, 125 (2014), 357378.
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, 175177, 1996.
A. Vogt, Resummation of smallx double logarithms in QCD: semiinclusive electronpositron annihilation, arXiv:1108.2993 [hepph], 2011.


FORMULA

a(n) = Sum( binomial(2*i, i) * binomial(2*n 2*i, ni1)/(i+1), i=0..n1).  Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: zC^4/(2C), where C=[1sqrt(14z)]/(2z) is the Catalan function.  Emeric Deutsch, Jul 05 2003
a(n) = binomial(2*n+1, n1)= n*C(n+1)/2, C(n)=A000108(n) (Catalan). G.f.: (12*x(13*x)*c(x))/(x*(14*x)) with g.f. c(x) of A000108.  Wolfdieter Lang, Jan 09 2004
G.f.: z*C(z)^3/(12*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;4x).  R. J. Mathar, Aug 09 2015
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)


EXAMPLE

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


MAPLE

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


MATHEMATICA

CoefficientList[ Series[ 8/(((Sqrt[1  4 x] + 1)^3)*Sqrt[1  4 x]), {x, 0, 22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
a[ n_] := Binomial[ 2 n + 1, n  1]; (* Michael Somos, Apr 25 2014 *)


PROG

(PARI) {a(n) = binomial( 2*n+1, n1)};
(MAGMA) [Binomial(2*n+1, n1): n in [1..30]]; // Vincenzo Librandi, Apr 20 2015
(Python)
from __future__ import division
A002054_list, b = [], 1
for n in range(1, 10**3):
A002054_list.append(b)
b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016


CROSSREFS

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


KEYWORD

nonn,easy,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



