login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216604 G.f. satisfies: A(x) = (1 + x*(1-x)*A(x)) * (1 + x^2*A(x)). 9
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 (list; graph; refs; listen; history; text; internal format)
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

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), ", "))

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

CROSSREFS

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

Sequence in context: A227047 A298304 A307970 * A211695 A261396 A018148

Adjacent sequences:  A216601 A216602 A216603 * A216605 A216606 A216607

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Sep 10 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 08:38 EDT 2020. Contains 337268 sequences. (Running on oeis4.)