The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089066 Number of distinct classes of permutations of length n under reversal, rotation and complement to n+1. 4
1, 1, 1, 3, 8, 38, 192, 1320, 10176, 91296, 908160, 9985920, 119761920, 1556847360, 21794734080, 326920043520, 5230700052480, 88921882828800, 1600593472880640, 30411275613143040, 608225502973132800 (list; graph; refs; listen; history; text; internal format)



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.


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.


Table of n, a(n) for n=1..21.

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.


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


n=5 case rotation, reversal, complement


n=5 case translation mod, reversal, complement



(* 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}]


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)).

Sequence in context: A123985 A219953 A286075 * A099030 A264657 A190658

Adjacent sequences:  A089063 A089064 A089065 * A089067 A089068 A089069




Ray Jerome, Dec 02 2003, Jul 17 2007


Definition changed and cross-references added by Olivier Gérard, Jul 31 2016



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 06:56 EDT 2021. Contains 346273 sequences. (Running on oeis4.)