|
%I #17 Jan 08 2022 16:29:08
%S 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,
%T 138,9,1,511,1120,500,55,1,1,1023,2816,1672,275,11,1,2047,6912,5264,
%U 1205,81,1,1,4095,16640,15808,4797,481,13
%N Triangle read by rows: number of Motzkin paths by length and by number of humps.
%C 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.)
%H Yan Zhuang, <a href="https://arxiv.org/abs/1508.02793">A generalized Goulden-Jackson cluster method and lattice path enumeration</a>, Discrete Mathematics 341.2 (2018): 358-379; arXiv:1508.02793 [math.CO], 2015-2018.
%F 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.
%F 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
%e Example: Table begins
%e n|
%e -+------------------
%e 0|1
%e 1|1
%e 2|1, 1
%e 3|1, 3
%e 4|1, 7, 1
%e 5|1, 15, 5
%e 6|1, 31, 18, 1
%e 7|1, 63, 56, 7
%e 8|1, 127, 160, 34, 1
%e T(5,2) = 5 counts FUDUD, UDFUD, UDUDF, UDUFD, UFDUD.
%t 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. *)
%o (Maxima)
%o N(n,k):=(binomial(n,k-1)*binomial(n,k))/n;
%o 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 */
%Y Column k=2 is A001793.
%Y Cf. A001263.
%K nonn,tabf
%O 0,5
%A _David Callan_, Aug 01 2004
|
