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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 68, 85, 112, 156, 226, 333, 490, 712, 1016, 1421, 1949, 2630, 3512, 4676, 6256, 8464, 11620, 16187, 22811, 32366, 46005, 65225, 91967, 128786, 179140, 247861, 341885, 471332, 651041, 902679

Offset

0,12

Links

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

Formula

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

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

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(11) = 2: UDUDUDUDUDUDUDUDUDUDUD, UUUUUUUUUUUDDDDDDDDDDD.
a(12) = 4: UDUDUDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUUUDDDDDDDDDDD, UUUUUUUUUUUDDDDDDDDDDDUD, UUUUUUUUUUUDUDDDDDDDDDDD.

Maple

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

Mathematica

With[{k = 10}, CoefficientList[Series[(1 - x + x^k - Sqrt[(1 - x + x^k)^2 - 4*x^k]) / (2*x^k), {x, 0, 50}], x]] (* Vaclav Kotesovec, Sep 02 2014 *)

Crossrefs

Column k=10 of A212363.

Sequence in context: A025739 A000124 A152947 * A212368 A217838 A212367

Adjacent sequences: A212366 A212367 A212368 * A212370 A212371 A212372

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved