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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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

LINKS

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

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+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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 7 03:32 EST 2016. Contains 278837 sequences.