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

Comments

a(n) = A104544(n,0) (n > 0).

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.

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

Example

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 + ...

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 *)

Prog

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

Crossrefs

Cf. A001006, A104544, A198957, A200718.

Sequence in context: A261896 A285184 A018008 * A027050 A240148 A109249

Adjacent sequences: A104542 A104543 A104544 * A104546 A104547 A104548

Keyword

nonn

Author

Emeric Deutsch, Mar 14 2005

Status

approved