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,7

Links

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

Yu Hin Au and Murray R. Bremner, Enumerating Multi-Operator Monomials in Commutative and Noncommutative Settings, arXiv:2604.25731 [math.CO], 2026. See pp. 10, 12.

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

Example

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.

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);
# Alternative:
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 *)

Crossrefs

Column k=5 of A212363.

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

Sequence in context: A317910 A065095 A005253 * A320591 A129339 A196719

Adjacent sequences: A212361 A212362 A212363 * A212365 A212366 A212367

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved