cp's OEIS Frontend

A002054 Binomial coefficient C(2n+1, n-1).

%I A002054 M3913 N1607 #268 Apr 11 2025 08:44:35
%S A002054 1,5,21,84,330,1287,5005,19448,75582,293930,1144066,4457400,17383860,
%T A002054 67863915,265182525,1037158320,4059928950,15905368710,62359143990,
%U A002054 244662670200,960566918220,3773655750150,14833897694226,58343356817424,229591913401900
%N A002054 Binomial coefficient C(2n+1, n-1).
%C A002054 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]
%C A002054 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
%C A002054 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
%C A002054 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
%C A002054 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
%C A002054 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_, May 31 2004
%C A002054 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
%C A002054 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 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - _David Callan_, Jul 25 2008
%C A002054 a(n+1) is the total number of ascents in the set of all n-permutations 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
%C A002054 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
%C A002054 a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - _Oliver Pechenik_, May 02 2014
%C A002054 Number of paths in the half-plane 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
%C A002054 From _Gus Wiseman_, Aug 20 2021: (Start)
%C A002054 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.
%C A002054 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)^(i-1) y_i. For example, the a(3) = 21 compositions are:
%C A002054   (35)  (152)  (1124)  (11141)  (111113)
%C A002054         (251)  (1223)  (12131)  (111212)
%C A002054                (1322)  (13121)  (111311)
%C A002054                (1421)  (14111)  (121112)
%C A002054                (2114)           (121211)
%C A002054                (2213)           (131111)
%C A002054                (2312)
%C A002054                (2411)
%C A002054 The following pertain to these compositions:
%C A002054 - The unordered version is A344741.
%C A002054 - Ranked by A345924 (reverse: A345923).
%C A002054 - A345197 counts compositions by length and alternating sum.
%C A002054 - A345925 ranks compositions with alternating sum 2 (reverse: A345922).
%C A002054 (End)
%D A002054 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 A002054 George Grätzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
%D A002054 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.
%D A002054 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002054 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002054 G. C. Greubel, <a href="/A002054/b002054.txt">Table of n, a(n) for n = 1..1000</a> (terms 1..100 computed by T. D. Noe)
%H A002054 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 A002054 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 A002054 F. R. Bernhart and N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>.
%H A002054 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>, 2017.
%H A002054 Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://ajc.maths.uq.edu.au/pdf/84/ajc_v84_p398.pdf">Dyck Paths with catastrophes modulo the positions of a given pattern</a>, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
%H A002054 David Callan, <a href="https://arxiv.org/abs/math/0211380">A recursive bijective approach to counting permutations containing 3-letter patterns</a>, arXiv:math/0211380 [math.CO], 2002.
%H A002054 Arthur Cayley, <a href="https://doi.org/10.1112/plms/s1-22.1.237">On the partitions of a polygon</a>, Proc. London Math. Soc., Vol. 22 (1891), pp. 237-262 = Collected Mathematical Papers, Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
%H A002054 Matteo Cervetti and Luca Ferrari, <a href="https://arxiv.org/abs/2009.01024">Pattern avoidance in the matching pattern poset</a>, arXiv:2009.01024 [math.CO], 2020.
%H A002054 Colin Defant, <a href="https://arxiv.org/abs/1905.02309">Proofs of Conjectures about Pattern-Avoiding Linear Extensions</a>, arXiv:1905.02309 [math.CO], 2019.
%H A002054 Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., Vol. 204, No. 1-3 (1999), pp. 167-202.
%H A002054 Gennady Eremin, <a href="https://arxiv.org/abs/2306.10318">Dyck Numbers, IV. Nested patterns in OEIS A036991</a>, arXiv:2306.10318 [math.CO], 2023. See (5) p. 7.
%H A002054 Luca Ferrari and Emanuele Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">Enumeration of edges in some lattices of paths</a>, J. Int. Seq., Vol. 17 (2014), Article 14.1.5; <a href="https://arxiv.org/abs/1203.6792">arXiv preprint</a>, arXiv:1203.6792 [math.CO], 2012.
%H A002054 Xiaoyu He, Emily Huang, Ihyun Nam and Rishubh Thaper, <a href="https://arxiv.org/abs/2109.12455">Shuffle Squares and Reverse Shuffle Squares</a>, arXiv:2109.12455 [math.CO], 2021.
%H A002054 Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, <a href="https://arxiv.org/abs/2204.14023">Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k</a>, arXiv:2204.14023 [math.CO], 2022.
%H A002054 Milan Janjic, <a href="https://web.archive.org/web/20181001110015/https://pmf.unibl.org/wp-content/uploads/2017/10/enumfor.pdf">Two Enumerative Functions</a>.
%H A002054 Werner Krandick, <a href="http://dx.doi.org/10.1016/j.cam.2003.08.018">Trees and jumps and real roots</a>, J. Computational and Applied Math., Vol. 162, No. 1 (2004), pp. 51-55.
%H A002054 Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
%H A002054 Toufik Mansour and Alek Vainshtein, <a href="https://arxiv.org/abs/math/0105073">Counting occurrences of 123 in a permutation</a>, arXiv:math/0105073 [math.CO], 2001.
%H A002054 Henri Mühle, <a href="https://arxiv.org/abs/1509.06942">Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices</a>, arXiv:1509.06942 [math.CO], 2015.
%H A002054 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.
%H A002054 John Noonan and Doron Zeilberger, <a href="https://arxiv.org/abs/math/9808080">The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns</a>, arXiv:math/9808080 [math.CO], 1998.
%H A002054 Oliver Pechenik, <a href="https://arxiv.org/abs/1209.1355">Cyclic sieving of increasing tableaux and small Schröder paths</a>, arXiv:1209.1355 [math.CO], 2012-2014.
%H A002054 Oliver Pechenik, <a href="http://dx.doi.org/10.1016/j.jcta.2014.04.002">Cyclic sieving of increasing tableaux and small Schröder paths</a>, J. Combin. Theory A, Vol. 125 (2014), pp. 357-378.
%H A002054 Karol Penson, <a href="https://www.youtube.com/watch?v=E5tzklLog8Y">Hausdorff moment problems for combinatorial numbers: heuristics via Meijer G-functions</a>, Nov. 2022.
%H A002054 Ronald C. Read, <a href="https://doi.org/10.1007/BF03031688">On general dissections of a polygon</a>, Aequationes Mathematicae, Vol. 18, No. 1-2 (1978), pp. 370-388; <a href="/A001004/a001004.pdf">Preprint</a>, 1974.
%H A002054 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 A002054 Richard P. Stanley, <a href="http://dx.doi.org/10.1006/jcta.1996.0099">Polygon dissections and standard Young tableaux</a>, J. Comb. Theory, Ser. A, Vol. 76 , No. 1 (1996), pp. 175-177.
%H A002054 Daniel W. Stasiuk, <a href="http://hdl.handle.net/10388/11865">An Enumeration Problem for Sequences of n-ary Trees Arising from Algebraic Operads</a>, Master's Thesis, University of Saskatchewan-Saskatoon (2018).
%H A002054 A. Vogt, <a href="https://arxiv.org/abs/1108.2993">Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation</a>, arXiv:1108.2993 [hep-ph], 2011.
%H A002054 N. J. Wildberger and Dean Rubine, <a href="https://doi.org/10.1080/00029890.2025.2460966">A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode</a>, Amer. Math. Monthly (2025). See section 12.
%F A002054 a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n - 2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
%F A002054 G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - _Emeric Deutsch_, Jul 05 2003
%F A002054 From _Wolfdieter Lang_, Jan 09 2004: (Start)
%F A002054 a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).
%F A002054 G.f.: (1 - 2*x - (1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)
%F A002054 G.f.: z*C(z)^3/(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 A002054 G.f.: 2F1(5/2, 2; 4; 4*x). - _R. J. Mathar_, Aug 09 2015
%F A002054 D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - _Chai Wah Wu_, Jan 26 2016
%F A002054 From _Ilya Gutkovskiy_, Aug 30 2016: (Start)
%F A002054 E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).
%F A002054 a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)
%F A002054 a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - _Taras Goy_, Aug 09 2018
%F A002054 G.f.: (x - 1 + (1 - 3*x)/sqrt(1 - 4*x))/(2*x^2). - _Michael Somos_, Jul 28 2021
%F A002054 From _Amiram Eldar_, Jan 24 2022: (Start)
%F A002054 Sum_{n>=1} 1/a(n) = 5/3 - 2*Pi/(9*sqrt(3)).
%F A002054 Sum_{n>=1} (-1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5)) - 7/5, where phi is the golden ratio (A001622). (End)
%F A002054 a(n) = A001405(2*n+1) - A000108(n+1), n >= 1 (from Eremin link, page 7). - _Gennady Eremin_, Sep 05 2023
%F A002054 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
%F A002054 From _Peter Bala_, Oct 13 2024: (Start)
%F A002054 a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x - 3)/sqrt(4 - x) (see Penson).
%F A002054 G.f. x*/sqrt(1 - 4*x) * c(x)^3. (End)
%e A002054 G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...
%p A002054 with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # _Zerinvary Lajos_, May 03 2007
%t A002054 CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x,0,22}], x] (* _Robert G. Wilson v_, Aug 08 2011 *)
%t A002054 a[ n_]:= Binomial[2 n + 1, n - 1]; (* _Michael Somos_, Apr 25 2014 *)
%o A002054 (PARI) {a(n) = binomial( 2*n+1, n-1)};
%o A002054 (Magma) [Binomial(2*n+1, n-1): n in [1..30]]; // _Vincenzo Librandi_, Apr 20 2015
%o A002054 (Python)
%o A002054 from __future__ import division
%o A002054 A002054_list, b = [], 1
%o A002054 for n in range(1,10**3):
%o A002054     A002054_list.append(b)
%o A002054     b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # _Chai Wah Wu_, Jan 26 2016
%o A002054 (GAP) List([1..25],n->Binomial(2*n+1,n-1)); # _Muniru A Asiru_, Aug 09 2018
%o A002054 (Sage) [binomial(2*n+1, n-1) for n in (1..25)] # _G. C. Greubel_, Mar 22 2019
%Y A002054 Diagonal 4 of triangle A100257. Also a diagonal of A033282.
%Y A002054 Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
%Y A002054 Cf. A001263.
%Y A002054 Column k=1 of A263771.
%Y A002054 Counts terms of A031445 with 2n+2 digits in binary.
%Y A002054 Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.
%Y A002054 Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002694 (m = 4), A003516 (m = 5), A002696 (m = 6), A030053 - A030056, A004310 - A004318.
%K A002054 nonn,easy
%O A002054 1,2
%A A002054 _N. J. A. Sloane_