OFFSET
1,4
COMMENTS
Contribution from Olivier Gérard, Jul 31 2016: (Start)
Let us consider two permutations to be equivalent if they can be obtained from each other by reversal (12345->54321), cyclic rotation (12345->(23451,34512,45123,51234), n+1-complement (31254->35412), or a combination of those three transformations (they commute with each other). a(n) is the number of classes. It is strictly inferior to (n-1)! for n>1.
If rotation is replaced by addition of a constant modulo n, one obtains the same number of classes but not exactly the same permutations starting n=5.
(End)
Original explanation by R. Jerome : Generate all permutations of a string of length n, such as 1234, which has length 4; there are n!=24 of these. Now remove all that have cycles less than 4 characters long; if you only use cyclic notation and not array notation then of the n! possibly only (n-1)! need to be considered. Then calculate the Inverse, Vertical reflection, [VErt reflection inverse], Rotation by 180 degree and [ROt by 180 deg inverse]. If any of these already exist on the list then this permutation is not distinct. Items in []'s are unnecessary since VE(x)=V(I(x))=I(V(x))=R(x) and RO(x)=R(I(x))=I(R(x))=V(x). There are some that are rotationally symmetric and some that are vertically symmetric (only possible for even lengths), but the majority are nonsymmetric.
LINKS
J. Gebel, Integer points on Mordell curves [Cached copy, after the original web site tnt.math.se.tmu.ac.jp was shut down in 2017]
Samuel Herman, Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
R. Jerome, Information for Unique Permutations.
EXAMPLE
Examples of permutations (notations of R. Jerome):
Rotationally symmetric: x1=R(x1)=124356=VE(x1), I(x1)=165342=V(x1)=RO(x1)
Vertically symmetric: x2=V(x2)=132645=RO(x2)), I(x2)=154623=R(x2)=VE(x2)
Nonsymmetric: x3=135264, I(x3)=146253, R(x3)=152463=VE(x3), V(x3)=136425=RO(x3)
a(4)=3: there are 3 distinct permutations of exactly length 4, out of a field of 4!=24 possible permutations. In cyclic notation they are designated (1234), (1243) and (1324). The others, (1342), (1423) and (1432), are equal to inverses, vertical mirror images or 180-degree rotations of those 3. The remaining 18 have cycles of length 1, 2 or 3, such as (143)(2) having a permutation of length 3 and a fixed cycle and (14)(23) having 2 permutations of length 2.
Examples of permutation representatives (from Olivier Gerard)
The representative is chosen to be the first of the class in lexicographic order.
n=4 both cases
1234,1243,1324
n=5 case rotation, reversal, complement
12345,12354,12435,12453,12534,13425,13524,14325
n=5 case translation mod, reversal, complement
12345,12354,12435,12453,12534,13425,13452,13524
MATHEMATICA
(* From the formula in A099030 *)
a[n_] := If[n < 3, 1, 1/4 If[Mod[n, 2] == 0, ((n - 1)! + (n/2 + 1) (n - 2)!!), ((n - 1)! + (n - 1)!!)]]; Table[a[n], {n, 1, 20}]
CROSSREFS
Apart from initial terms, same as A099030. - Ray Jerome, Feb 25 2005
Cf. A000939 (same idea under (rotation, addition mod n and reversal) or (rotation, addition mod n and complement)).
Cf. A000940 (same idea under (rotation, addition mod n, reversal and complement)).
Cf. A001710 (shifted, same idea under (rotation and reversal) or (addition mod n and complement)).
Cf. A002619 (same idea under (rotation and addition mod n)).
Cf. A262480 (same idea under (reversal and complement)).
cf. A275527 (same idea under (rotation and complement) or (addition mod n and reversal)).
KEYWORD
nonn
AUTHOR
Ray Jerome, Dec 02 2003, Jul 17 2007
EXTENSIONS
Definition changed and cross-references added by Olivier Gérard, Jul 31 2016
STATUS
approved