A135328 - OEIS

%I #17 Feb 14 2021 13:03:32

%S 1,1,2,4,1,10,4,29,12,1,90,36,6,290,114,24,1,960,376,86,8,3246,1272,

%T 303,40,1,11164,4380,1074,168,10,38934,15293,3838,660,60,1,137358,

%U 54012,13812,2528,290,12,489341,192612,50013,9584,1265,84,1

%N 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 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 Alois P. Heinz, <a href="/A135328/b135328.txt">Rows n = 0..200, flattened</a>

%H 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 From _Emeric Deutsch_, Dec 14 2007: (Start)

%F 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 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 Triangle begins:

%e      1;

%e      1;

%e      2;

%e      4    1;

%e     10    4;

%e     29   12   1;

%e     90   36   6;

%e    290  114  24  1;

%e    960  376  86  8;

%e   3246 1272 303 40 1;

%e   ...

%e 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 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 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 # third Maple program:

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

%p       `if`(x=0, 1, expand(b(x-1, y+1, `if`(y=1, 1, 0))*

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

%p     end:

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

%p seq(T(n), n=0..14);  # _Alois P. Heinz_, Nov 16 2019

%t b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0,

%t      If[x == 0, 1, Expand[b[x - 1, y + 1, If[y == 1, 1, 0]]*

%t      If[t == 3, z, 1]] + b[x - 1, y - 1, If[1 <= t <= 2, t + 1, 0]]]];

%t T[n_] := CoefficientList[b[2n, 0, 0], z];

%t T /@ Range[0, 14] // Flatten (* _Jean-François Alcover_, Feb 14 2021, after _Alois P. Heinz_ *)

%Y Cf. A000108, A135334.

%K nonn,tabf

%O 0,3

%A _N. J. A. Sloane_, Dec 07 2007

%E Edited and extended by _Emeric Deutsch_, Dec 14 2007