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

Author

David Callan, Aug 01 2004

Keywords

• nonn
• tabf

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.)

Examples

			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.
		

Links

• 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.

Crossrefs

Column k=2 is A001793.

Cf. A001263.

Programs

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. *)

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 */

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