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

1, 1, 1, 1, 1, 1, 2, 8, 29, 85, 211, 464, 943, 1873, 3914, 9101, 23298, 61915, 162283, 409888, 996456, 2360486, 5555333, 13244114, 32357022, 80958851, 205389082, 522000262, 1317987172, 3297123652, 8190326857, 20302864970, 50482613327, 126318440989

Offset

0,7

Comments

Lengths of descents are unrestricted.

The radius of convergence of g.f. A(x) is r = 5*(1-2*s+s^2)/(s*(5*s-4)) = 0.3804593157188..., where s = A(r) is described below. - Vaclav Kotesovec, Mar 20 2014

Links

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

Vaclav Kotesovec, Recurrence (of order 10)

Vaclav Kotesovec, Asymptotic of subsequences of A212382

Formula

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

Representation in terms of special values of generalized hypergeometric function of type 12F11: a(n) = hypergeom([1/7, 2/7, 3/7, 4/7, 5/7, 6/7, -(1/6)*n, -(1/6)*n+5/6, -(1/6)*n+2/3, -(1/6)*n+1/2, -(1/6)*n+1/3, 1/6-(1/6)*n], [1/6, 1/3, 1/3, 1/2, 1/2, 2/3, 2/3, 5/6, 5/6, 1, 7/6], 7^7/6^6), n>=0. - Karol A. Penson, Jun 21 2013

a(n) ~ s^(n+3/2) * (5*s-4)^(n+2) / (2 * sqrt(Pi) * sqrt(3*s-2) * n^(3/2) * 5^(n+5/2) * (s-1)^(2*n+9/2)), where s = 1.87696911628429... is the root of the equation 2869 - 29970*s + 138225*s^2 - 373000*s^3 + 655625*s^4 - 787500*s^5 + 656250*s^6 - 375000*s^7 + 140625*s^8 - 31250*s^9 + 3125*s^10 = 0. - Vaclav Kotesovec, Mar 20 2014

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

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(6) = 2: UDUDUDUDUDUD, UUUUUUDDDDDD.
a(7) = 8: UDUDUDUDUDUDUD, UDUUUUUUDDDDDD, UUUUUUDDDDDDUD, UUUUUUDDDDDUDD, UUUUUUDDDDUDDD, UUUUUUDDDUDDDD, UUUUUUDDUDDDDD, UUUUUUDUDDDDDD.

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

Mathematica

b[x_, y_, u_] := b[x, y, u] = If[x<0 || y<x, 0, If[x == 0 && y == 0, 1, b[x, y-1, True] + If[u, Sum [b[x - (5*t+1), y, False], {t, 0, (x-1)/5}], 0]]]; a[n_] := b[n, n, True]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

Prog

(Maxima)
a(n):=sum(binomial(4*k-3*n-1, n-k)*binomial(n+1, 5*k-4*n), k, 0, n)/(n+1); /* Vladimir Kruchinin, Mar 05 2016 */
(PARI) a(n) = sum(k=0, n, binomial(4*k-3*n-1, n-k)*binomial(n+1, 5*k-4*n))/(n+1); \\ Michel Marcus, Mar 05 2016

Crossrefs

Column k=5 of A212382.

Sequence in context: A306847 A364523 A107025 * A333882 A365760 A365758

Adjacent sequences: A212382 A212383 A212384 * A212386 A212387 A212388

Keyword

nonn

Author

Alois P. Heinz, May 12 2012

Status

approved