

A001791


a(n) = binomial coefficient C(2n, n1).
(Formerly M3500 N1421)


131



0, 1, 4, 15, 56, 210, 792, 3003, 11440, 43758, 167960, 646646, 2496144, 9657700, 37442160, 145422675, 565722720, 2203961430, 8597496600, 33578000610, 131282408400, 513791607420, 2012616400080, 7890371113950, 30957699535776, 121548660036300, 477551179875952
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,1) and the peaks at even level are shown by *.  Emeric Deutsch, Dec 05 2003
Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges.  Emeric Deutsch, Feb 22 2004
Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line xy=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN.  Herbert Kociemba, May 23 2004
Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536.  Gary W. Adamson, Jan 04 2008
Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...).  Gary W. Adamson, May 17 2009
Also number of peaks plus number of valleys in all Dyck npaths.  David Scambler, Oct 08 2012
Apparently counts UDDUD in all Dyck paths of semilength n+2.  David Scambler, Apr 22 2013
Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1.  David Scambler, Apr 30 2013
For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (socalled "weak" compositions).  L. Edson Jeffery, Jul 24 2014
Number of paths in the halfplane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU.  José Luis Ramírez Ramírez, Apr 19 2015
For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n).  Amiram Eldar, Dec 04 2020
a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,1)} that start at the origin, never go below the xaxis, and end strictly above the xaxis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU.  David Callan and Emeric Deutsch, Jan 25 2021
Also the number of integer compositions of 2n+1 with alternating sum 1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (1)^(i1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:
(1,2) (2,3) (3,4)
(1,3,1) (1,4,2)
(1,1,1,2) (2,4,1)
(1,2,1,1) (1,1,2,3)
(1,2,2,2)
(1,3,2,1)
(2,1,1,3)
(2,2,1,2)
(2,3,1,1)
(1,1,1,3,1)
(1,2,1,2,1)
(1,3,1,1,1)
(1,1,1,1,1,2)
(1,1,1,2,1,1)
(1,2,1,1,1,1)
The following relate to these compositions.
 The unordered version is A000070.
 Allowing any negative alternating sum gives A000346.
 The opposite (positive 1) version is A000984.
 The version for reversealternating sum is also A001791 (this sequence).
 Taking alternating sum 2 instead of 1 gives A002054.
 The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.
Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.
(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.
Cornelius Lanczos, Applied Analysis, PrenticeHall, Englewood Cliffs, NJ, 1956, p. 517.
R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.
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].
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.


FORMULA

Convolution of A001700 (central binomial of odd order) and A000108 (Catalan): a(n+1) = Sum_{k=0..n} C(k)*binomial(2*(nk)+1, nk), C(k): Catalan.  Wolfdieter Lang
E.g.f.: exp(2x) I_1(2x), where I_1 is Bessel function.  Michael Somos, Sep 08 2002
a(n) = Sum_{k=0..n} C(n, k)*C(n, k+1).  Paul Barry, May 15 2003
a(n) = Sum_{i=1..n} binomial(i+n1, n).
G.f.: (12xsqrt(14x))/(2x*sqrt(14x)).  Emeric Deutsch, Dec 05 2003
a(n) = (1/(2*Pi))*Integral_{x=0..4} (x^n*(x2)/sqrt(x(4x))) is the moment sequence representation.  Paul Barry, Jan 11 2007
Starting (1, 4, 15, 56, 210, ...) gives the binomial transform of A025566 starting (1, 3, 8, 22, 61, 171, ...).  Gary W. Adamson, Sep 01 2007
Dfinite with recurrence: (n1)*(n+1)*a(n) = 2*n*(2n1)*a(n1).  R. J. Mathar, Dec 17 2011
G.f.: 1/(2*x)  G(0) where G(k) = 1  1/(2*x  8*x^3*(2*k+1)/(4*x^2*(2*k+1) (k+1)/G(k+1))); (continued fraction, 3rd kind, 3step);
E.g.f.: BesselI(1,2*x)*exp(2*x) = x*G(0) where G(k) = 1 + 2*x*(4*k+3)/((2*k+1)*(2*k+3)  x*(2*k+1)*(2*k+3)*(4*k+5)/(x*(4*k+5) + 2*(k+1)*(k+2)/G(k+1))); (continued fraction, 3rd kind, 3step).
(End)
a(n) = Sum_{i=1..n} binomial(2*i2,i1)*binomial(2*(ni+1),ni+2)/(ni+1).  Vladimir Kruchinin, Sep 07 2015
L.g.f.: 1/(1  x/(1  x/(1  x/(1  x/(1  x/(1  ...)))))) = Sum_{n>=1} a(n)*x^n/n.  Ilya Gutkovskiy, May 10 2017
Sum_{n>=1} 1/a(n) = 1/3 + 5*Pi/(9*sqrt(3)).  Amiram Eldar, Dec 04 2020
Sum_{n>=1} (1)^(n+1)/a(n) = 1/5 + 14*sqrt(5)*log(phi)/25, where log(phi) = A002390.  Amiram Eldar, Feb 20 2021
a(n) = Product_{i=1..(n  1)} (((4*i + 6)*i + 2)/((i + 2)*i)), for n>=1.  Neven Sajko, Oct 10 2021


MATHEMATICA

Table[Binomial[2n, n1], {n, 0, 30}] (* Harvey P. Dale, Jul 12 2012 *)
CoefficientList[ Series[(1  2x  Sqrt[1  4x])/(2x*Sqrt[1  4x]), {x, 0, 26}], x] (* Robert G. Wilson v, Aug 10 2018 *)


PROG

(PARI) a(n)=if(n<1, 0, (2*n)!/(n+1)!/(n1)!)
(Maxima) A001791(n):=binomial(2*n, n1)$
(GAP) List([0..30], n>Binomial(2*n, n1)); # Muniru A Asiru, Aug 09 2018


CROSSREFS

A345197 counts compositions by length and alternating sum.
Cf. A000070, A000302, A000346, A002054, A008549, A032443, A088218, A097805, A163493, A202736, A345910.


KEYWORD

nonn,easy,nice


AUTHOR



STATUS

approved



