A166301 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having pyramid weight k.

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 1, 2, 5, 0, 0, 0, 0, 1, 2, 6, 8, 0, 0, 0, 0, 1, 2, 8, 13, 13, 0, 0, 0, 0, 1, 2, 10, 19, 29, 21, 0, 0, 0, 0, 1, 2, 12, 25, 51, 60, 34, 0, 0, 0, 0, 1, 2, 14, 31, 78, 120, 122, 55, 0, 0, 0, 0, 1, 2, 16, 37, 110, 200, 282, 241

Offset: 0

Author

Emeric Deutsch, Nov 07 2009

Keywords

• nonn
• tabl

Comments

A pyramid in a Dyck word (path) is a factor of the form U^h D^h, h being the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.

Sum of entries in row n is the secondary structure number A004148(n-1) (n>=2).

T(n,n)=A000045(n-1) (n>=1; the Fibonacci numbers).

Sum(k*T(n,k), k>=0)=A166302(n).

Examples

			T(6,5)=2 because we have U(UUDD)(UUUDDD)D and U(UUUDDD)(UUDD)D (the maximal pyramids are shown between parentheses).
Triangle starts:
1;
0,0;
0,0,1;
0,0,0,1;
0,0,0,0,2;
0,0,0,0,1,3;
0,0,0,0,1,2,5;
0,0,0,0,1,2,6,8;
		

Links

• A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

Crossrefs

Cf. A004148, A166302, A000045, A091866.

Programs

Maple

eq := G = 1+z*G*(G-1+t^2*z*(1-z)/(1-t*z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 12 do P[n] := sort(expand(coeff(Gser, z, n))) end do: for n from 0 to 12 do seq(coeff(P[n], t, j), j = 0 .. n) end do; # yields sequence in triangular form

Formula

G.f.: G=G(t,z) satisfies G = 1 + zG[G - 1 + tz - tz(1 - t)/(1 - tz)].