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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 12, 67, 287, 1002, 3004, 8009, 19449, 43759, 92380, 184787, 353137, 650497, 1170632, 2110021, 3977161, 8271836, 19536661, 51111062, 140210129, 385123916, 1032218316, 2670065961, 6645249777, 15922990909, 36823807747, 82485177457

Offset

0,11

Comments

Lengths of descents are unrestricted.

Links

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

Vaclav Kotesovec, Asymptotic of subsequences of A212382

Formula

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

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 = 9 and r = 0.4164039515514120671..., s = 1.882616423435763466... 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(10) = 2: UDUDUDUDUDUDUDUDUDUD, UUUUUUUUUUDDDDDDDDDD.
a(11) = 12: UDUDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUUDDDDDDDDDD, UUUUUUUUUUDDDDDDDDDDUD, UUUUUUUUUUDDDDDDDDDUDD, UUUUUUUUUUDDDDDDDDUDDD, UUUUUUUUUUDDDDDDDUDDDD, UUUUUUUUUUDDDDDDUDDDDD, UUUUUUUUUUDDDDDUDDDDDD, UUUUUUUUUUDDDDUDDDDDDD, UUUUUUUUUUDDDUDDDDDDDD, UUUUUUUUUUDDUDDDDDDDDD, UUUUUUUUUUDUDDDDDDDDDD.

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-(9*t+1), y, false), t=0..(x-1)/9), 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)^9), A), x, n+1), x, n):
seq(a(n), n=0..40);

Crossrefs

Column k=9 of A212382.

Sequence in context: A039633 A265451 A180195 * A241074 A020062 A185035

Adjacent sequences: A212386 A212387 A212388 * A212390 A212391 A212392

Keyword

nonn

Author

Alois P. Heinz, May 12 2012

Status

approved