login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
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

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]

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

Sequence in context: A123985 A219953 A286075 * A099030 A264657 A190658

Adjacent sequences:  A089063 A089064 A089065 * A089067 A089068 A089069

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 03:01 EST 2018. Contains 317427 sequences. (Running on oeis4.)