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

1, 1, 1, 1, 1, 1, 1, 1, 2, 10, 46, 166, 496, 1288, 3004, 6437, 12895, 24583, 45799, 87211, 180235, 420547, 1087220, 2941931, 7927664, 20705636, 51886966, 124660576, 288445186, 648173927, 1431655546, 3156274456, 7062245781, 16256654077, 38704049941, 94853117381

Offset

0,9

Comments

Lengths of descents are unrestricted.

Links

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

Vaclav Kotesovec, Asymptotic of subsequences of A212382

Formula

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

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 = 7 and r = 0.4020785148135889828..., s = 1.877947072112206660... 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

a(n) = Sum_{k=0..n} (binomial(6*k-5*n-1,n-k)*binomial(n+1,7*k-6*n))/(n+1). - Vladimir Kruchinin, Mar 05 2016

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(8) = 2: UDUDUDUDUDUDUDUD, UUUUUUUUDDDDDDDD.
a(9) = 10: UDUDUDUDUDUDUDUDUD, UDUUUUUUUUDDDDDDDD, UUUUUUUUDDDDDDDDUD, UUUUUUUUDDDDDDDUDD, UUUUUUUUDDDDDDUDDD, UUUUUUUUDDDDDUDDDD, UUUUUUUUDDDDUDDDDD, UUUUUUUUDDDUDDDDDD, UUUUUUUUDDUDDDDDDD, UUUUUUUUDUDDDDDDDD.

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

Mathematica

a[n_] := Sum[Binomial[6k-5n-1, n-k]*Binomial[n+1, 7k-6n], {k, 0, n}]/(n+1);
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 03 2017, after Vladimir Kruchinin *)

Prog

(Maxima)
a(n):=sum(binomial(6*k-5*n-1, n-k)*binomial(n+1, 7*k-6*n), k, 0, n)/(n+1); /* Vladimir Kruchinin, Mar 05 2016 */

Crossrefs

Column k=7 of A212382.

Sequence in context: A209010 A306752 A306859 * A191813 A360412 A181294

Adjacent sequences: A212384 A212385 A212386 * A212388 A212389 A212390

Keyword

nonn

Author

Alois P. Heinz, May 12 2012

Status

approved