This site is supported by donations to The OEIS Foundation.

 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 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 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 23 17:13 EST 2019. Contains 319399 sequences. (Running on oeis4.)