A104545 Number of Motzkin paths of length n having no consecutive (1,0) steps.
1, 1, 1, 3, 5, 11, 25, 55, 129, 303, 721, 1743, 4241, 10415, 25761, 64095, 160385, 403263, 1018369, 2581887, 6569089, 16767871, 42927105, 110194175, 283574017, 731427583, 1890600193, 4896499455, 12704869633, 33021750015, 85966113281
Offset: 0
Keywords
Examples
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). The logarithm of the g.f. A = A(x) equals the series: log(A(x)) = (1 + x*A^2)*x/A + (1 + 2^2*x*A^2 + x^2*A^4)*x^2/A^2/2 + (1 + 3^2*x*A^2 + 3^2*x^2*A^4 + x^3*A^6)*x^3/A^3/3 + (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 + (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 + ...
Links
- Michael De Vlieger, Table of n, a(n) for n = 0..2302
- Andrei Asinowski, Cyril Banderier, Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
- Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Programs
-
Maple
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);
-
Mathematica
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 *) CoefficientList[Series[(1-Sqrt[1-4x^2 (1+x)^2])/(2x^2 (1+x)),{x,0,30}],x] (* Harvey P. Dale, Mar 02 2020 *) -
Maxima
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 */
-
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)} -
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)} -
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)}
Formula
G.f.: (1-sqrt(1-4z^2*(1+z)^2))/(2z^2*(1+z)).
G.f. A(x) satisfies:
(1) A(x) = (1+x)*(1 + x^2*A(x)^2).
(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)] ).
(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)] ).
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
(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
a(n) ~ 3^(1/4) * (1+sqrt(3))^(n + 1/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Nov 17 2017
Comments