A114584 Number of Motzkin paths of length n having no UHD's (U=(1,1), H=(1,0), D=(1,-1)).

1, 1, 2, 3, 7, 15, 36, 85, 209, 517, 1303, 3312, 8510, 22029, 57447, 150709, 397569, 1053822, 2805518, 7498035, 20110254, 54110386, 146021880, 395114304, 1071772322, 2913900196, 7939004648, 21672609566, 59272260791, 162380575451

Offset

0,3

Comments

Column 0 of A114583.

Links

Jinyuan Wang, Table of n, a(n) for n = 0..1000

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

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

Formula

G.f.: (1-z+z^3-sqrt((1+z+z^3)(1-3z+z^3)))/(2z^2).

Conjecture: +(n+2)*a(n) +(n+2)*a(n-1) +3*(-3*n+2)*a(n-2) +(-7*n+13)*a(n-3) +(4*n-13)*a(n-4) +6*(-n+5)*a(n-5) +(n-7)*a(n-6) +3*(n-8)*a(n-7)=0. - R. J. Mathar, Feb 16 2018

a(n) = Sum_{i=0..n/2} Sum_{j=0..n/2-i} (-1)^j*C(n-2*j,i)*C(n-2*j-2*i,j)*C(n-2*j-i,i)/(i+1). - Vladimir Kruchinin, May 05 2018

a(n) = a(n-1) - a(n-3) + Sum_{i=0..n-2} a(i)*a(n-2-i), a(0)=1. - Vladimir Kruchinin, May 05 2018

a(n) = Sum_{i=0..n/2} binomial(n,i)*binomial(n-i,i)*hypergeom([(2*i - n)/3, (2*i - n + 1)/3, (2*i - n + 2)/ 3], [(1 - n)/2, -n/2], 27/4) / (i + 1). - Peter Luschny, May 05 2018

G.f. A(x) satisfies: A(x) = (1 + x^2 * A(x)^2) / (1 - x + x^3). - Ilya Gutkovskiy, Jul 20 2021

Example

a(4)=7 because the only counterexamples among the 9 Motzkin paths of length 4 are HUHD and UHDH.

Maple

G:=(1-z+z^3-sqrt((1+z+z^3)*(1-3*z+z^3)))/2/z^2: Gser:=series(G, z=0, 35): 1, seq(coeff(Gser, z^n), n=1..32);

Mathematica

a[n_] := Sum[Binomial[n, i] Binomial[n - i, i] HypergeometricPFQ[{(2 i - n)/3, (2 i - n + 1)/3, (2 i - n + 2)/ 3}, {(1 - n)/2, -n/2}, 27/4] /(i + 1), {i, 0, n /2}];
Table[a[n], {n, 0, 29}] (* Peter Luschny, May 05 2018 *)

Prog

(Maxima)
a(n):=sum(sum((-1)^j*binomial(n-2*j, i)*binomial(n-2*j-2*i, j)*binomial(n-2*j-i, i), j, 0, (n)/2-i)/(i+1), i, 0, (n)/2); /* Vladimir Kruchinin, May 05 2018 */
(PARI) x='x+O('x^99); Vec((1-x+x^3-((1+x+x^3)*(1-3*x+x^3))^(1/2))/(2*x^2)) \\ Altug Alkan, May 05 2018

Crossrefs

Cf. A114583.

Sequence in context: A005909 A003006 A052321 * A328779 A039826 A221547

Adjacent sequences: A114581 A114582 A114583 * A114585 A114586 A114587

Keyword

nonn

Author

Emeric Deutsch, Dec 09 2005

Status

approved