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

Column k=8 of A212363.

Sequence in context: A212369 A212368 A217838 * A225088 A175777 A098574

Adjacent sequences: A212364 A212365 A212366 * A212368 A212369 A212370

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved