cp's OEIS Frontend

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

%I A135333 #16 Apr 01 2017 20:31:44
%S A135333 1,1,2,4,1,11,2,1,32,7,2,1,99,22,8,2,1,318,73,26,9,2,1,1051,246,90,30,
%T A135333 10,2,1,3550,844,312,108,34,11,2,1,12200,2936,1096,384,127,38,12,2,1,
%U A135333 42520,10334,3886,1379,462,147,42,13,2,1,149930,36736,13897,4978,1694
%N A135333 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k DUDU's starting at level 1.
%C A135333 Each of rows 0, 1 and 2 contains one entry. Row n contains n-1 entries (n >= 2). Row sums are the Catalan numbers (A000108). Column 0 yields A135339. - _Emeric Deutsch_, Dec 13 2007
%H A135333 Alois P. Heinz, <a href="/A135333/b135333.txt">Rows n = 0..150, flattened</a>
%H A135333 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 A135333 G.f.: 1+zC+z^2*C^3/[1+(1-t)zC], where C=[1-sqrt(1-4z)]/(2z) is the g.f. of the Catalan numbers (A000108). T(n,k) = d(0,k)*c(n-1)+Sum[(-1)^(j-k)*(j+3)binomial(j,k)binomial(2n-j-2,n),j=k..n-2]/(n+1), where c(m) = binomial(2m,m)/(m+1) = A000108(m) is a Catalan number and d(0,k) is the Kronecker symbol. - _Emeric Deutsch_, Dec 13 2007
%e A135333 Triangle begins:
%e A135333 1
%e A135333 1
%e A135333 2
%e A135333 4 1
%e A135333 11 2 1
%e A135333 32 7 2 1
%e A135333 99 22 8 2 1
%e A135333 318 73 26 9 2 1
%e A135333 1051 246 90 30 10 2 1
%e A135333 ...
%e A135333 T(4,1)=2 because we have U(DUDU)UDD and UUD(DUDU)D; T(4,2)=1 because we have U(DU[DU)DU]D (the DUDU's starting at level 1 are shown between parentheses).
%p A135333 G:=1+z*C+z^2*C^3/(1+(1-t)*z*C): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,17)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; 1; for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) end do; # yields sequence in triangular form; _Emeric Deutsch_, Dec 13 2007
%p A135333 # second Maple program:
%p A135333 b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
%p A135333       `if`(y<x, b(x-1, y+1, [1, 3, 1, 3][t])*`if`(t=4, z, 1), 0)+
%p A135333       `if`(y>0, b(x-1, y-1, `if`(y=1, [2, 1, 4, 1][t], 1)), 0)))
%p A135333     end:
%p A135333 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
%p A135333 seq(T(n), n=0..14);  # _Alois P. Heinz_, Sep 28 2015
%t A135333 b[x_, y_, t_] := b[x, y, t] = Expand[If[x == 0, 1, If[y < x, b[x - 1, y + 1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1], 0] + If[y > 0, b[x - 1, y - 1, If[y == 1, {2, 1, 4, 1}[[t]], 1]], 0]]]; T[n_] := Function [p, Table[ Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Feb 14 2016, after _Alois P. Heinz_ *)
%Y A135333 Cf. A000108, A135339.
%K A135333 nonn,tabf
%O A135333 0,3
%A A135333 _N. J. A. Sloane_, Dec 07 2007
%E A135333 Edited and extended by _Emeric Deutsch_, Dec 13 2007