A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 19, 14, 7, 1, 1, 53, 46, 22, 9, 1, 1, 153, 150, 82, 31, 11, 1, 1, 453, 495, 299, 127, 41, 13, 1, 1, 1367, 1651, 1087, 507, 181, 52, 15, 1, 1, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 13015, 18692, 14442, 7824, 3271, 1128, 316, 77, 19

Offset

0,5

Comments

Column k=0 is A078481.

Column k=1 is A244236.

Row sums are the Catalan numbers (A000108).

Links

Alois P. Heinz, Rows n = 0..150, flattened

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Formula

G.f.: G=G(t, z) satisfies the equation z(1+z-tz)G^2-(1+z+z^2-tz-tz^2)G+1+z-tz=0.

Example

T(3,0) = 3 because UDUUDD, UUDDUD and UUUDDD are the only Dyck paths of semilength 3 and having no UDUD in them.
Triangle begins:
     1;
     1;
     1,    1;
     3,    1,    1;
     7,    5,    1,    1;
    19,   14,    7,    1,   1;
    53,   46,   22,    9,   1,   1;
   153,  150,   82,   31,  11,   1,  1;
   453,  495,  299,  127,  41,  13,  1,  1;
  1367, 1651, 1087,  507, 181,  52, 15,  1, 1;
  4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1;

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])
      +b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Jun 02 2014

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 2, 4, 2}[[t]]] + b[x-1, y-1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1] ]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Apr 29 2015, after Alois P. Heinz *)

Crossrefs

Cf. A078481, A000108, A102405 (the same for DUDU), A243752, A243753, A244236.

T(2n,n) gives A304361.

Sequence in context: A118801 A080936 A343237 * A065625 A287213 A284631

Adjacent sequences: A094504 A094505 A094506 * A094508 A094509 A094510

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 05 2004

Status

approved