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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 09 2005
STATUS
approved