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

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

Sequence in context: A298304 A367691 A307970 * A211695 A261396 A357532

Adjacent sequences: A216601 A216602 A216603 * A216605 A216606 A216607

Keyword

nonn

Author

Paul D. Hanna, Sep 10 2012

Status

approved