A132891 Sum of the heights of all left factors of Dyck paths of length n.

1, 3, 6, 14, 28, 61, 121, 257, 508, 1065, 2103, 4372, 8634, 17842, 35254, 72524, 143396, 293968, 581630, 1189102, 2354168, 4802331, 9512984, 19370764, 38391332, 78056544, 154773135, 314281350, 623427154, 1264546021, 2509378855, 5085153822, 10094528146

Offset: 1

Author

Emeric Deutsch, Sep 08 2007

Keywords

• nonn

Comments

See A132890 for the statistic "height" on left factors of Dyck paths.

Examples

			a(4)=14 because the six left factors of Dyck paths of length 4 are UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, having heights 1, 2, 2, 2, 3 and 4, respectively.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..700
• Toufik Mansour and Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.2.

Crossrefs

Cf. A132890.

Programs

Maple

v := ((1-sqrt(1-4*z^2))*1/2)/z: g := proc (k) options operator, arrow: v^k*(1+v)*(1+v^2)/((1+v^(k+1))*(1+v^(k+2))) end proc: T := proc (n, k) options operator, arrow; coeff(series(g(k), z = 0, 70), z, n) end proc: seq(add(k*T(n, k), k = 1 .. n), n = 1 .. 30);

Mathematica

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y > 0, b[x - 2, y - 1, k], 0] + b[x - 2, y + 1, Max[y + 1, k]]];
T[n_] := Table[Coefficient[b[2n, 0, 0], z, i], {i, 1, n}];
a[n_] := T[n].Range[n];
Array[a, 33] (* Jean-François Alcover, Nov 10 2020, after Alois P. Heinz in A132890 *)

Formula

a(n) = Sum_{k=1..n} k * A132890(n,k).