%I #63 Jan 22 2023 09:15:23
%S 1,1,1,2,3,4,7,12,19,33,59,102,181,329,593,1076,1979,3643,6723,12494,
%T 23289,43498,81557,153356,288925,545687,1032997,1958978,3721819,
%U 7083716,13503311,25778612,49283755,94345179,180830195,347006694,666636809,1282024484,2467964693
%N G.f. satisfies: A(x) = (1 + x*(1-x)*A(x)) * (1 + x^2*A(x)).
%C The radius of convergence of the g.f. A(x) equals 1/2, with A(1/2) = 4.
%C More generally, if A(x) = (1 + x*(t-x)*A(x)) * (1 + x^2*A(x)), |t|>0, then
%C A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k) )
%C where the radius of convergence r of the g.f. A(x) satisfies
%C r = (1-r)^2/(t-r) = (1-t*r)/(2*(1-r)) with A(r) = 1/(r*(1-r)) = 2/(1-t*r).
%C 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
%H G. C. Greubel, <a href="/A216604/b216604.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, preprint, 2019.
%F G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k) ).
%F G.f.: ((1-x) - sqrt( (1-x)^2 - 4*x^3*(1-x) )) / (2*x^3*(1-x)).
%F a(n) ~ 2^(n+2)/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Sep 16 2013
%F 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
%F a(n) = 1 + Sum_{k=0..n-3} a(k) * a(n-k-3). - _Ilya Gutkovskiy_, Jan 28 2021
%F 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
%e 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 + ...
%e The logarithm of the g.f. begins:
%e log(A(x)) = ((1-x) + x)*x + ((1-x)^2 + 2^2*x*(1-x) + x^2)*x^2/2 +
%e ((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3)*x^3/3 +
%e ((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 +
%e ((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 + ...
%e Explicitly,
%e 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 + ...
%t 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 *)
%o (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)}
%o (PARI) {a(n)=polcoeff(2/(1-x+sqrt((1-x)^2-4*x^3*(1-x) +x*O(x^n))),n)}
%o for(n=0,40,print1(a(n),", "))
%o (PARI) a(n) = sum(k=0, n\3, binomial(n-2*k, k)*binomial(2*k, k)/(k+1)); \\ _Seiichi Manyama_, Jan 22 2023
%o (Maxima)
%o 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 */
%o a(n):=sum((binomial(2*m,m)*binomial(n-2*m+1,n-3*m))/(n-2*m+1),m,0,n/3);
%o /*_Vladimir Kruchinin_, Jan 27 2022 */
%Y Cf. A000108, A217464, A105633, A216434, A216454, A216447, A192415, A216616, A216617.
%K nonn
%O 0,4
%A _Paul D. Hanna_, Sep 10 2012
|