|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
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.
|
|
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}];
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|