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

1, 1, 2, 5, 13, 1, 36, 5, 1, 104, 21, 6, 1, 309, 84, 28, 7, 1, 939, 322, 124, 36, 8, 1, 2905, 1206, 522, 174, 45, 9, 1, 9118, 4455, 2127, 795, 235, 55, 10, 1, 28964, 16302, 8492, 3487, 1155, 308, 66, 11, 1, 92940, 59268, 33396, 14894, 5412, 1617, 394, 78, 12, 1

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn
• tabf

Comments

Each of rows 0, 1, 2, 3 has one entry. Row n (n >= 3) has n-2 entries. Row sums yield the Catalan numbers (A000108). Column 0 yields A036765. - Emeric Deutsch, Dec 14 2007

Examples

			Triangle begins:
1
1
2
5
13 1
36 5 1
104 21 6 1
309 84 28 7 1
...
T(5,1) = 5 because we have UUUUDUDDDD, UUUUDDUDDD, UUUUDDDUDD, UUUUDDDDUD and UDUUUUDDDD.
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened
• FindStat - Combinatorial Statistic Finder, The number of occurrences of the contiguous pattern [.,[.,[.,[.,.]]]].
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A000108, A036765, A243752.

Programs

Maple

eq:=(1-t)*z^3*G^3+z*(t+z-t*z)*G^2+((1-t)*z-1)*G+1: g:=RootOf(eq,G): gser:= simplify(series(g,z=0,15)): for n from 0 to 12 do P[n]:=sort(coeff(gser,z,n)) end do: 1;1;2; for n from 3 to 12 do seq(coeff(P[n],t,j),j=0..n-3) end do; # yields sequence in triangular form; # Emeric Deutsch, Dec 14 2007
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y+1, min(t+1, 4))*
      `if`(t=4, z, 1) +b(x-1, y-1, 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, Min[t+1, 4]]*If[t == 4, z, 1] + b[x-1, y-1, 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, Nov 28 2014, after Alois P. Heinz *)

Formula

G.f.: G=G(t,z) satisfies (1-t)*z^3*G^3 + z*(t+z-t*z)*G^2 + ((1-t)*z-1)*G+1 = 0. - Emeric Deutsch, Dec 14 2007

Extensions

Edited and extended by Emeric Deutsch, Dec 14 2007