login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A104573 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having trapezoid weight k. 1
1, 1, 1, 1, 1, 3, 1, 6, 2, 1, 12, 8, 1, 24, 22, 4, 1, 48, 58, 20, 1, 96, 149, 69, 8, 1, 192, 373, 221, 48, 1, 384, 914, 675, 198, 16, 1, 768, 2200, 1977, 740, 112, 1, 1536, 5216, 5597, 2593, 536, 32, 1, 3072, 12208, 15407, 8611, 2280, 256, 1, 6144, 28256, 41418, 27389 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

A Motzkin path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(1,0) and never going below the x-axis. Motzkin paths are counted by the Motzkin numbers (A001006).

A trapezoid in a Motzkin path is a factor of the form U^i H^j D^i (i>=1, j>=0), i being the height of the trapezoid. A trapezoid in a Motzkin path w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The trapezoid weight of a Motzkin path is the sum of the heights of its maximal trapezoids. For example, in the Motzkin path w=UH(UHD)D(UUDD) we have two maximal trapezoids (shown between parentheses) of heights 1 and 2, respectively. The trapezoid weight of w is 1+2=3.

This concept is analogous to the concept of pyramid weight in a Dyck path (see the Denise-Simion paper).

Row sums yield the Motzkin numbers (A001006).

Row n has 1+floor(n/2) terms.

T(2n+1,n)=(n+2)*2^(n-1) (A001792).

REFERENCES

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

LINKS

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

FORMULA

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

EXAMPLE

Triangle begins:

1;

1;

1,1;

1,3;

1,6,2;

1,12,8;

1,24,22,4;

T(4,0)=1,T(4,1)=6, T(4,2)=2 because the nine Motzkin paths of length 4, namely HHHH, HH(UD),H(UD)H,H(UHD),(UD)HH,(UD)(UD),(UHD)H,(UHHD),(UUDD), have trapezoid weights 0,1,1,1,1,2,1,1,2, respectively; the maximal trapezoids are shown between parentheses.

CROSSREFS

Cf. A001006, A001792, A104574.

Sequence in context: A152193 A055151 A181187 * A010467 A182182 A158823

Adjacent sequences:  A104570 A104571 A104572 * A104574 A104575 A104576

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Mar 16 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 21 01:47 EDT 2014. Contains 240824 sequences.