|
%I M3500 N1421 #262 Feb 29 2024 23:08:21
%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
%C 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
%C 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 x-axis, and end strictly above the x-axis; 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
%C From _Gus Wiseman_, Jul 21 2021: (Start)
%C 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)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:
%C (1,2) (2,3) (3,4)
%C (1,3,1) (1,4,2)
%C (1,1,1,2) (2,4,1)
%C (1,2,1,1) (1,1,2,3)
%C (1,2,2,2)
%C (1,3,2,1)
%C (2,1,1,3)
%C (2,2,1,2)
%C (2,3,1,1)
%C (1,1,1,3,1)
%C (1,2,1,2,1)
%C (1,3,1,1,1)
%C (1,1,1,1,1,2)
%C (1,1,1,2,1,1)
%C (1,2,1,1,1,1)
%C The following relate to these compositions.
%C - The unordered version is A000070.
%C - Allowing any negative alternating sum gives A000346.
%C - The opposite (positive 1) version is A000984.
%C - The version for reverse-alternating sum is also A001791 (this sequence).
%C - Taking alternating sum -2 instead of -1 gives A002054.
%C - The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.
%C - Ranked by A345910 (reverse: A345912).
%C 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.
%C (End)
%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 Cornelius 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 Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, <a href="https://arxiv.org/abs/2301.09765">Enumeration of multi-rooted plane trees</a>, arXiv:2301.09765 [math.CO], 2023.
%H Jean-Luc Baril and Sergey Kirgizov, <a href="https://doi.org/10.1016/j.disc.2017.06.005">The pure descent statistic on permutations</a>, Discrete Mathematics, Vol. 340, No. 10 (2017), pp. 2550-2558; <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">preprint</a>, 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 and 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 Jelena Đokic, <a href="https://arxiv.org/abs/2308.04155">A short note on the order of the double reduced 2-factor transfer digraph for rectangular grid graphs</a>, arXiv:2308.04155 [math.CO], 2023.
%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 21.
%H Guo-Niu Han, <a href="https://web.archive.org/web/20111226024706/http://www-irma.u-strasbg.fr:80/~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 Milan Janjic and Boris Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
%H Milan Janjic and Boris 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., Vol. 17 (2014), Article 14.3.5.
%H Christian Krattenthaler and Daniel Yaqubi, <a href="https://doi.org/10.1016/j.aam.2018.08.004">Some determinants of path generating functions, II</a>, Advances in Applied Mathematics, Vol. 101 (2018), pp. 232-265; <a href="https://arxiv.org/abs/1802.05990">arXiv preprint</a>, arXiv:1802.05990 [math.CO], 2018.
%H Cornelius 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, Vol. 15 (2012), Article 12.3.3. - From _N. J. A. Sloane_, Sep 16 2012
%H Mark Shattuck, <a href="https://arxiv.org/abs/2303.06300">Enumeration of non-crossing partitions according to subwords with repeated letters</a>, arXiv:2303.06300 [math.CO], 2023.
%H Zhi Lan Wang, <a href="https://doi.org/10.1007/s10114-016-5565-5">Tautological integrals on symmetric products of curves</a>, Acta Mathematica Sinica, English Series, Vol. 32, No. 8 (2016), pp. 901-910; <a href="https://arxiv.org/abs/1506.08405">arXiv preprint</a>, arXiv:1506.08405 [math.AG], 2015-2016; <a href="http://123.57.41.99/Jwk_sxxb_en/EN/abstract/abstract22794.shtml">alternative link</a>.
%H Jian Zhou, <a href="https://arxiv.org/abs/1810.03883">Fat and Thin Emergent Geometries of Hermitian One-Matrix Models</a>, arXiv:1810.03883 [math-ph], 2018.
%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 a(n) = 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 D-finite with recurrence: (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
%F Sum_{n>=1} 1/a(n) = 1/3 + 5*Pi/(9*sqrt(3)). - _Amiram Eldar_, Dec 04 2020
%F 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
%F a(n) = Product_{i=1..(n - 1)} (((4*i + 6)*i + 2)/((i + 2)*i)), for n>=1. - _Neven Sajko_, Oct 10 2021
%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 Diagonal 3 of triangle A100257.
%Y First differences are in A076540.
%Y Cf. A000108, A000984, A002378, A002390, A025566, A132812.
%Y A345197 counts compositions by length and alternating sum.
%Y Cf. A000070, A000302, A000346, A002054, A008549, A032443, A088218, A097805, A163493, A202736, A345910.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
|
