A261003 a(n) = A136439(n) + Catalan(n).

1, 2, 5, 15, 48, 160, 549, 1924, 6851, 24700, 89945, 330239, 1220884, 4540128, 16968958, 63701573, 240059998, 907760348, 3443048256, 13094812968, 49925646786, 190772846082, 730451716847, 2802033270234, 10767028435468, 41438212118088, 159711845145544, 616393788920923, 2381898673172602

Offset

0,2

Comments

This is the quantity S_{n-1} as given by a literal reading of Dershowitz and Rinderknecht (2015), Equations (1) and (2). If the lower limit in the right-hand sum in Eq. (1) is changed to "h >= 2", we obtain A136439.

a(n) is the total number of levels visited by all Dyck paths of semilength n. - Alois P. Heinz, Apr 14 2024

Links

Alois P. Heinz, Table of n, a(n) for n = 0..650

N. Dershowitz and C. Rinderknecht, The Average Height of Catalan Trees by Counting Lattice Paths, Math. Mag., 88 (No. 3, 2015), 187-195.

Formula

a(n) = A000108(n) + A136439(n).

Maple

# Maple code for Equations (1) and (2) of Dershowitz and Rinderknecht (2015).
H:=proc(n, h) local b, k; b:=binomial; add(b(2*n, n+1-k*h)-2*b(2*n, n-k*h)+b(2*n, n-1-k*h), k=1..n+1); end;
S1:=n->add(H(n, h), h=1..n+1); [seq(S1(n), n=0..30)];

Mathematica

b[x_, y_, h_] := b[x, y, h] = If[x == 0, h, Sum[If[x+j > y, b[x-1, y-j, Max[h, y-j]], 0], {j, Range[-1, Min[1, y]]~Complement~{0}}]];
a[n_] :=  b[2n, 0, 0] + CatalanNumber[n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 15 2023, after Alois P. Heinz in A136439 *)

Crossrefs

Cf. A000108, A136439.

Row sums of A371928.

Sequence in context: A289589 A071739 A268407 * A365268 A366041 A372532

Adjacent sequences: A261000 A261001 A261002 * A261004 A261005 A261006

Keyword

nonn

Author

N. J. A. Sloane, Aug 12 2015

Status

approved