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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097229 Triangle read by rows: number of Motzkin paths by length and by number of humps. 1
1, 1, 1, 1, 3, 1, 7, 1, 1, 15, 5, 1, 31, 18, 1, 1, 63, 56, 7, 1, 127, 160, 34, 1, 1, 255, 432, 138, 9, 1, 511, 1120, 500, 55, 1, 1, 1023, 2816, 1672, 275, 11, 1, 2047, 6912, 5264, 1205, 81, 1, 1, 4095, 16640, 15808, 4797, 481, 13 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

T(n,k) = number of Motzkin paths of length n containing exactly k humps. (A hump is an upstep followed by 0 or more flatsteps followed by a downstep.)

LINKS

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

Zhuang, Yan. A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.

FORMULA

G.f.: ((-1 + 2*x - 2*x^2 + x^2*y + ((1 - 2*x)^2 + 2*x^2*(-1 + 2*x - 2*x^2)*y + x^4*y^2)^(1/2))/(2*(-1 + x)*x^2) = Sum_{n>=0, k>=0} a(n, k) x^n y^k satisfies x^2 A(x, y)^2 - ( x^2(1-y)/(1-x) + (1-x) )A(x, y) + 1 = 0.

EXAMPLE

Example: Table begins

n|

0|1

1|1

2|1, 1

3|1, 3

4|1, 7, 1

5|1, 15, 5

6|1, 31, 18, 1

7|1, 63, 56, 7

8|1, 127, 160, 34, 1

T(5,2) = 5 counts FUDUD, UDFUD, UDUDF, UDUFD, UFDUD.

MATHEMATICA

Program: (Math'ca) a[n_, k_]/; k<0 || k>n/2 := 0; a[n_, 0]/; n>=0 := 1; a[n_, k_]/; 1<=k<=n := a[n, k] = a[n-1, k] + Sum[a[n-r, k-1], {r, 2, n}]+Sum[a[r-2, j]a[n-r, k-j], {r, 2, n}, {j, k}] This recurrence counts a(n, k) by first return to ground level.

CROSSREFS

Column k=2 is A001793.

Sequence in context: A143470 A114580 A257597 * A097862 A097612 A136011

Adjacent sequences:  A097226 A097227 A097228 * A097230 A097231 A097232

KEYWORD

nonn,tabf,changed

AUTHOR

David Callan, Aug 01 2004

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 February 19 16:56 EST 2018. Contains 299356 sequences. (Running on oeis4.)