|
| |
|
|
A104545
|
|
Number of Motzkin paths of length n having no consecutive (1,0) steps.
|
|
5
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| a(n)=A104544(n,0) (n>0).
|
|
|
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)] ).
|
|
|
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);
|
|
|
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)}
|
|
|
CROSSREFS
| Cf. A001006, A104544, A198957, A200718.
Sequence in context: A018116 A167796 A018008 * A027050 A109249 A196423
Adjacent sequences: A104542 A104543 A104544 * A104546 A104547 A104548
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 14 2005
|
| |
|
|
