|
| |
|
|
A002054
|
|
Binomial coefficient C(2n+1,n-1).
(Formerly M3913 N1607)
|
|
36
| |
|
|
1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226
(list; graph; refs; listen; history; 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 (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
|
|
|
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.
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.
G. Gratzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
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.
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).
R. P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76, 175-177, 1996.
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, Arxiv preprint arXiv:1108.2993, 2011
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..100
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].
D. Callan, A recursive bijective approach to counting permutations...
Milan Janjic, Two Enumerative Functions
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
|
|
|
FORMULA
| 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
|
|
|
MAPLE
| seq((count(Composition(2*n), size=n-1)), n=2..24); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 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 *)
|
|
|
PROG
| (PARI) a(n)=binomial(2*n+1, n-1)
|
|
|
CROSSREFS
| Diagonal 4 of triangle A100257.
Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
Cf. A001263.
Sequence in context: A146041 A146585 A026027 * A028948 A002450 A084241
Adjacent sequences: A002051 A002052 A002053 * A002055 A002056 A002057
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
