This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001791 a(n) = binomial coefficient C(2n, n-1).
(Formerly M3500 N1421)

%I M3500 N1421

%S 0,1,4,15,56,210,792,3003,11440,43758,167960,646646,2496144,9657700,

%T 37442160,145422675,565722720,2203961430,8597496600,33578000610,

%U 131282408400,513791607420,2012616400080,7890371113950,30957699535776,121548660036300,477551179875952

%N a(n) = binomial coefficient C(2n, n-1).

%C 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

%C 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

%C 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 x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - _Herbert Kociemba_, May 23 2004

%C 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

%C 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

%C Also number of peaks plus number of valleys in all Dyck n-paths. - _David Scambler_, Oct 08 2012

%C Apparently counts UDDUD in all Dyck paths of semilength n+2. - _David Scambler_, Apr 22 2013

%C Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - _David Scambler_, Apr 30 2013

%C For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - _L. Edson Jeffery_, Jul 24 2014

%C Number of paths in the half-plane 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

%D 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.

%D C. Lanczos, Applied Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 517.

%D R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281-295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.

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

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

%H T. D. Noe and Matuszka Tamás, <a href="/A001791/b001791.txt">Table of n, a(n) for n = 0..1200</a> (terms n = 0..200 from T. D. Noe)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H J.-L. Baril, S. Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, Preprint, 2016.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry5/barry223.html">On the Hurwitz Transform of Sequences</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.

%H Miklós Bóna, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p62">Surprising Symmetries in Objects Counted by Catalan Numbers</a>, Electronic J. Combin., 19 (2012), P62, eq. (6).

%H Libor Caha, Daniel Nagaj, <a href="https://arxiv.org/abs/1805.07168">The pair-flip model: a very entangled translationally invariant spin chain</a>, arXiv:1805.07168 [quant-ph], 2018.

%H Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p77puzzle.pdf">Enumeration of Standard Puzzles</a>

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]

%H A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, <a href="http://www.acta.sapientia.ro/acta-info/C4-2/info42-7.pdf">Parallel enumeration of degree sequences of simple graphs</a>, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 260-288.

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Two Enumerative Functions</a>

%H M. Janjic and B. Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv preprint arXiv:1301.4550 [math.CO], 2013.

%H M. Janjic, B. Petkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html">A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers</a>, J. Int. Seq. 17 (2014) # 14.3.5

%H Christian Krattenthaler, Daniel Yaqubi, <a href="https://arxiv.org/abs/1802.05990">Some determinants of path generating functions, II</a>, Adv. Appl. Math. 101 (2018), 232-265.

%H C. Lanczos, <a href="/A002457/a002457.pdf">Applied Analysis</a> (Annotated scans of selected pages)

%H Asamoah Nkwanta and Earl R. Barnes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Nkwanta/nkwanta2.html">Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind</a>, Journal of Integer Sequences, Article 12.3.3, 2012. - From _N. J. A. Sloane_, Sep 16 2012.

%H Zhi Lan Wang, <a href="https://arxiv.org/abs/1506.08405">Tautological Integrals on Symmetric Products of Curves</a>, Acta Mathematica Sinica, English Series, Aug., 2016, Vol. 32, No. 8, pp. 901-910 DOI: 10.1007/s10114-016-5565-5. See <a href="">also</a>

%F a(n) = n*A000108(n).

%F G.f.: x*(d/dx)c(x) where c(x) = Catalan g.f. - _Wolfdieter Lang_

%F Convolution of A001700 (central binomial of odd order) and A000108 (Catalan): a(n+1) = Sum_{k=0..n} C(k)*binomial(2*(n-k)+1, n-k), C(k): Catalan. - _Wolfdieter Lang_

%F E.g.f.: exp(2x) I_1(2x), where I_1 is Bessel function. - _Michael Somos_, Sep 08 2002

%F a(n) = Sum_{k=0..n} C(n, k)*C(n, k+1). - _Paul Barry_, May 15 2003

%F a(n) = Sum_{i=1..n} binomial(i+n-1, n).

%F G.f.: (1-2x-sqrt(1-4x))/(2x*sqrt(1-4x)). - _Emeric Deutsch_, Dec 05 2003

%F A092956/(n!). - _Amarnath Murthy_, Jun 16 2004

%F a(n) = binomial(2n,n) - A000108(n). - _Paul Barry_, Apr 21 2005.

%F a(n) = (1/(2*Pi))*Integral_{x=0..4} (x^n*(x-2)/sqrt(x(4-x))) is the moment sequence representation. - _Paul Barry_, Jan 11 2007

%F Row sums of triangle A132812 starting (1, 4, 15, 56, 210, ...). - _Gary W. Adamson_, Sep 01 2007

%F 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

%F For n >= 1, a(2^n) = 2^(n+1)*A001795(2^(n-1)). - _Vladimir Shevelev_, Sep 05 2010

%F (n-1)*(n+1)*a(n) = 2*n*(2n-1)*a(n-1). - _R. J. Mathar_, Dec 17 2011

%F From _Sergei N. Gladkovskii_, Jul 07 2012: (Start)

%F 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, 3-step);

%F 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, 3-step).

%F (End)

%F G.f.: c(x)^3/(2-c(x)) where c(x) is the g.f. for A000108. - _Cheyne Homberger_, May 05 2014

%F G.f.: z*C(z)^2/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - _José Luis Ramírez Ramírez_, Apr 19 2015

%F G.f.: x*2F1(3/2,2;3;4x). - _R. J. Mathar_, Aug 09 2015

%F a(n) = Sum_{i=1..n}((binomial(2*i-2,i-1)*binomial(2*(n-i+1),n-i+2))/(n-i+1)). - _Vladimir Kruchinin_, Sep 07 2015

%F 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

%t Table[Binomial[2n,n-1],{n,0,30}] (* _Harvey P. Dale_, Jul 12 2012 *)

%t CoefficientList[ Series[(1 - 2x - Sqrt[1 - 4x])/(2x*Sqrt[1 - 4x]), {x, 0, 26}], x] (* _Robert G. Wilson v_, Aug 10 2018 *)

%o (PARI) a(n)=if(n<1,0,(2*n)!/(n+1)!/(n-1)!)

%o (Maxima) A001791(n):=binomial(2*n,n-1)$

%o makelist(A001791(n),n,0,30); /* _Martin Ettl_, Nov 05 2012 */

%o (MAGMA) [Binomial(2*n, n-1): n in [0..30]]; // _Vincenzo Librandi_, Apr 20 2015

%o (GAP) List([0..30],n->Binomial(2*n,n-1)); # _Muniru A Asiru_, Aug 09 2018

%Y Cf. A000984.

%Y Diagonal 3 of triangle A100257.

%Y First differences are in A076540.

%Y Cf. A000108, A000984, A002378, A025566, A132812.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 09:23 EST 2018. Contains 317279 sequences. (Running on oeis4.)