1,2

If permutations are converted to (i,p(i)) permutation arrays, then this automorphism is obtained by their "SW-NE diagonal toroidal shifts" (see Matthias Engelhardt's Java program in A006841), while the Maple procedure below converts each permutation to a siteswap pattern (used in juggling), rotates it by one digit and converts the resulting new (or same) siteswap pattern back to a permutation.

When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.

T. D. Noe, Table of n, a(n) for n=1..100

Index entries for sequences related to necklaces

a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!)

If I have a five-element permutation like 25431, in cycle notation (1 2 5)(3 4), I mark the numbers 1-5 clockwise onto a circle and draw directed edges from 1 to 2, from 2 to 5, from 5 to 1 and a double-way edge between 3 and 4. All the 5-element permutations that produce some rotation (discarding the labels of the nodes) of that chord diagram belong to the same equivalence class with 25431. The sequence gives the count of such equivalence classes.

Algebraic formula: with(numtheory); SSRPCC := proc(n) local d, s; s := 0; for d in divisors(n) do s := s + phi(n/d)*((n/d)^d)*(d!); od; RETURN(s/n); end;

Empirically: with(group); SiteSwapRotationPermutationCycleCounts := proc(upto_n) local b, u, n, a, r; a := []; for n from 1 to upto_n do b := []; u := n!; for r from 0 to u-1 do b := [op(b), 1+PermRank3R(SiteSwap2Perm1(rotateL(Perm2SiteSwap2(PermUnrank3Rfix(n, r)))))]; od; a := [op(a), CountCycles(b)]; od; RETURN(a); end;

PermUnrank3Rfixaux := proc(n, r, p) local s; if(0 = n) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Rfixaux(n-1, r-(s*((n-1)!)), permul(p, [[n, n-s]]))); fi; end;

PermUnrank3Rfix := (n, r) -> convert(PermUnrank3Rfixaux(n, r, []), 'permlist', n);

SiteSwap2Perm1 := proc(s) local e, n, i, a; n := nops(s); a := []; for i from 1 to n do e := ((i+s[i]) mod n); if(0 = e) then e := n; fi; a := [op(a), e]; od; RETURN(convert(invperm(convert(a, 'disjcyc')), 'permlist', n)); end;

Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul)

A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.

A064636 (derangements-the same automorphism).

A061417[n] = A064649[n]/n

Sequence in context: A123429 A006841 A003223 this_sequence A153921 A060315 A148111

Adjacent sequences: A061414 A061415 A061416 this_sequence A061418 A061419 A061420

nonn,easy,nice

Antti Karttunen May 02 2001