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

Author

Alois P. Heinz, May 10 2012

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Column k=6 of A212363.

Programs

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

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.