|
|
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
|
|
|
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.
T(n,k) = Sum_{i=1..n} binomial(n, 2*i)*N(i,k), T(n,0)=1, where N(n,k) is the triangle of Narayana numbers A001263. - Vladimir Kruchinin, Jan 08 2022
|
|
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
|
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. *)
|
|
PROG
|
(Maxima)
N(n, k):=(binomial(n, k-1)*binomial(n, k))/n;
T(n, k):=if k=0 then 1 else sum(binomial(n, 2*i)*N(i, k), i, 1, n); /* Vladimir Kruchinin, Jan 08 2022 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|