A246188 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k occurrences of the string ududu, where u=(1,1), d=(1,-1).

1, 1, 2, 4, 1, 11, 2, 1, 31, 8, 2, 1, 92, 28, 9, 2, 1, 283, 99, 34, 10, 2, 1, 893, 354, 129, 40, 11, 2, 1, 2875, 1273, 492, 161, 46, 12, 2, 1, 9407, 4598, 1882, 646, 195, 52, 13, 2, 1, 31189, 16679, 7199, 2597, 816, 231, 58, 14, 2, 1, 104555, 60712, 27570, 10400, 3422, 1002, 269, 64, 15, 2, 1

Offset

0,3

Comments

Row n contains n-1 entries (n>=2).

Sum of entries in row n is the Catalan number A000108(n).

Sum(k*T(n,k), k>=0) = A001791(n-2) (n>=2).

T(21,k) = A243752(21,k), T(n,0) = A243753(n,21) = A247333(n). - Alois P. Heinz, Sep 13 2014

Links

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

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

Formula

G.f.: C(z*(1-t*z-z^2+t*z^2)/(1-t*z-z^3+t*z^3)), where C(u) = (1-sqrt(1-4*u))/(2*u) is the Catalan function. See Corollary 2.2 in the Mansour reference.

Example

Row 4 is 11, 2, 1; indeed in the 14 Dyck paths of semilength 4 ududu occurs only once in ududuudd, once in uudududd, and twice in udududud.
Triangle starts:
   1;
   1;
   2;
   4, 1;
  11, 2, 1;
  31, 8, 2, 1;
  ...

Maple

C := proc (u) options operator, arrow: (1/2-(1/2)*sqrt(1-4*u))/u end proc: G := C(z*(1-t*z-z^2+t*z^2)/(1-t*z-z^3+t*z^3)): Gser := simplify(series(G, z = 0, 20)): T := proc (n, k) options operator, arrow: coeff(coeff(Gser, z, n), t, k) end proc: 1; 1; for n from 2 to 12 do seq(T(n, k), k = 0 .. n-2) end do; # yields sequence in triangular form
# second Maple program:
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, 4][t])*
     `if`(t=5, z, 1) +b(x-1, y-1, [1, 3, 1, 5, 1][t]))))
    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, Sep 10 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, 4}[[t]] ]*If[t == 5, z, 1] + b[x-1, y-1, {1, 3, 1, 5, 1}[[t]] ]]]]; 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, May 27 2015, after Alois P. Heinz *)

Crossrefs

Cf. A000108, A001791, A243752, A243753, A247333.

Sequence in context: A346419 A048941 A308300 * A135333 A124503 A114499

Adjacent sequences: A246185 A246186 A246187 * A246189 A246190 A246191

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 10 2014

Status

approved