A135333 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k DUDU's starting at level 1.

1, 1, 2, 4, 1, 11, 2, 1, 32, 7, 2, 1, 99, 22, 8, 2, 1, 318, 73, 26, 9, 2, 1, 1051, 246, 90, 30, 10, 2, 1, 3550, 844, 312, 108, 34, 11, 2, 1, 12200, 2936, 1096, 384, 127, 38, 12, 2, 1, 42520, 10334, 3886, 1379, 462, 147, 42, 13, 2, 1, 149930, 36736, 13897, 4978, 1694

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn
• tabf

Comments

Each of rows 0, 1 and 2 contains one entry. Row n contains n-1 entries (n >= 2). Row sums are the Catalan numbers (A000108). Column 0 yields A135339. - Emeric Deutsch, Dec 13 2007

Examples

			Triangle begins:
1
1
2
4 1
11 2 1
32 7 2 1
99 22 8 2 1
318 73 26 9 2 1
1051 246 90 30 10 2 1
...
T(4,1)=2 because we have U(DUDU)UDD and UUD(DUDU)D; T(4,2)=1 because we have U(DU[DU)DU]D (the DUDU's starting at level 1 are shown between parentheses).
		

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.

Crossrefs

Cf. A000108, A135339.

Programs

Maple

G:=1+z*C+z^2*C^3/(1+(1-t)*z*C): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,17)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; 1; for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 13 2007
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
      `if`(y0, b(x-1, y-1, `if`(y=1, [2, 1, 4, 1][t], 1)), 0)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 28 2015

Mathematica

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

Formula

G.f.: 1+zC+z^2*C^3/[1+(1-t)zC], where C=[1-sqrt(1-4z)]/(2z) is the g.f. of the Catalan numbers (A000108). T(n,k) = d(0,k)*c(n-1)+Sum[(-1)^(j-k)*(j+3)binomial(j,k)binomial(2n-j-2,n),j=k..n-2]/(n+1), where c(m) = binomial(2m,m)/(m+1) = A000108(m) is a Catalan number and d(0,k) is the Kronecker symbol. - Emeric Deutsch, Dec 13 2007

Extensions

Edited and extended by Emeric Deutsch, Dec 13 2007