A155587 -id:A155587 - cp's OEIS frontend

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

N. J. A. Sloane

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

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.

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

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

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

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

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

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

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

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

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

A166588 Partial sums of A097331; binomial transform of A166587.

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 5, 10, 10, 24, 24, 66, 66, 198, 198, 627, 627, 2057, 2057, 6919, 6919, 23715, 23715, 82501, 82501, 290513, 290513, 1033413, 1033413, 3707853, 3707853, 13402698, 13402698, 48760368, 48760368, 178405158, 178405158, 656043858

Offset: 0

Paul Barry, Oct 17 2009

Hankel transform is A131713. The Hankel transform of the sequence 1,1,2,2,... is A128017(n+3). A155587 doubled.

G. C. Greubel, Table of n, a(n) for n = 0..1000

CoefficientList[Series[(1+2*x-Sqrt[1-4*x^2])/(2*x*(1-x)), {x, 0, 40}], x] (* Vaclav Kotesovec, Feb 08 2014 *)

G.f.: (1+2x-sqrt(1-4x^2))/(2x(1-x))=((1+x^2*c(x^2))/(1-x)-1)/x, c(x) the g.f. of A000108.
a(n) = Sum_{k=0..n} C(n,k)*A166587(k).
Conjecture: (-n-1)*a(n) + (n+1)*a(n-1) + 4*(n-2)*a(n-2) + 4*(-n+2)*a(n-3) = 0. - R. J. Mathar, Nov 15 2012
a(n) ~ 2^(n+1/2) * (3-(-1)^n) / (3 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 08 2014

A155586 A modified Catalan sequence array.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 2, 1, 1, 1, 14, 5, 2, 1, 1, 1, 42, 14, 5, 2, 1, 1, 1, 132, 42, 14, 5, 2, 1, 1, 1, 429, 132, 42, 14, 5, 2, 1, 1, 1, 1430, 429, 132, 42, 14, 5, 2, 1, 1, 1, 4862, 1430, 429, 132, 42, 14, 5, 2, 1, 1, 1, 16796, 4862, 1430, 429, 132, 42, 14, 5, 2, 1, 1

Offset: 0

Paul Barry, Jan 24 2009

Row sums are in A155587. Stieltjes associate array to A091491.

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins
  1;
  1,    1;
  1,    1,   1;
  1,    2,   1,   1;
  1,    5,   2,   1,  1;
  1,   14,   5,   2,  1,  1;
  1,   42,  14,   5,  2,  1, 1;
  1,  132,  42,  14,  5,  2, 1, 1;
  1,  429, 132,  42, 14,  5, 2, 1, 1;
  1, 1430, 429, 132, 42, 14, 5, 2, 1, 1;
  ...

Cf. A000108, A091491, A155587.

T(n,k) = [k <= n] * if(k=0, 1, A000108(n-k)) for 0 <= k <= n, where [ ] is the Iverson bracket.

Bivariate o.g.f.: 1/(1 - x) + c(x) * x*y/(1 - x*y), where c(x) is the o.g.f. of A000108. - Petros Hadjicostas, Aug 03 2020

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3

Offset: 1

Gus Wiseman, Nov 22 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Positions of first appearances are A014137.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
Positions of 2's are A155587, indices of A020988.
The standard ranking of the ordered tree is A358523.
Nodes of the ordered tree are counted by A358551, standard A358372.
For standard instead of binary encoding we have A358379.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A057122, A358373, A358505, A358524.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[Depth[bint[k]]-1,{k,Select[Range[0,1000],binbalQ]}]

A377168 a(0) = 1, for n > 0 a(n) is defined by a recurrence with brackets matching the n-th Dyck word in lexicographic order, see comments for more details.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 2, 2, 2, 4, 3, 3, 3, 3, 3, 2, 3, 1, 1, 3, 1, 1, 1, 5, 4, 4, 4, 4, 4, 3, 4, 2, 2, 4, 2, 2, 2, 4, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 2, 4, 3, 2, 3, 3, 2, 3, 2, 1, 2, 2, 1, 2, 1, 6, 5, 5, 5, 5, 5, 4, 5, 3, 3, 5, 3, 3, 3, 5, 4, 4, 4, 4, 5, 4, 3

Offset: 0

John Tyler Rascoe, Oct 18 2024

The transformation from a Dyck word or well-formed bracket expression into a recurrence formula is defined by the ordered steps, "()" -> "(k)" where k is the number of pairs of outer brackets inclosing the brackets in question, then ")(" -> ")+(", and finally "(" -> "a(".

For k > 1, the first occurrence of k occurs at A155587(k)-1.

			For n = 53 the 53rd Dyck word in lexicographic order is 1110010010 or ((())())() written as a well-formed bracket expression. The first adjacent pair of closed brackets is twice nested, the second pair once, and the last pair is open; giving (((2))(1))(0). Next "+" is added in between each pair of adjacent opposite brackets ")(", and finally "a" is appended to the left of each right bracket "(", yielding the formula a(53) = a(a(a(2)) + a(1)) + a(0).
The formulas for a(n) begin:
 n | n-th Dyck word | a(n)
 0        *           1
 1        ()          a(0)
 2       ()()         a(0)+a(0)
 3       (())         a(a(1))
 4      ()()()        a(0)+a(0)+a(0)
 5      ()(())        a(0)+a(a(1))
 6      (())()        a(a(1))+a(0)
 7      (()())        a(a(1)+a(1))
 8      ((()))        a(a(a(2)))
 9     ()()()()       a(0)+a(0)+a(0)+a(0)
 10    ()()(())       a(0)+a(0)+a(a(1))
 ...

Cf. A063171 (Dyck words in lexicographic order).

Cf. A000108, A014486, A155587.

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen():
    return #from Chai Wah Wu, see A014486
def A377168_list(maxn):
    A = [1]
    D = list(islice(A014486_gen(),maxn+1))
    for n in range(1,maxn+1):
        c,c2 = 0,0
        y = bin(D[n])[2:].replace("1","u").replace("0","v")
        z = y
        for i in range(1,len(y)):
            if y[i] == "u":
                c += 1
                if y[i-1] == "v":
                    z = z[:i+c2] + '+' + z[i+c2:]
                    c2 += 1
            else:
                if y[i-1] == "u":
                    z = z[:i+c2] + str(c) + z[i+c2:]
                    c2 += (len(str(c)))
                c -= 1
        A.append(eval(z.replace("u","A[").replace("v","]")))
    return(A)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A166588 Partial sums of A097331; binomial transform of A166587.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A155586 A modified Catalan sequence array.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A377168 a(0) = 1, for n > 0 a(n) is defined by a recurrence with brackets matching the n-th Dyck word in lexicographic order, see comments for more details.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python