

A002054


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


88



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

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]
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) is the 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) is the 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) is the 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
Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.
Also the number of integer compositions of 2n+2 with alternating sum 2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (1)^(i1) y_i. For example, the a(3) = 21 compositions are:
(35) (152) (1124) (11141) (111113)
(251) (1223) (12131) (111212)
(1322) (13121) (111311)
(1421) (14111) (121112)
(2114) (121211)
(2213) (131111)
(2312)
(2411)
The following pertain to these compositions:
 The unordered version is A344741.
 A345197 counts compositions by length and alternating sum.
 A345925 ranks compositions with alternating sum 2 (reverse: A345922).
(End)


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.
George Grätzer, 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

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].
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., Vol. 22 (1891), pp. 237262 = Collected Mathematical Papers, Vols. 113, Cambridge Univ. Press, London, 18891897, Vol. 13, pp. 93ff.


FORMULA

a(n) = Sum_{j=0..n1} binomial(2*j, j) * binomial(2*n  2*j, nj1)/(j+1).  Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: z*C^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.: (1  2*x  (13*x)*c(x))/(x*(14*x)) with g.f. c(x) of A000108. (End)
Dfinite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)).  Chai Wah Wu, Jan 26 2016
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..n1} (n+1i)*binomial(2n+2,i), n >= 1.  Taras Goy, Aug 09 2018
G.f.: (x  1 + (1  3*x)/sqrt(1  4*x))/(2*x^2).  Michael Somos, Jul 28 2021
Sum_{n>=1} 1/a(n) = 5/3  2*Pi/(9*sqrt(3)).
Sum_{n>=1} (1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5))  7/5, where phi is the golden ratio (A001622). (End)
G.f.: x/(1  4*x)^2 * c(x/(1  4*x))^3, where c(x) = (1  sqrt(1  4*x))/(2*x) is the g.f. of the Catalan numbers A000108.  Peter Bala, Feb 03 2024


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[14x] +1)^3)*Sqrt[14x]), {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)};
(Python)
from __future__ import division
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, n1)); # Muniru A Asiru, Aug 09 2018
(Sage) [binomial(2*n+1, n1) for n in (1..25)] # G. C. Greubel, Mar 22 2019


CROSSREFS

Counts terms of A031445 with 2n+2 digits in binary.
Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.


KEYWORD

nonn,easy


AUTHOR



STATUS

approved



