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

Author

Alois P. Heinz, May 10 2012

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Column k=10 of A212363.

Programs

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

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.