OFFSET
0,7
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
G.f. satisfies: A(x) = 1+A(x)*(x-x^5*(1-A(x))).
a(n) = a(n-1) + Sum_{k=1..n-5} a(k)*a(n-5-k) if n>0; a(0) = 1.
Recurrence: (n+5)*a(n) = (2*n+7)*a(n-1) - (n+2)*a(n-2) + (2*n-5)*a(n-5) + 2*(n-4)*a(n-6) - (n-10)*a(n-10). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=0..(n-1)/4} C(n-4*k,k)*C(n-4*k,k+1)/(n-4*k) for n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019
EXAMPLE
a(0) = 1: the empty path.
a(1) = 1: UD.
a(5) = 1: UDUDUDUDUD.
a(6) = 2: UDUDUDUDUDUD, UUUUUUDDDDDD.
a(7) = 4: UDUDUDUDUDUDUD, UDUUUUUUDDDDDD, UUUUUUDDDDDDUD, UUUUUUDUDDDDDD.
a(8) = 7: UDUDUDUDUDUDUDUD, UDUDUUUUUUDDDDDD, UDUUUUUUDDDDDDUD, UDUUUUUUDUDDDDDD, UUUUUUDDDDDDUDUD, UUUUUUDUDDDDDDUD, UUUUUUDUDUDDDDDD.
MAPLE
a:= proc(n) option remember;
`if`(n=0, 1, a(n-1) +add(a(k)*a(n-5-k), k=1..n-5))
end:
seq(a(n), n=0..50);
# second Maple program:
a:= n-> coeff(series(RootOf(A=1+A*(x-x^5*(1-A)), A), x, n+1), x, n):
seq(a(n), n=0..50);
MATHEMATICA
CoefficientList[Series[(1-x+x^5-Sqrt[-4*x^5+(1-x+x^5)^2])/(2*x^5), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 10 2012
STATUS
approved