cp's OEIS Frontend

A135328 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k UDDU's starting at level 1.

%I A135328 #17 Feb 14 2021 13:03:32
%S A135328 1,1,2,4,1,10,4,29,12,1,90,36,6,290,114,24,1,960,376,86,8,3246,1272,
%T A135328 303,40,1,11164,4380,1074,168,10,38934,15293,3838,660,60,1,137358,
%U A135328 54012,13812,2528,290,12,489341,192612,50013,9584,1265,84,1
%N A135328 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k UDDU's starting at level 1.
%C A135328 Each of rows 0, 1, 2 has one term; row n (n >= 1) has ceiling(n/2) terms. Row sums are the Catalan numbers (A000108). Column 0 yields A135334. - _Emeric Deutsch_, Dec 14 2007
%H A135328 Alois P. Heinz, <a href="/A135328/b135328.txt">Rows n = 0..200, flattened</a>
%H A135328 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 A135328 From _Emeric Deutsch_, Dec 14 2007: (Start)
%F A135328 T(n,k) = 2*((k+1)/(n+1))*Sum_{j=k..floor((n-1)/2)} (-1)^(j-k)*binomial(j+1, k+1)*binomial(2n-2j-1, n) (n >= 1).
%F A135328 G.f.: 1 + z*C^2/(1 + (1-t)*z^2*C^2), where C = (1-sqrt(1-4z))/(2z) is the g.f. of the Catalan numbers (A000108). (End)
%e A135328 Triangle begins:
%e A135328      1;
%e A135328      1;
%e A135328      2;
%e A135328      4    1;
%e A135328     10    4;
%e A135328     29   12   1;
%e A135328     90   36   6;
%e A135328    290  114  24  1;
%e A135328    960  376  86  8;
%e A135328   3246 1272 303 40 1;
%e A135328   ...
%e A135328 T(4,1)=4 because we have UDU(UDDU)D, U(UDDU)DUD, U(UDDU)UDD and UUD(UDDU)D (the UDDU's starting at level 1 are shown between parentheses).
%p A135328 T:=proc(n,k) options operator, arrow: (2*k+2)*(sum((-1)^(j-k)*binomial(j+1, k+1)*binomial(2*n-2*j-1,n),j=k..floor((1/2)*n-1/2)))/(n+1) end proc: 1; for n to 13 do seq(T(n,k),k=0..ceil((n-2)*1/2)) end do; # yields sequence in triangular form; _Emeric Deutsch_, Dec 14 2007
%p A135328 G:=1+z*C^2/(1+(1-t)*z^2*C^2): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,16)): for n from 0 to 13 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; for n to 13 do seq(coeff(P[n],t,j),j=0..floor((n-1)*1/2)) end do; # yields sequence in triangular form; _Emeric Deutsch_, Dec 14 2007
%p A135328 # third Maple program:
%p A135328 b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p A135328       `if`(x=0, 1, expand(b(x-1, y+1, `if`(y=1, 1, 0))*
%p A135328       `if`(t=3, z, 1))+b(x-1, y-1, `if`(t in [1, 2], t+1, 0))))
%p A135328     end:
%p A135328 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
%p A135328 seq(T(n), n=0..14);  # _Alois P. Heinz_, Nov 16 2019
%t A135328 b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0,
%t A135328      If[x == 0, 1, Expand[b[x - 1, y + 1, If[y == 1, 1, 0]]*
%t A135328      If[t == 3, z, 1]] + b[x - 1, y - 1, If[1 <= t <= 2, t + 1, 0]]]];
%t A135328 T[n_] := CoefficientList[b[2n, 0, 0], z];
%t A135328 T /@ Range[0, 14] // Flatten (* _Jean-François Alcover_, Feb 14 2021, after _Alois P. Heinz_ *)
%Y A135328 Cf. A000108, A135334.
%K A135328 nonn,tabf
%O A135328 0,3
%A A135328 _N. J. A. Sloane_, Dec 07 2007
%E A135328 Edited and extended by _Emeric Deutsch_, Dec 14 2007