login
A114584
Number of Motzkin paths of length n having no UHD's (U=(1,1), H=(1,0), D=(1,-1)).
2
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 09 2005
STATUS
approved