

A162984


Number of Dyck paths with no UUU's and no DDD's of semilength n and having k UUDUDD's (0<=k<=floor(n/3); U=(1,1), D=(1,1)).


3



1, 1, 2, 3, 1, 6, 2, 12, 5, 25, 11, 1, 53, 26, 3, 114, 62, 9, 249, 148, 25, 1, 550, 355, 69, 4, 1227, 853, 189, 14, 2760, 2057, 509, 46, 1, 6253, 4973, 1359, 145, 5, 14256, 12050, 3600, 446, 20, 32682, 29256, 9484, 1334, 75, 1, 75293, 71154, 24870, 3914, 265, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

T(n,k) is the number of weighted lattice paths in B(n) having k peaks. The members of B(n) are paths of weight n that start at (0,0), end on but never go below the horizontal axis, and whose steps are of the following four kinds: an (1,0)step with weight 1, an (1,0)step with weight 2, a (1,1)step with weight 2, and a (1,1)step with weight 1. The weight of a path is the sum of the weights of its steps. A peak is a (1,1)step followed by a (1,1)step. Example: T(7,2)=3. Indeed, denoting by h (H) the (1,0)step of weight 1 (2), and U=(1,1), D=(1,1), we have hUDUD, UDhUD, and UDUDh.
Number of entries in row n is 1+floor(n/3).


LINKS



FORMULA

G.f.: G=G(t,z) satisfies G = 1 + zG + z^2*G + z^3*(G1+t)G.
Sum of entries in row n = A004148(n+1).
Sum(k*T(n,k), k=0..floor(n/3)) = A110320(n2).


EXAMPLE

T(4,1) = 2 because we have UDUUDUDD and UUDUDDUD.
Triangle starts:
1;
1;
2;
3, 1;
6, 2;
12, 5;
25, 11, 1;
53, 26, 3;


MAPLE

G := ((1zz^2+z^3t*z^3sqrt(12*zz^22*t*z^3z^42*z^5+z^6+2*t*z^4+2*t*z^52*t*z^6+t^2*z^6))*1/2)/z^3: Gser := simplify(series(G, z = 0, 20)): for n from 0 to 16 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 16 do seq(coeff(P[n], t, j), j = 0 .. floor((1/3)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x or t=9, 0,
`if`(x=0, 1, expand(b(x1, y+1, [2, 3, 9, 5, 3, 2, 2, 2][t])+
`if`(t=6, z, 1) *b(x1, y1, [8, 8, 4, 7, 6, 7, 9, 7][t]))))
end:
T:= n> (p> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):


MATHEMATICA

b[x_, y_, t_] := b[x, y, t] = If[y<0  y>x  t == 9, 0, If[x == 0, 1, Expand[b[x1, y+1, {2, 3, 9, 5, 3, 2, 2, 2}[[t]] ] + If[t == 6, z, 1]*b[x1, y1, {8, 8, 4, 7, 6, 7, 9, 7}[[t]] ]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 20}] // Flatten (* JeanFrançois Alcover, May 27 2015, after Alois P. Heinz *)


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



