A191315 Sum of the heights of all dispersed Dyck paths of length n (i.e., of Motzkin paths of length n with no (1,0) steps at positive heights).

0, 0, 1, 2, 6, 11, 27, 50, 115, 216, 481, 913, 1992, 3809, 8192, 15748, 33512, 64685, 136546, 264422, 554686, 1077055, 2248105, 4375221, 9095238, 17735812, 36745504, 71776633, 148288346, 290092160, 597876033, 1171153370, 2408702852, 4723840544, 9697826974, 19038878297

Offset: 0

Author

Emeric Deutsch, May 31 2011

Keywords

• nonn

Comments

a(n) = Sum_{k>=0} k * A191314(n,k).

Examples

			a(4)=6 because the sum of the heights of the paths HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD is 0+1+1+1+1+2=6; here U=(1,1), H=(1,0), D=(1,-1).
		

Links

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

Crossrefs

Cf. A108299, A191314.

Programs

Maple

F[0] := 1: F[1] := 1-z: for k from 2 to 36 do F[k] := sort(expand(F[k-1]-z^2*F[k-2])) end do: G := sum(j*z^(2*j)/(F[j]*F[j+1]), j = 0 .. 34): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, n), n = 0 .. 35);
# second Maple program:
b:= proc(x, y, m) option remember;
      `if`(y>x or y<0, 0, `if`(x=0, m, b(x-1, y-1, m)+
      `if`(y=0, b(x-1, y, m), 0)+b(x-1, y+1, max(m, y+1))))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 13 2017

Mathematica

b[x_, y_, m_] := b[x, y, m] = If[y > x || y < 0, 0, If[x == 0, m, b[x - 1, y - 1, m] + If[y == 0, b[x - 1, y, m], 0] + b[x - 1, y + 1, Max[m, y + 1]]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 16 2017, after Alois P. Heinz *)

Formula

G.f.: G(z) = Sum_{j>=0}(jz^(2j)/(F(j)F(j+1))), where F(k) are polynomials in z defined by F(0)=1, F(1)=1-z, F(k)=F(k-1)-z^2*F(k-2) for k>=2. The coefficients of these polynomials form the triangle A108299.