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,2

Comments

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

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.

Formula

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

Example

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.

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

Crossrefs

Cf. A132890.

Sequence in context: A356804 A345334 A354294 * A200544 A308448 A055890

Adjacent sequences: A132888 A132889 A132890 * A132892 A132893 A132894

Keyword

nonn

Author

Emeric Deutsch, Sep 08 2007

Status

approved