A304200 a(n) is the number of cyclic permutations with at most 2 ascents.

1, 1, 1, 2, 6, 18, 58, 186, 570, 1680, 4878, 14058, 40200, 114450, 325290, 923846, 2624730, 7465410, 21261828, 60647370, 173288724, 496014934, 1422223506, 4084793082, 11751102060, 33857989968, 97697014590, 282295318536, 816759712080, 2366027865810, 6861964439314

Offset

0,4

Comments

a(n) is the number of cyclic permutations with at most two ascents. These permutations can also be characterized as admitting a [1, 1, 1]-gridding, meaning they are composed of three contiguous increasing segments.

Links

Table of n, a(n) for n=0..30.

K. Archer and S. Elizalde, Cyclic permutations realized by signed shifts, Journal of Combinatorics, 5 (2014), 1-30.

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

Formula

a(n) = L(3,n) - n*L(2,n) when n !== 2 (mod 4) and n>2;

a(n) = L(3,n) + L(3,n/2) - n*(L(2,n) + L(2,n/2)) when n == 2 (mod 4) and n>2;

where L(k,n) is the number of k-ary Lyndon words of length n.

Prog

(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) = if (n <=2, 1, if ((n % 4) != 2, L3(n) - n*L2(n), L3(n) + L3(n/2) - n*(L2(n) + L2(n/2)))); \\ Michel Marcus, May 16 2018

Crossrefs

Equals A303117 when n !== 2 (mod 4).

Cf. A001037, A027376.

Sequence in context: A355388 A351787 A307755 * A081057 A000137 A151282

Adjacent sequences: A304197 A304198 A304199 * A304201 A304202 A304203

Keyword

nonn

Author

Kassie Archer, May 07 2018

Status

approved