A306669 Number of aperiodic permutation necklaces of weight n.

1, 0, 1, 4, 23, 110, 719, 4992, 40302, 362492, 3628799, 39912804, 479001599, 6226974714, 87178289207, 1307673722880, 20922789887999, 355687417744992, 6402373705727999, 121645100223036700, 2432902008176115023, 51090942167993548790, 1124000727777607679999

Offset

1,4

Comments

A permutation is aperiodic if every rotation of {1...n} acts on the vertices of the cycle decomposition to produce a different digraph. A permutation necklace is an equivalence class of permutations under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Gus Wiseman, Inequivalent representatives of the a(5) = 23 aperiodic necklace permutations.

Formula

a(n) = A324514(n)/n.

a(n) = (1/n)*Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019

Mathematica

Table[Length[Select[Permutations[Range[n]], UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n, 1, k+1]]&, #, n-1]&]]/n, {n, 6}]

Prog

(PARI) a(n) = (1/n)*sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019

Crossrefs

Cf. A000031, A000740, A000939, A001037, A059966, A060223, A061417, A086675, A323861, A323865, A323866, A323871.

Cf. A324461, A324512, A324513, A324514.

Sequence in context: A082970 A197868 A017973 * A124507 A239813 A174248

Adjacent sequences: A306666 A306667 A306668 * A306670 A306671 A306672

Keyword

nonn

Author

Gus Wiseman, Mar 04 2019

Extensions

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

Status

approved