A303117 a(n) is the number of cyclic permutations with at most two descents.

1, 1, 1, 2, 6, 18, 62, 186, 570, 1680, 4890, 14058, 40200, 114450, 325230, 923846, 2624730, 7465410, 21260652, 60647370, 173288724, 496014934, 1422211494, 4084793082, 11751102060, 33857989968, 97696908330, 282295318536, 816759712080, 2366027865810, 6861963548198, 19922800783578, 57902584654650

Offset: 0

Author

Kassie Archer, Apr 18 2018

Keywords

• nonn

Comments

The number of cyclic permutations with at most 2 descents is equal to L(3,n)-n*L(2,n) where L(k,n) is the number of primitive necklaces (equivalently, the number of Lyndon words) of length n on k letters.

Links

• I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 189-215, (1993).

Crossrefs

Cf. A027376, A001037.

Programs

PARI

L2(n) = if(n>1, sumdiv(n, d, moebius(d)*2^(n/d))/n, n+1); \\ A001037
L3(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);  \\ A027376
a(n) = L3(n)-n*L2(n); \\ Michel Marcus, May 17 2018

Formula

a(n) = A027376(n) - n*A001037(n).

a(n) = L(3,n)-n*L(2,n) where L(k,n) is the number of primitive k-ary necklaces (or equivalently, Lyndon words) of length n.