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

1, 1, 2, 4, 1, 9, 5, 23, 17, 2, 63, 54, 15, 178, 177, 69, 5, 514, 594, 273, 49, 1515, 1997, 1056, 280, 14, 4545, 6698, 4077, 1308, 168, 13827, 22487, 15545, 5745, 1140, 42, 42540, 75701, 58377, 24695, 6105, 594, 132124, 255455, 216864, 103862, 29810

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn
• tabf

Comments

From Emeric Deutsch, Dec 15 2007: (Start)

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

Row sums yield the Catalan numbers (A000108).

Column 0 yields A135307.

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

Examples

			Triangle begins:
     1;
     1;
     2;
     4,    1;
     9,    5;
    23,   17,    2;
    63,   54,   15;
   178,  177,   69,    5;
   514,  594,  273,   49;
  1515, 1997, 1056,  280,   14;
  4545, 6698, 4077, 1308,  168;
  ...
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).
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A000108, A135307, A243752.

Programs

Maple

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
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

Mathematica

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 *)

Formula

From Emeric Deutsch, Dec 15 2007: (Start)

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).

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)

Extensions

More terms from R. J. Mathar and Emeric Deutsch, Dec 08 2007