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
Keywords
Examples
a(4)=7 because the only counterexamples among the 9 Motzkin paths of length 4 are HUHD and UHDH.
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.
Crossrefs
Cf. A114583.
Programs
-
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 *) -
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
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
Comments