A212388 Number of Dyck n-paths all of whose ascents have lengths equal to 1 (mod 8).

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 11, 56, 221, 716, 2003, 5006, 11441, 24312, 48648, 92721, 170811, 311886, 589590, 1220979, 2864973, 7450852, 20309628, 55305706, 146505451, 373452808, 913836082, 2150455648, 4887179761, 10794337952, 23375638064, 50219351232

Offset

0,10

Comments

Lengths of descents are unrestricted.

Links

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

Vaclav Kotesovec, Asymptotic of subsequences of A212382

Formula

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

a(n) ~ s^2 / (n^(3/2) * r^(n-1/2) * sqrt(2*Pi*p*(s-1)*(1+s/(1+p*(s-1))))), where p = 8 and r = 0.4098875088359862102..., s = 1.880071788712472133... are roots of the system of equations r = p*(s-1)^2 / (s*(1-p+p*s)), (r*s)^p = (s-1-r*s)/(s-1). - Vaclav Kotesovec, Jul 16 2014

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(9) = 2: UDUDUDUDUDUDUDUDUD, UUUUUUUUUDDDDDDDDD.
a(10) = 11: UDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUDDDDDDDDD, UUUUUUUUUDDDDDDDDDUD, UUUUUUUUUDDDDDDDDUDD, UUUUUUUUUDDDDDDDUDDD, UUUUUUUUUDDDDDDUDDDD, UUUUUUUUUDDDDDUDDDDD, UUUUUUUUUDDDDUDDDDDD, UUUUUUUUUDDDUDDDDDDD, UUUUUUUUUDDUDDDDDDDD, UUUUUUUUUDUDDDDDDDDD.

Maple

b:= proc(x, y, u) option remember;
      `if`(x<0 or  y<x, 0, `if`(x=0 and y=0, 1, b(x, y-1, true)+
      `if`(u, add (b(x-(8*t+1), y, false), t=0..(x-1)/8), 0)))
    end:
a:= n-> b(n$2, true):
seq(a(n), n=0..40);
# second Maple program
a:= n-> coeff(series(RootOf(A=1+x*A/(1-(x*A)^8), A), x, n+1), x, n):
seq(a(n), n=0..40);

Crossrefs

Column k=8 of A212382.

Sequence in context: A115205 A306753 A306860 * A198769 A037554 A106804

Adjacent sequences: A212385 A212386 A212387 * A212389 A212390 A212391

Keyword

nonn

Author

Alois P. Heinz, May 12 2012

Status

approved