cp's OEIS Frontend

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

%I A132891 #19 Dec 19 2022 10:32:01
%S A132891 1,3,6,14,28,61,121,257,508,1065,2103,4372,8634,17842,35254,72524,
%T A132891 143396,293968,581630,1189102,2354168,4802331,9512984,19370764,
%U A132891 38391332,78056544,154773135,314281350,623427154,1264546021,2509378855,5085153822,10094528146
%N A132891 Sum of the heights of all left factors of Dyck paths of length n.
%C A132891 See A132890 for the statistic "height" on left factors of Dyck paths.
%H A132891 Alois P. Heinz, <a href="/A132891/b132891.txt">Table of n, a(n) for n = 1..700</a>
%H A132891 Toufik Mansour and Gokhan Yilidirim, <a href="https://www.doi.org/10.3906/mat-1901-86">Longest increasing subsequences in involutions avoiding patterns of length three</a>, Turkish Journal of Mathematics (2019), Section 2.2.
%F A132891 a(n) = Sum_{k=1..n} k * A132890(n,k).
%e A132891 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.
%p A132891 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);
%t A132891 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 A132891 T[n_] := Table[Coefficient[b[2n, 0, 0], z, i], {i, 1, n}];
%t A132891 a[n_] := T[n].Range[n];
%t A132891 Array[a, 33] (* _Jean-François Alcover_, Nov 10 2020, after _Alois P. Heinz_ in A132890 *)
%Y A132891 Cf. A132890.
%K A132891 nonn
%O A132891 1,2
%A A132891 _Emeric Deutsch_, Sep 08 2007