cp's OEIS Frontend

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

%I A097229 #17 Jan 08 2022 16:29:08
%S A097229 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 A097229 138,9,1,511,1120,500,55,1,1,1023,2816,1672,275,11,1,2047,6912,5264,
%U A097229 1205,81,1,1,4095,16640,15808,4797,481,13
%N A097229 Triangle read by rows: number of Motzkin paths by length and by number of humps.
%C A097229 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 A097229 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 A097229 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 A097229 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 A097229 Example: Table begins
%e A097229   n|
%e A097229   -+------------------
%e A097229   0|1
%e A097229   1|1
%e A097229   2|1,   1
%e A097229   3|1,   3
%e A097229   4|1,   7,   1
%e A097229   5|1,  15,   5
%e A097229   6|1,  31,  18,  1
%e A097229   7|1,  63,  56,  7
%e A097229   8|1, 127, 160, 34, 1
%e A097229 T(5,2) = 5 counts FUDUD, UDFUD, UDUDF, UDUFD, UFDUD.
%t A097229 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 A097229 (Maxima)
%o A097229 N(n,k):=(binomial(n,k-1)*binomial(n,k))/n;
%o A097229 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 A097229 Column k=2 is A001793.
%Y A097229 Cf. A001263.
%K A097229 nonn,tabf
%O A097229 0,5
%A A097229 _David Callan_, Aug 01 2004