cp's OEIS Frontend

A132890 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have height k (1 <= k <= n).

%I A132890 #34 Dec 19 2022 10:31:51
%S A132890 1,1,1,1,1,1,1,3,1,1,1,3,4,1,1,1,7,5,5,1,1,1,7,13,6,6,1,1,1,15,18,20,
%T A132890 7,7,1,1,1,15,39,26,27,8,8,1,1,1,31,57,73,35,35,9,9,1,1,1,31,112,99,
%U A132890 109,44,44,10,10,1,1,1,63,169,253,152,154,54,54,11,11,1,1
%N A132890 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have height k (1 <= k <= n).
%C A132890 Sum of terms in row n = binomial(n, floor(n/2)) = A001405(n).
%C A132890 T(n,2) = A052551(n-2) (n >= 2).
%C A132890 T(n,3) = A005672(n) = Fibonacci(n+1) - 2^floor(n/2).
%C A132890 Sum_{k=1..n} k*T(n,k) = A132891(n).
%H A132890 Alois P. Heinz, <a href="/A132890/b132890.txt">Rows n = 1..141, flattened</a>
%H A132890 Steven R. Finch, <a href="https://arxiv.org/abs/1802.04615">How far might we walk at random?</a>, arXiv:1802.04615 [math.HO], 2018.
%H A132890 R. Kemp, <a href="http://dx.doi.org/10.1016/0012-365X(81)90235-1">On the average depth of a prefix of the Dycklanguage D_1</a>, Discrete Math., 36, 1981, 155-170.
%H A132890 Toufik Mansour, 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 A132890 The g.f. of column k is g(k, z) = v^k*(1+v)*(1+v^2)*/((1+v^(k+1))*(1+v^(k+2))), where v = (1-sqrt(1-4*z^2))/(2*z). (Obtained as the difference G(k,z)-G(k-1,z), where G(k,z) is given in the R. Kemp reference (p. 159).)
%e A132890 T(5,3)=4 because we have UDUUU, UUDUU, UUUDD and UUUDU, where U=(1,1) and D=(1,-1).
%e A132890 Triangle starts:
%e A132890   1;
%e A132890   1, 1;
%e A132890   1, 1, 1;
%e A132890   1, 3, 1, 1;
%e A132890   1, 3, 4, 1; 1;
%e A132890   1, 7, 5, 5, 1, 1;
%p A132890 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, 50), z, n) end proc: for n from 0 to 12 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form
%p A132890 # second Maple program:
%p A132890 b:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y>0,
%p A132890       b(x-2, y-1, k), 0)+ b(x-2, y+1, max(y+1, k)))
%p A132890     end:
%p A132890 T:= n-> (p-> seq(coeff(p, z, i), i=1..n))(b(2*n, 0$2)):
%p A132890 seq(T(n), n=1..16);  # _Alois P. Heinz_, Sep 05 2017
%t A132890 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 A132890 T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n}]][b[2n, 0, 0]];
%t A132890 Table[T[n], {n, 1, 16}] // Flatten (* _Jean-François Alcover_, Apr 01 2018, after _Alois P. Heinz_ *)
%Y A132890 Cf. A001405, A052551, A005672, A132891, A068914.
%K A132890 nonn,tabl
%O A132890 1,8
%A A132890 _Emeric Deutsch_, Sep 08 2007
%E A132890 Keyword tabl added by _Michel Marcus_, Apr 09 2013