|
%I #27 Mar 11 2020 23:00:00
%S 1,1,1,3,5,11,25,55,129,303,721,1743,4241,10415,25761,64095,160385,
%T 403263,1018369,2581887,6569089,16767871,42927105,110194175,283574017,
%U 731427583,1890600193,4896499455,12704869633,33021750015,85966113281
%N Number of Motzkin paths of length n having no consecutive (1,0) steps.
%C a(n) = A104544(n,0) (n > 0).
%H Michael De Vlieger, <a href="/A104545/b104545.txt">Table of n, a(n) for n = 0..2302</a>
%H Andrei Asinowski, Cyril Banderier, Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.
%F G.f.: (1-sqrt(1-4z^2*(1+z)^2))/(2z^2*(1+z)).
%F G.f. A(x) satisfies:
%F (1) A(x) = (1+x)*(1 + x^2*A(x)^2).
%F (2) A(x) = exp( Sum_{n>=1} x^n * A(x)^(-n)/n * [Sum_{k=0..n} C(n,k)^2 * x^k * A(x)^(2*k)] ).
%F (3) A(x) = exp( Sum_{n>=1} x^n * A(x)^(-n)/n * [(1-x/A(x)^2)^(2*n+1) * Sum_{k>=0} C(n+k,k)^2*x^k * A(x)^(2*k)] ).
%F a(n+1) = sum(binomial(2*k,k)/(k+1)*(binomial(2*k,n-2*k+1)+binomial(2*k,n-2*k)),k,ceiling(n/4),(n+1)/2), a(0)=1. - _Vladimir Kruchinin_, Mar 14 2012
%F (n+2)*a(n) + (n+2)*a(n-1) + 4*(-n+1)*a(n-2) + 12*(-n+2)*a(n-3) + 12*(-n+3)*a(n-4) + 4*(-n+4)*a(n-5) = 0. - _R. J. Mathar_, Jul 23 2017
%F a(n) ~ 3^(1/4) * (1+sqrt(3))^(n + 1/2) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Nov 17 2017
%e a(3)=3 because we have UDH, HUD and UHD, where U=(1,1), D=(1,-1) and H=(1,0) (HHH does not qualify).
%e The logarithm of the g.f. A = A(x) equals the series:
%e log(A(x)) = (1 + x*A^2)*x/A + (1 + 2^2*x*A^2 + x^2*A^4)*x^2/A^2/2 +
%e (1 + 3^2*x*A^2 + 3^2*x^2*A^4 + x^3*A^6)*x^3/A^3/3 +
%e (1 + 4^2*x*A^2 + 6^2*x^2*A^4 + 4^2*x^3*A^6 + x^4*A^8)*x^4/A^4/4 +
%e (1 + 5^2*x*A^2 + 10^2*x^2*A^4 + 10^2*x^3*A^6 + 5^2*x^4*A^8 + x^5*A^10)*x^5/A^5/5 + ...
%p G:=(1-sqrt(1-4*z^2*(1+z)^2))/2/z^2/(1+z): Gser:=series(G,z=0,35): 1,seq(coeff(Gser,z^n),n=1..31);
%t Array[Sum[Binomial[2 k, k]/(k + 1) (Binomial[2 k, # - 2 k + 1] + Binomial[2 k, # - 2 k]), {k, Ceiling[#/4], (# + 1)/2}] &[# - 1] &, 31, 0] (* _Michael De Vlieger_, Feb 18 2020 *)
%t CoefficientList[Series[(1-Sqrt[1-4x^2 (1+x)^2])/(2x^2 (1+x)),{x,0,30}],x] (* _Harvey P. Dale_, Mar 02 2020 *)
%o (PARI) {a(n)=local(p=-1,q=2,A=1+x);for(i=1,n,A=(1+x*A^(p+1))*(1+x^2*A^(p+q+1))+x*O(x^n));polcoeff(A,n)}
%o (PARI) {a(n)=local(p=-1,q=2,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*sum(j=0,m,binomial(m, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}
%o (PARI) {a(n)=local(p=-1,q=2,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*(1-x*A^q)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}
%o (Maxima)
%o b(n):=sum(binomial(2*k,k)/(k+1)*(binomial(2*k,n-2*k+1)+binomial(2*k,n-2*k)),k,ceiling(n/4),(n+1)/2); a(n):=if n=0 then 1 else b(n-1); /* _Vladimir Kruchinin_, Mar 14 2012 */
%Y Cf. A001006, A104544, A198957, A200718.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Mar 14 2005
|
