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

Links

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

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.

Example

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

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

Crossrefs

Column k=9 of A212363.

Sequence in context: A000124 A152947 A212369 * A217838 A212367 A225088

Adjacent sequences: A212365 A212366 A212367 * A212369 A212370 A212371

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved