A097229 Triangle read by rows: number of Motzkin paths by length and by number of humps.

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

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.

Yan Zhuang, A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379; arXiv:1508.02793 [math.CO], 2015-2018.

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

Column k=2 is A001793.

Cf. A001263.

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