A212367 Number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 8).

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 47, 62, 87, 129, 197, 302, 457, 677, 980, 1392, 1957, 2752, 3907, 5630, 8237, 12187, 18123, 26927, 39810, 58472, 85381, 124234, 180677, 263375, 385538, 567036, 837306, 1239408, 1835867, 2717386, 4016173

Offset: 0

Author

Alois P. Heinz, May 10 2012

Keywords

• nonn

Examples

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(9) = 2: UDUDUDUDUDUDUDUDUD, UUUUUUUUUDDDDDDDDD.
a(10) = 4: UDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUDDDDDDDDD, UUUUUUUUUDDDDDDDDDUD, UUUUUUUUUDUDDDDDDDDD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Column k=8 of A212363.

Programs

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

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.