|
Search: id:A097229
|
|
|
| A097229 |
|
Triangle read by rows: number of Motzkin paths by length and by number of humps. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
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.)
|
|
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: A026499 A143470 A114580 this_sequence A097862 A097612 A136011
Adjacent sequences: A097226 A097227 A097228 this_sequence A097230 A097231 A097232
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
David Callan (callan(AT)stat.wisc.edu), Aug 01 2004
|
|
|
Search completed in 0.002 seconds
|
