A261003 - OEIS

%I #29 Apr 15 2024 18:28:39

%S 1,2,5,15,48,160,549,1924,6851,24700,89945,330239,1220884,4540128,

%T 16968958,63701573,240059998,907760348,3443048256,13094812968,

%U 49925646786,190772846082,730451716847,2802033270234,10767028435468,41438212118088,159711845145544,616393788920923,2381898673172602

%N a(n) = A136439(n) + Catalan(n).

%C 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.

%C a(n) is the total number of levels visited by all Dyck paths of semilength n. - _Alois P. Heinz_, Apr 14 2024

%H Alois P. Heinz, <a href="/A261003/b261003.txt">Table of n, a(n) for n = 0..650</a>

%H N. Dershowitz and C. Rinderknecht, <a href="http://www.jstor.org/stable/10.4169/math.mag.88.3.187">The Average Height of Catalan Trees by Counting Lattice Paths</a>, Math. Mag., 88 (No. 3, 2015), 187-195.

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

%p # Maple code for Equations (1) and (2) of Dershowitz and Rinderknecht (2015).

%p 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;

%p S1:=n->add(H(n,h),h=1..n+1); [seq(S1(n),n=0..30)];

%t 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}}]];

%t a[n_] :=  b[2n, 0, 0] + CatalanNumber[n];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Apr 15 2023, after _Alois P. Heinz_ in A136439 *)

%Y Cf. A000108, A136439.

%Y Row sums of A371928.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Aug 12 2015