login
A306669
Number of aperiodic permutation necklaces of weight n.
5
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).
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2019
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019
STATUS
approved