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

%I #26 Jan 21 2019 15:32:35

%S 1,1,1,1,1,1,2,4,7,11,16,23,35,57,96,161,264,425,682,1106,1821,3030,

%T 5055,8412,13956,23145,38487,64261,107673,180762,303651,510187,857692,

%U 1443597,2433495,4108299,6943862,11746362,19883655,33681015,57096874,96874214

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

%H Alois P. Heinz, <a href="/A212364/b212364.txt">Table of n, a(n) for n = 0..1000</a>

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

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

%F 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

%F 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

%e a(0) = 1: the empty path.

%e a(1) = 1: UD.

%e a(5) = 1: UDUDUDUDUD.

%e a(6) = 2: UDUDUDUDUDUD, UUUUUUDDDDDD.

%e a(7) = 4: UDUDUDUDUDUDUD, UDUUUUUUDDDDDD, UUUUUUDDDDDDUD, UUUUUUDUDDDDDD.

%e a(8) = 7: UDUDUDUDUDUDUDUD, UDUDUUUUUUDDDDDD, UDUUUUUUDDDDDDUD, UDUUUUUUDUDDDDDD, UUUUUUDDDDDDUDUD, UUUUUUDUDDDDDDUD, UUUUUUDUDUDDDDDD.

%p a:= proc(n) option remember;

%p `if`(n=0, 1, a(n-1) +add(a(k)*a(n-5-k), k=1..n-5))

%p end:

%p seq(a(n), n=0..50);

%p # second Maple program:

%p a:= n-> coeff(series(RootOf(A=1+A*(x-x^5*(1-A)), A), x, n+1), x, n):

%p seq(a(n), n=0..50);

%t 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 *)

%Y Column k=5 of A212363.

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

%K nonn

%O 0,7

%A _Alois P. Heinz_, May 10 2012