A216604 G.f. satisfies: A(x) = (1 + x*(1-x)*A(x)) * (1 + x^2*A(x)).

1, 1, 1, 2, 3, 4, 7, 12, 19, 33, 59, 102, 181, 329, 593, 1076, 1979, 3643, 6723, 12494, 23289, 43498, 81557, 153356, 288925, 545687, 1032997, 1958978, 3721819, 7083716, 13503311, 25778612, 49283755, 94345179, 180830195, 347006694, 666636809, 1282024484, 2467964693

Offset: 0

Author

Paul D. Hanna, Sep 10 2012

Keywords

• nonn

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

Examples

			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 + ...
		

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.

Crossrefs

Cf. A000108, A217464, A105633, A216434, A216454, A216447, A192415, A216616, A216617.

Programs

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 *)

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 */

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

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