A014138 Partial sums of (Catalan numbers starting 1, 2, 5, ...).

0, 1, 3, 8, 22, 64, 196, 625, 2055, 6917, 23713, 82499, 290511, 1033411, 3707851, 13402696, 48760366, 178405156, 656043856, 2423307046, 8987427466, 33453694486, 124936258126, 467995871776, 1757900019100

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Number of paths starting from the root in all ordered trees with n+1 edges (a path is a nonempty tree with no vertices of outdegree greater than 1). Example: a(2)=8 because the five trees with three edges have altogether 1+0+2+2+3=8 paths hanging from the roots. - Emeric Deutsch, Oct 20 2002

a(n) is the sum of the mean maximal pyramid size over all Dyck (n+1)-paths. Also, a(n) = sum of the mean maximal sawtooth size over all Dyck (n+1)-paths. A pyramid (resp. sawtooth) in a Dyck path is a subpath of the form U^k D^k (resp. (UD)^k) with k>=1 and k is its size. For example, the maximal pyramids in the Dyck path uUUDD|UD|UDdUUDD are indicated by uppercase letters (and separated by a vertical bar). Their sizes are 2,1,1,2 left to right and the mean maximal pyramid size of the path is 6/4 = 3/2. Also, the mean maximal sawtooth size of this path is (1+2+1)/3 = 4/3. - David Callan, Jun 07 2006

p^2 divides a(p-1) for prime p of form p=6k+1 (A002476(k)). - Alexander Adamchuk, Jul 03 2006

p^2 divides a(p^2-1) for prime p>3. p^2 divides a(p^3-1) for prime p=7,13,19,... prime p in the form p=6k+1. - Alexander Adamchuk, Jul 03 2006

Row sums of triangle A137614. - Gary W. Adamson, Jan 30 2008

Equals INVERTi transform of A095930: (1, 4, 15, 57, 220, 859, ...). - Gary W. Adamson, May 15 2009

a(n) < A000108(n+1), therefore A176137(n) <= 1. - Reinhard Zumkeller, Apr 10 2010

a(n) is also the sum of the numbers in Catalan's triangle (A009766) from row 0 to row n. - Patrick Labarque, Jul 27 2010

Equals the Catalan sequence starting (1, 1, 2, ...) convolved with A014137 starting (1, 2, 4, 9, ...). - Gary W. Adamson, May 20 2013

p divides a((p-3)/2) for primes {11,23,47,59,...} = A068231 primes congruent to 11 mod 12. - Alexander Adamchuk, Dec 27 2013

a(n) is the number of parking functions of size n avoiding the patterns 132, 213, and 231. - Lara Pudwell, Apr 10 2023

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000(terms 0 to 200 computed by T. D. Noe)
• Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
• Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv preprint arXiv:1107.5490 [math.CO], 2011.
• S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
• Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.
• Kevin Topley, Computationally Efficient Bounds for the Sum of Catalan Numbers, arXiv:1601.04223 [math.CO], 2016.

Crossrefs

Cf. A000108, A002476, A005554, A068231, A095930, A137614, A155587.

Programs

Haskell

a014138 n = a014138_list !! n
a014138_list = scanl1 (+) a000108_list  -- Reinhard Zumkeller, Mar 01 2013

Maple

a:=n->sum((binomial(2*j,j)/(j+1)),j=1..n): seq(a(n), n=0..24); # Zerinvary Lajos, Dec 01 2006
# Second program:
A014138 := series(exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)*(3/2*int(BesselI(0, 2*x)*exp(x), x) - 1/2), x = 0, 26):
seq(n!*coeff(A014138, x, n), n = 0 .. 24); # Mélika Tebni, Aug 31 2024

Mathematica

Table[Sum[(2k)!/k!/(k+1)!,{k,1,n}],{n,1,70}] (* Alexander Adamchuk, Jul 03 2006 *)
Join[{0},Accumulate[CatalanNumber[Range[30]]]] (* Harvey P. Dale, Jan 25 2013 *)
CoefficientList[Series[(1 - 2 x - (1 - 4 x)^(1/2))/(2 x (1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 21 2015 *)
a[0] := 0; a[n_] := Sum[CatalanNumber[k], {k, 1, n}]; Table[a[n], {n,0,50}] (* G. C. Greubel, Jan 14 2017 *)

PARI

Vec((1-2*x-(1-4*x)^(1/2))/(2*x*(1-x))) \\ Charles R Greathouse IV, Feb 11 2011

Python

from _future_ import division
A014138_list, b, s = [0], 1, 0
for n in range(1,10**2):
    s += b
    A014138_list.append(s)
    b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 28 2016

Formula

a(n) = A014137(n)-1.

G.f.: (1-2*x-sqrt(1-4x))/(2x(1-x)) = (C(x)-1)/(1-x) where C(x) is the generating function for the Catalan numbers. - Rocio Blanco, Apr 02 2007

a(n) = Sum_{k=1..n} A000108(k). - Alexander Adamchuk, Jul 03 2006

Binomial transform of A005554: (1, 2, 3, 6, 13, 30, 72, ...). - Gary W. Adamson, Nov 23 2007

D-finite with recurrence: (n+1)*a(n) + (1-5n)*a(n-1) + 2*(2n-1)*a(n-2) = 0. - R. J. Mathar, Dec 14 2011

Equals the Catalan sequence starting (1, 1, 2, ...) convolved with A014137 starting (1, 2, 4, 9, ...). - Gary W. Adamson, May 20 2013

G.f.: 1/x - G(0)/(1-x)/x, where G(k) = 1 - x/(1 - x/(1 - x/(1 - x/G(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013

G.f.: 1/x - T(0)/(2*x*(1-x)), where T(k) = 2*x*(2*k+1)+ k+2 - 2*x*(k+2)*(2*k+3)/T(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2013

a(n) ~ 2^(2*n+2)/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013

a(n) = Sum_{i+jA000108. - Yuchun Ji, Jan 10 2019

E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)*(3/2*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx - 1/2). - Mélika Tebni, Aug 31 2024

Extensions

Edited by Max Alekseyev, Sep 13 2009 (including adding an initial 0)

Definition edited by N. J. A. Sloane, Oct 03 2009