OFFSET
0,4
COMMENTS
The radius of convergence of the g.f. A(x) equals 1/2, with A(1/2) = 4.
More generally, if A(x) = (1 + x*(t-x)*A(x)) * (1 + x^2*A(x)), |t|>0, then
A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k) )
where the radius of convergence r of the g.f. A(x) satisfies
r = (1-r)^2/(t-r) = (1-t*r)/(2*(1-r)) with A(r) = 1/(r*(1-r)) = 2/(1-t*r).
Number of Motzkin excursions of length n that avoid the patterns UU, UD and DH. A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0. - Andrei Asinowski, Dec 20 2019
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.
FORMULA
G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k) ).
G.f.: ((1-x) - sqrt( (1-x)^2 - 4*x^3*(1-x) )) / (2*x^3*(1-x)).
a(n) ~ 2^(n+2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
a(n) = Sum_{q=0..n} 1/(q+1)*Sum_{r=0..q+1} C(n-2*q-2,n-r-q)*C(q+1,r-1)*C(q+1,r). - Vladimir Kruchinin, Jan 22 2019
a(n) = 1 + Sum_{k=0..n-3} a(k) * a(n-k-3). - Ilya Gutkovskiy, Jan 28 2021
a(n) = Sum_{m=0..n/3} C(2*m,m)*C(n-2*m+1,n-3*m)/(n-2*m+1). - Vladimir Kruchinin, Jan 27 2022
EXAMPLE
G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 19*x^8 + ...
The logarithm of the g.f. begins:
log(A(x)) = ((1-x) + x)*x + ((1-x)^2 + 2^2*x*(1-x) + x^2)*x^2/2 +
((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3)*x^3/3 +
((1-x)^4 + 4^2*x*(1-x)^3 + 6^2*x^2*(1-x)^2 + 4^2*x^3*(1-x) + x^4)*x^4/4 +
((1-x)^5 + 5^2*x*(1-x)^4 + 10^2*x^2*(1-x)^3 + 10^2*x^3*(1-x)^2 + 5^2*x^4*(1-x) + x^5)*x^5/5 + ...
Explicitly,
log(A(x)) = x + x^2/2 + 4*x^3/3 + 5*x^4/4 + 6*x^5/5 + 16*x^6/6 + 29*x^7/7 + 45*x^8/8 + 94*x^9/9 + 186*x^10/10 + ... + A217464(n)*x^n/n + ...
MATHEMATICA
CoefficientList[Series[((1 - x) - Sqrt[(1 - x)^2 - 4*x^3*(1 - x)])/(2*x^3 *(1 - x)), {x, 0, 50}], x] (* G. C. Greubel, Jan 24 2017 *)
PROG
(PARI) {a(n)=polcoeff(exp(sum(m=1, n+1, x^m/m*sum(k=0, m, binomial(m, k)^2*x^k*(1-x)^(m-k) + x*O(x^n)))), n)}
(PARI) {a(n)=polcoeff(2/(1-x+sqrt((1-x)^2-4*x^3*(1-x) +x*O(x^n))), n)}
for(n=0, 40, print1(a(n), ", "))
(PARI) a(n) = sum(k=0, n\3, binomial(n-2*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023
(Maxima)
a(n):=sum(sum(binomial(n-2*q-2, n-r-q)*binomial(q+1, r-1)*binomial(q+1, r) , r, 0, q+1)/(q+1), q, 0, n); /* Vladimir Kruchinin, Jan 22 2019 */
a(n):=sum((binomial(2*m, m)*binomial(n-2*m+1, n-3*m))/(n-2*m+1), m, 0, n/3);
/*Vladimir Kruchinin, Jan 27 2022 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Sep 10 2012
STATUS
approved