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,3

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, 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.

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+j<n} C(i)*C(j), where C = A000108. - Yuchun Ji, Jan 10 2019

Maple

a:=n->sum((binomial(2*j, j)/(j+1)), j=1..n): seq(a(n), n=0..24); # Zerinvary Lajos, Dec 01 2006

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

Prog

(PARI) Vec((1-2*x-(1-4*x)^(1/2))/(2*x*(1-x))) \\ Charles R Greathouse IV, Feb 11 2011
(Haskell)
a014138 n = a014138_list !! n
a014138_list = scanl1 (+) a000108_list  -- Reinhard Zumkeller, Mar 01 2013
(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

Crossrefs

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

Sequence in context: A047926 A192681 A339288 * A099324 A290898 A117420

Adjacent sequences: A014135 A014136 A014137 * A014139 A014140 A014141

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

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

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

Status

approved