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,15

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).

Links

Table of n, a(n) for n=0..89.

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

Formula

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

Example

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;

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

Crossrefs

Cf. A004148, A166302, A000045, A091866.

Sequence in context: A092037 A338848 A364045 * A354059 A187081 A369308

Adjacent sequences: A166298 A166299 A166300 * A166302 A166303 A166304

Keyword

nonn,tabl

Author

Emeric Deutsch, Nov 07 2009

Status

approved