login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014137 Partial sums of Catalan numbers (A000108). 291

%I

%S 1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,

%T 13402697,48760367,178405157,656043857,2423307047,8987427467,

%U 33453694487,124936258127,467995871777,1757900019101,6619846420553,24987199492705,94520750408709,358268702159069

%N Partial sums of Catalan numbers (A000108).

%C This is also the result of applying the transformation on generating functions A -> 1/((1-x)*(1-x*A)) to the g.f. for the Catalan numbers.

%C p divides a(p)-3 for prime p=3 and p=7,13,19,31,37,43.. = A002476 (Primes of form 6n + 1). p^2 divides a(p^2)-3 for prime p>3. - _Alexander Adamchuk_, Jul 11 2006

%C Prime p divides a(p) for p = {2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...} = A045309 Primes congruent to {0, 2} mod 3; and A045309 Primes p such that x^3 = n (integer) has only one solution mod p. Nonprime numbers n such that n divides a(n) are listed in A128287 = {1, 8, 133, ...}. - _Alexander Adamchuk_, Feb 23 2007

%C For p prime >=5, a(p-1) = 1 or -2 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). For example, with p=5, a(p-1) = 23 = -2 (mod p). - _David Callan_, Nov 29 2007

%C Hankel transform is A010892(n+1). - _Paul Barry_, Apr 24 2009

%C Equals INVERTi transform of A000245: (1, 3, 9, 28,...). - _Gary W. Adamson_, May 15 2009

%C The subsequence of prime partial sums of Catalan numbers begins: a(1) = 2, a(4) = 23, a(6) = 197, a(16) = 48760367, see A121852. - _Jonathan Vos Post_, Feb 10 2010

%C Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1 including two kinds of (1,1). - _Alois P. Heinz_, Oct 14 2015

%C Binomial transform of A086246(n+1) = [1, 1, 1, 2, 4, 9, ...], or, equivalently, of A001006 (Motzkin numbers) with 1 prepended.

%H G. C. Greubel, <a href="/A014137/b014137.txt">Table of n, a(n) for n = 0..1000</a> (terms 0 to 200 by T. D. Noe)

%H G. Alvarez, J. E. Bergner, R. Lopez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bergner/bergner2.html">Action Graphs and Catalan Numbers</a>, J. Int. Seq. 18 (2015) 15.7.2

%H Maciej Bendkowski, Pierre Lescanne, <a href="https://arxiv.org/abs/1804.03862">Combinatorics of explicit substitutions</a>, arXiv:1804.03862 [cs.LO], 2018.

%H W. Chammam, F. Marcellán and R. Sfaxi, <a href="http://dx.doi.org/10.1016/j.laa.2011.10.010">Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation</a>, Linear Algebra Appl. (2011), in press

%H Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.

%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%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 I. Pak, <a href="http://dx.doi.org/10.1090/S0002-9939-04-07031-5">Partition identities and geometric bijections</a>, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.

%H Hao Pan and Zhi-Wei Sun, <a href="http://arxiv.org/abs/math/0509648">A combinatorial identity with application to Catalan numbers</a>, arXiv:math/0509648 [math.CO], 2005-2006.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2

%H Kevin Topley, <a href="http://arxiv.org/abs/1601.04223">Computationally Efficient Bounds for the Sum of Catalan Numbers</a>, arXiv:1601.04223 [math.CO], 2016.

%F a(n) = A014138(n-1) + 1.

%F G.f.: (1-(1-4*x)^(1/2))/(2*x*(1-x)).

%F Sum_{i=1..n} c(i) = Sum_{i=1..n} binomial(2*i-2, i-1)/i = 1/(n-1)! * [n^(n-2) + binomial(n, 2)*n^(n-3) + {8*binomial(n-4, 0) + 19*binomial(n-4, 1) + 24*binomial(n-4, 2) + 14*binomial(n-4, 3) + 3*binomial(n-4, 4)}*n^(n-4) +{18*binomial(n-5, 0) + 82*binomial(n-5, 1) + 229*binomial(n-5, 2) + 323*binomial(n-5, 3) + 244*binomial(n-5, 4) + 95*binomial(n-5, 5) + 15*binomial(n-5, 6)}*n^(n-5) + ... + binomial(n-3, 0)*(n-1)! ] (where c() = Catalan numbers A000108). - _André F. Labossière_, May 17 2004

%F a(n) = Sum_{k=0..n} (2k)!/(k!)^2/(k+1). - _Alexander Adamchuk_, Jul 11 2006

%F Conjecture: (n+1)*a(n)+(1-5*n)*a(n-1) +2*(2*n-1)*a(n-2)=0. - _R. J. Mathar_, Dec 14 2011

%F Mathar's conjecture 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

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

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

%F a(n) ~ 2^(2*n+2)/(3*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Dec 10 2013

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

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

%e 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 + ...

%p a:= proc(n) option remember; `if`(n<2, n+1,

%p ((5*n-1)*a(n-1)-(4*n-2)*a(n-2))/(n+1))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 18 2013

%t Table[Sum[(2k)!/(k!)^2/(k+1),{k,0,n}],{n,0,30}] (* _Alexander Adamchuk_, Jul 11 2006 *)

%t Accumulate[CatalanNumber[Range[0,30]]] (* _Harvey P. Dale_, May 08 2012 *)

%t a[ n_] := SeriesCoefficient[ (1 - (1 - 4 x)^(1/2)) / (2 x (1 - x)), {x, 0, n}]; (* _Michael Somos_, Oct 24 2015 *)

%t 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 *)

%o (PARI) Vec((1-(1-4*x)^(1/2))/(2*x*(1-x))+O(x^99)) \\ _Charles R Greathouse IV_, Feb 11 2011

%o (PARI)

%o sm(v)={my(s=vector(#v)); s[1]=v[1]; for(n=2, #v, s[n]=v[n]+s[n-1]); s; }

%o C(n)=binomial(2*n, n)/(n+1);

%o sm(vector(66, n, C(n-1)))

%o /* _Joerg Arndt_, May 04 2013 */

%o (Python)

%o from __future__ import division

%o A014137_list, b, s = [], 1, 0

%o for n in range(10**2):

%o s += b

%o A014137_list.append(s)

%o b = b*(4*n+2)//(n+2) # _Chai Wah Wu_, Jan 28 2016

%o (Sage)

%o def A014137():

%o f, c, n = 1, 1, 1

%o while True:

%o yield f

%o n += 1

%o c = c * (4*n - 6) // n

%o f = c + f

%o a = A014137()

%o print [a.next() for _ in range(29)] # _Peter Luschny_, Nov 30 2016

%Y Cf. A000108, A000245, A094638, A001246, A033536, A000984, A094639, A006134, A082894, A002897, A079727, A002476, A045309, A128287.

%K nonn,nice,changed

%O 0,2

%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 20 10:57 EST 2018. Contains 317385 sequences. (Running on oeis4.)