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

1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 23, 35, 57, 96, 161, 264, 425, 682, 1106, 1821, 3030, 5055, 8412, 13956, 23145, 38487, 64261, 107673, 180762, 303651, 510187, 857692, 1443597, 2433495, 4108299, 6943862, 11746362, 19883655, 33681015, 57096874, 96874214

Offset: 0

Author

Alois P. Heinz, May 10 2012

Keywords

• nonn

Examples

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(5) = 1: UDUDUDUDUD.
a(6) = 2: UDUDUDUDUDUD, UUUUUUDDDDDD.
a(7) = 4: UDUDUDUDUDUDUD, UDUUUUUUDDDDDD, UUUUUUDDDDDDUD, UUUUUUDUDDDDDD.
a(8) = 7: UDUDUDUDUDUDUDUD, UDUDUUUUUUDDDDDD, UDUUUUUUDDDDDDUD, UDUUUUUUDUDDDDDD, UUUUUUDDDDDDUDUD, UUUUUUDUDDDDDDUD, UUUUUUDUDUDDDDDD.
		

Links

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

Crossrefs

Column k=5 of A212363.

Cf. A023432 (m=3), A023427 (m=4), this sequence (m=5), A212386(m=6).

Programs

Maple

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

Mathematica

CoefficientList[Series[(1-x+x^5-Sqrt[-4*x^5+(1-x+x^5)^2])/(2*x^5),{x,0,20}],x] (* Vaclav Kotesovec, Mar 20 2014 *)

Formula

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

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

Recurrence: (n+5)*a(n) = (2*n+7)*a(n-1) - (n+2)*a(n-2) + (2*n-5)*a(n-5) + 2*(n-4)*a(n-6) - (n-10)*a(n-10). - Vaclav Kotesovec, Mar 20 2014

a(n) = Sum_{k=0..(n-1)/4} C(n-4*k,k)*C(n-4*k,k+1)/(n-4*k) for n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019