1,2

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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (callan(AT)stat.wisc.edu), Jul 25 2008

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

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

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.

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.

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

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.

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

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

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

T. D. Noe, Table of n, a(n) for n=1..100

Milan Janjic, Two Enumerative Functions

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

T. Mansour and A. Vainshtein, Counting occurrences of 123 in a permutation.

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

D. Callan, A recursive bijective approach to counting permutations...

Sum( binomial(2*i, i) * binomial(2*n -2*i, n-i-1)/(i+1), i=0..n-1) = binomial(2*n + 1, n - 1) - Yong Kong (ykong(AT)curagen.com), Dec 26 2000

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

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. - Wolfdieter Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de), Jan 09, 2004

seq((count(Composition(2*n), size=n-1)), n=2..24); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 03 2007

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

Diagonal 4 of triangle A100257.

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

Cf. A001263.

Sequence in context: A146041 A146585 A026027 this_sequence A028948 A002450 A084241

Adjacent sequences: A002051 A002052 A002053 this_sequence A002055 A002056 A002057

nonn,easy

N. J. A. Sloane (njas(AT)research.att.com).