A162984 - OEIS

%I #15 May 27 2015 09:37:19

%S 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,

%T 4,1227,853,189,14,2760,2057,509,46,1,6253,4973,1359,145,5,14256,

%U 12050,3600,446,20,32682,29256,9484,1334,75,1,75293,71154,24870,3914,265,6

%N 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)).

%C 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.

%C Number of entries in row n is 1+floor(n/3).

%H Alois P. Heinz, <a href="/A162984/b162984.txt">Rows n = 0..250, flattened</a>

%H M. Bona and A. Knopfmacher, <a href="http://dx.doi.org/10.1007/s00026-010-0060-7">On the probability that certain compositions have the same number of parts</a>, Ann. Comb., 14 (2010), 291-306.

%F G.f.: G=G(t,z) satisfies G = 1 + zG + z^2*G + z^3*(G-1+t)G.

%F Sum of entries in row n = A004148(n+1).

%F T(n,0) = A162985(n).

%F Sum(k*T(n,k), k=0..floor(n/3)) = A110320(n-2).

%e T(4,1) = 2 because we have UDUUDUDD and UUDUDDUD.

%e Triangle starts:

%e 1;

%e 1;

%e 2;

%e 3,   1;

%e 6,   2;

%e 12,  5;

%e 25, 11, 1;

%e 53, 26, 3;

%p G := ((1-z-z^2+z^3-t*z^3-sqrt(1-2*z-z^2-2*t*z^3-z^4-2*z^5+z^6+2*t*z^4+2*t*z^5-2*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

%p # second Maple program:

%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x or t=9, 0,

%p      `if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 9, 5, 3, 2, 2, 2][t])+

%p      `if`(t=6, z, 1) *b(x-1, y-1, [8, 8, 4, 7, 6, 7, 9, 7][t]))))

%p     end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):

%p seq(T(n), n=0..20);  # _Alois P. Heinz_, Jun 10 2014

%t b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x || t == 9, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 3, 9, 5, 3, 2, 2, 2}[[t]] ] + If[t == 6, z, 1]*b[x-1, y-1, {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 (* _Jean-François Alcover_, May 27 2015, after _Alois P. Heinz_ *)

%Y Cf. A004148, A110320, A162985, A246177.

%K nonn,tabf

%O 0,3

%A _Emeric Deutsch_, Oct 11 2009