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

1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 38, 52, 76, 117, 184, 288, 442, 662, 972, 1414, 2063, 3047, 4572, 6952, 10645, 16303, 24857, 37672, 56821, 85541, 128948, 195103, 296548, 452501, 692053, 1058990, 1619311, 2473171, 3773889, 5757885, 8791090

Offset

0,9

Links

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

Formula

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

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

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(8) = 2: UDUDUDUDUDUDUDUD, UUUUUUUUDDDDDDDD.
a(9) = 4: UDUDUDUDUDUDUDUDUD, UDUUUUUUUUDDDDDDDD, UUUUUUUUDDDDDDDDUD, UUUUUUUUDUDDDDDDDD.

Maple

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

Mathematica

With[{k = 7}, 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=7 of A212363.

Sequence in context: A225088 A175777 A098574 * A309838 A334251 A175776

Adjacent sequences: A212363 A212364 A212365 * A212367 A212368 A212369

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved