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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 57, 73, 99, 142, 211, 317, 473, 694, 997, 1402, 1937, 2648, 3614, 4967, 6917, 9782, 14023, 20284, 29438, 42647, 61457, 87963, 125093, 177074, 250157, 353692, 501658, 714768, 1023296, 1470843

Offset: 0

Author

Alois P. Heinz, May 10 2012

Keywords

• nonn

Examples

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(10) = 2: UDUDUDUDUDUDUDUDUDUD, UUUUUUUUUUDDDDDDDDDD.
a(11) = 4: UDUDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUUDDDDDDDDDD, UUUUUUUUUUDDDDDDDDDDUD, UUUUUUUUUUDUDDDDDDDDDD.
		

Links

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

Crossrefs

Column k=9 of A212363.

Programs

Maple

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

Mathematica

With[{k = 9}, 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^9*(1-A(x))).

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