OFFSET
0,10
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
G.f. satisfies: A(x) = 1+A(x)*(x-x^8*(1-A(x))).
a(n) = a(n-1) + Sum_{k=1..n-8} a(k)*a(n-8-k) if n>0; a(0) = 1.
EXAMPLE
a(0) = 1: the empty path.
a(1) = 1: UD.
a(9) = 2: UDUDUDUDUDUDUDUDUD, UUUUUUUUUDDDDDDDDD.
a(10) = 4: UDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUDDDDDDDDD, UUUUUUUUUDDDDDDDDDUD, UUUUUUUUUDUDDDDDDDDD.
MAPLE
a:= proc(n) option remember;
`if`(n=0, 1, a(n-1) +add(a(k)*a(n-8-k), k=1..n-8))
end:
seq(a(n), n=0..60);
# second Maple program:
a:= n-> coeff(series(RootOf(A=1+A*(x-x^8*(1-A)), A), x, n+1), x, n):
seq(a(n), n=0..60);
MATHEMATICA
With[{k = 8}, CoefficientList[Series[(1 - x + x^k - Sqrt[(1 - x + x^k)^2 - 4*x^k]) / (2*x^k), {x, 0, 40}], x]] (* Vaclav Kotesovec, Sep 02 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 10 2012
STATUS
approved