A014137 Partial sums of Catalan numbers (A000108).
1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918, 23714, 82500, 290512, 1033412, 3707852, 13402697, 48760367, 178405157, 656043857, 2423307047, 8987427467, 33453694487, 124936258127, 467995871777, 1757900019101, 6619846420553, 24987199492705, 94520750408709, 358268702159069
Offset: 0
Examples
G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 65*x^5 + 197*x^6 + 626*x^7 + 2056*x^8 + ...
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 200 by T. D. Noe)
- G. Alvarez, J. E. Bergner, and R. Lopez, Action Graphs and Catalan Numbers, J. Int. Seq. 18 (2015), 15.7.2.
- M. Apagodu, D. Zeilberger, Using the Freshman's dream to prove combinatorial congruences, Am. Math. Mon. 124, No. 7, 597-608 (2017), prop. 2'
- Maciej Bendkowski and Pierre Lescanne, Combinatorics of explicit substitutions, arXiv:1804.03862 [cs.LO], 2018.
- W. Chammam, F. Marcellán and R. Sfaxi, Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation, Linear Algebra Appl. 436(7) (2012), 2105-2116.
- Joel E. Cohen, Variance Functions of Asymptotically Exponentially Increasing Integer Sequences Go Beyond Taylor's Law, J. Int. Seq., Vol. 25 (2022), Article 22.9.3.
- Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, 18 (2015), Article 15.5.8.
- Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
- Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
- Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
- Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.
- I. Pak, Partition identities and geometric bijections, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.
- Hao Pan and Zhi-Wei Sun, A combinatorial identity with application to Catalan numbers, arXiv:math/0509648 [math.CO], 2005-2006.
- Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
- Kevin Topley, Computationally Efficient Bounds for the Sum of Catalan Numbers, arXiv:1601.04223 [math.CO], 2016.
Crossrefs
Programs
-
Magma
[(&+[Catalan(k): k in [0..n]]): n in [0..40]]; // G. C. Greubel, Jun 30 2024
-
Maple
a:= proc(n) option remember; `if`(n<2, n+1, ((5*n-1)*a(n-1)-(4*n-2)*a(n-2))/(n+1)) end: seq(a(n), n=0..30); # Alois P. Heinz, May 18 2013 A014137List := proc(m) local A, P, n; A := [1]; P := [1]; for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-n]]); A := [op(A), P[-1]] od; A end: A014137List(30); # Peter Luschny, Mar 26 2022 -
Mathematica
Table[Sum[(2k)!/(k!)^2/(k+1),{k,0,n}],{n,0,30}] (* Alexander Adamchuk, Jul 11 2006 *) Accumulate[CatalanNumber[Range[0,30]]] (* Harvey P. Dale, May 08 2012 *) a[ n_] := SeriesCoefficient[ (1 - (1 - 4 x)^(1/2)) / (2 x (1 - x)), {x, 0, n}]; (* Michael Somos, Oct 24 2015 *) Table[(1 + CatalanNumber[n] (3 (n + 1) Hypergeometric2F1[1, -n, 1/2 - n, 1/4] - 4 n - 2))/2, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *) -
PARI
Vec((1-(1-4*x)^(1/2))/(2*x*(1-x))+O(x^99)) \\ Charles R Greathouse IV, Feb 11 2011
-
PARI
sm(v)={my(s=vector(#v)); s[1]=v[1]; for(n=2, #v, s[n]=v[n]+s[n-1]); s; } C(n)=binomial(2*n, n)/(n+1); sm(vector(66, n, C(n-1))) /* Joerg Arndt, May 04 2013 */ -
Python
from _future_ import division A014137_list, b, s = [], 1, 0 for n in range(10**2): s += b A014137_list.append(s) b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 28 2016
-
Sage
def A014137(): f, c, n = 1, 1, 1 while True: yield f n += 1 c = c * (4*n - 6) // n f = c + f a = A014137() print([next(a) for in range(29)]) # _Peter Luschny, Nov 30 2016
Formula
a(n) = A014138(n-1) + 1.
G.f.: (1 - (1 - 4*x)^(1/2))/(2*x*(1 - x)).
a(n) = Sum_{k=0..n} (2k)!/(k!)^2/(k+1). - Alexander Adamchuk, Jul 11 2006
D-finite with recurrence: (n+1)*a(n) + (1-5*n)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 14 2011
Mathar's formula reduces to 2*(2*n-1)*C(n-1) = (n+1)*C(n), which is a known recurrence of the Catalan numbers, so the conjecture is true. - Peter J. Taylor, Mar 23 2015
Let C(n+1) = binomial(2*n+2,n+1)/(n+2) and H(n) = hypergeometric([1,n+3/2],[n+3],4) then A014137(n) = -(-1)^(2/3) - C(n+1)*H(n) and A014138(n) = -I^(2/3) - C(n+1)*H(n). - Peter Luschny, Aug 09 2012
G.f. (conjecture): Q(0)/(1-x), where Q(k)= 1 + (4*k + 1)*x/(k + 1 - 2*x*(k + 1)*(4*k + 3)/(2*x*(4*k + 3) + (2*k + 3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ 2^(2*n + 2)/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013
0 = a(n)*(16*a(n+1) - 26*a(n+2) + 10*a(n+3)) + a(n+1)*(-14*a(n+1) + 23*a(n+2) - 11*a(n+3)) + a(n+2)*(a(n+2) + a(n+3)) if n >= 0. - Michael Somos, Oct 24 2015
a(n) = (1 + A000108(n)*(3*(n+1)*hypergeom([1,-n], [1/2-n], 1/4) - 4*n - 2))/2. - Vladimir Reshetnikov, Oct 03 2016
G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x * (1 - x) * A(x)^2. - Ilya Gutkovskiy, Jul 25 2021
From Peter Luschny, Nov 16 2022: (Start)
a(n) = C(n)*hypergeom([1, -n - 1], [1/2 - n], 1/4) + 1/2.
a(n) = A358436(n) / C(n). (End)
E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)/2*(3*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx + 1). - Mélika Tebni, Sep 01 2024
Comments