cp's OEIS Frontend

A135306 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDDU's.

%I A135306 #29 Nov 16 2019 06:03:06
%S A135306 1,1,2,4,1,9,5,23,17,2,63,54,15,178,177,69,5,514,594,273,49,1515,1997,
%T A135306 1056,280,14,4545,6698,4077,1308,168,13827,22487,15545,5745,1140,42,
%U A135306 42540,75701,58377,24695,6105,594,132124,255455,216864,103862,29810
%N A135306 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDDU's.
%C A135306 From _Emeric Deutsch_, Dec 15 2007: (Start)
%C A135306 Row 0 has 1 term; row n (n >= 1) has ceiling(n/2) terms.
%C A135306 Row sums yield the Catalan numbers (A000108).
%C A135306 Column 0 yields A135307.
%C A135306 T(2n+1, n) = binomial(2n,n)/(n+1) (the Catalan numbers, A000108). (End)
%H A135306 Alois P. Heinz, <a href="/A135306/b135306.txt">Rows n = 0..200, flattened</a>
%H A135306 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 A135306 From _Emeric Deutsch_, Dec 15 2007: (Start)
%F A135306 T(n,k) = (1/n)*binomial(n,k)*Sum_{j=k..floor((n-1)/2)} (-1)^(j-k)*binomial(n-k, j-k)*binomial(2n-3j, n-j+1).
%F A135306 G.f.: G = G(t,z) satisfies z*G^3 - ((1-t)*z+1)*G^2 + (1+2*(1-t)*z)*G - (1-t)*z = 0. (End)
%e A135306 Triangle begins:
%e A135306      1;
%e A135306      1;
%e A135306      2;
%e A135306      4,    1;
%e A135306      9,    5;
%e A135306     23,   17,    2;
%e A135306     63,   54,   15;
%e A135306    178,  177,   69,    5;
%e A135306    514,  594,  273,   49;
%e A135306   1515, 1997, 1056,  280,   14;
%e A135306   4545, 6698, 4077, 1308,  168;
%e A135306   ...
%e A135306 T(4,1) = 5 because we have U(UDDU)DUD, U(UDDU)UDD, UU(UDDU)DD, UDU(UDDU)D and UUD(UDDU)D (the UDDU's are shown between parentheses).
%p A135306 A135306 := proc(n,k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((n-1)/2)) ; %*binomial(n,k)/n ; fi ; end: for n from 0 to 20 do for k from 0 to max(0,(n-1)/2) do printf("%a, ",A135306(n,k)) ; od: od: # _R. J. Mathar_, Dec 08 2007
%p A135306 T:=proc(n,k) options operator, arrow: binomial(n,k)*(sum((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((1/2)*n-1/2)))/n 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 15 2007
%t A135306 T[n_, k_] := Binomial[n, k]*Sum[(-1)^(j-k)*Binomial[n-k, j-k]*Binomial[2*n - 3*j, -j+n+1], {j, k, (n-1)/2}]/n; T[0, 0] = 1; Table[T[n, k], {n, 0, 13}, {k, 0, If[n == 0, 0, Quotient[n-1, 2]]}] // Flatten (* _Jean-François Alcover_, Nov 27 2014, after _Emeric Deutsch_ *)
%Y A135306 Cf. A000108, A135307, A243752.
%K A135306 nonn,tabf
%O A135306 0,3
%A A135306 _N. J. A. Sloane_, Dec 07 2007
%E A135306 More terms from _R. J. Mathar_ and _Emeric Deutsch_, Dec 08 2007