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

1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 30, 43, 66, 106, 172, 275, 429, 656, 996, 1522, 2360, 3714, 5897, 9376, 14852, 23410, 36788, 57828, 91187, 144413, 229561, 365678, 582766, 928280, 1477877, 2353062, 3749721, 5983631, 9562565, 15300700, 24501417

Offset

0,8

Links

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

Formula

G.f. satisfies: A(x) = 1+A(x)*(x-x^6*(1-A(x))).

a(n) = a(n-1) + Sum_{k=1..n-6} a(k)*a(n-6-k) if n>0; a(0) = 1.

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(6) = 1: UDUDUDUDUDUD.
a(7) = 2: UDUDUDUDUDUDUD, UUUUUUUDDDDDDD.
a(8) = 4: UDUDUDUDUDUDUDUD, UDUUUUUUUDDDDDDD, UUUUUUUDDDDDDDUD, UUUUUUUDUDDDDDDD.

Maple

a:= proc(n) option remember;
      `if`(n=0, 1, a(n-1) +add(a(k)*a(n-6-k), k=1..n-6))
    end:
seq(a(n), n=0..50);
# second Maple program:
a:= n-> coeff(series(RootOf(A=1+A*(x-x^6*(1-A)), A), x, n+1), x, n):
seq(a(n), n=0..50);

Mathematica

CoefficientList[Series[(1 - x + x^6 - Sqrt[(1-x+x^6)^2 - 4*x^6])/ (2*x^6), {x, 0, 40}], x] (* Vaclav Kotesovec, Sep 02 2014 *)

Crossrefs

Column k=6 of A212363.

Sequence in context: A175776 A177176 A005689 * A131075 A365698 A133523

Adjacent sequences: A212362 A212363 A212364 * A212366 A212367 A212368

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved