cp's OEIS Frontend

A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

%I A094507 #30 May 12 2018 22:17:12
%S A094507 1,1,1,1,3,1,1,7,5,1,1,19,14,7,1,1,53,46,22,9,1,1,153,150,82,31,11,1,
%T A094507 1,453,495,299,127,41,13,1,1,1367,1651,1087,507,181,52,15,1,1,4191,
%U A094507 5539,3967,1991,781,244,64,17,1,1,13015,18692,14442,7824,3271,1128,316,77,19
%N A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).
%C A094507 Column k=0 is A078481.
%C A094507 Column k=1 is A244236.
%C A094507 Row sums are the Catalan numbers (A000108).
%H A094507 Alois P. Heinz, <a href="/A094507/b094507.txt">Rows n = 0..150, flattened</a>
%H A094507 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%F A094507 G.f.: G=G(t, z) satisfies the equation z(1+z-tz)G^2-(1+z+z^2-tz-tz^2)G+1+z-tz=0.
%e A094507 T(3,0) = 3 because UDUUDD, UUDDUD and UUUDDD are the only Dyck paths of semilength 3 and having no UDUD in them.
%e A094507 Triangle begins:
%e A094507      1;
%e A094507      1;
%e A094507      1,    1;
%e A094507      3,    1,    1;
%e A094507      7,    5,    1,    1;
%e A094507     19,   14,    7,    1,   1;
%e A094507     53,   46,   22,    9,   1,   1;
%e A094507    153,  150,   82,   31,  11,   1,  1;
%e A094507    453,  495,  299,  127,  41,  13,  1,  1;
%e A094507   1367, 1651, 1087,  507, 181,  52, 15,  1, 1;
%e A094507   4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1;
%p A094507 b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p A094507      `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])
%p A094507       +b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
%p A094507     end:
%p A094507 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
%p A094507 seq(T(n), n=0..15);  # _Alois P. Heinz_, Jun 02 2014
%t A094507 b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 2, 4, 2}[[t]]] + b[x-1, y-1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1] ]; Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, Apr 29 2015, after _Alois P. Heinz_ *)
%Y A094507 Cf. A078481, A000108, A102405 (the same for DUDU), A243752, A243753, A244236.
%Y A094507 T(2n,n) gives A304361.
%K A094507 nonn,tabf
%O A094507 0,5
%A A094507 _Emeric Deutsch_, Jun 05 2004