A135306 - OEIS

%I #29 Nov 16 2019 06:03:06

%S 1,1,2,4,1,9,5,23,17,2,63,54,15,178,177,69,5,514,594,273,49,1515,1997,

%T 1056,280,14,4545,6698,4077,1308,168,13827,22487,15545,5745,1140,42,

%U 42540,75701,58377,24695,6105,594,132124,255455,216864,103862,29810

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

%C From _Emeric Deutsch_, Dec 15 2007: (Start)

%C Row 0 has 1 term; row n (n >= 1) has ceiling(n/2) terms.

%C Row sums yield the Catalan numbers (A000108).

%C Column 0 yields A135307.

%C T(2n+1, n) = binomial(2n,n)/(n+1) (the Catalan numbers, A000108). (End)

%H Alois P. Heinz, <a href="/A135306/b135306.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 15 2007: (Start)

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

%e      1;

%e      1;

%e      2;

%e      4,    1;

%e      9,    5;

%e     23,   17,    2;

%e     63,   54,   15;

%e    178,  177,   69,    5;

%e    514,  594,  273,   49;

%e   1515, 1997, 1056,  280,   14;

%e   4545, 6698, 4077, 1308,  168;

%e   ...

%e 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 := 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 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 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 Cf. A000108, A135307, A243752.

%K nonn,tabf

%O 0,3

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

%E More terms from _R. J. Mathar_ and _Emeric Deutsch_, Dec 08 2007