A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

1, 1, 1, 4, 12, 64, 360, 2544, 20160, 181632

Offset: 1

Author

Olivier Gérard, Jul 31 2016

Keywords

• nonn
• more

Comments

Let us consider two permutations to be equivalent if they can be obtained from each other by cyclic rotation (12345->(23451,34512,45123,51234) or n+1-complement (31254->35412), or a combination of those two transformations (they commute with each other). a(n) is the number of classes.

We obtain the same number of classes if the transformations are (addition of a constant modulo n and reversal (12345->54321)) but not the same set of representatives.

It seems probable that a(2n+1) = (2n)!/2

This sequence may be related to A113247 (and A113248) as they share a common dissection 1, 4, 64, 2544, 181632. The fact that they count permutation classes for the major index is a further indication.

Number of path necklaces, defined as equivalence classes of (labeled, undirected) Hamiltonian paths under rotation of the vertices. The cycle version is A000939. - Gus Wiseman, Mar 02 2019

Examples

			Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.
n=4 case addition mod n and reversal
1234, 1243, 1324, 1423.
n=4 case rotation and complement
1234, 1243, 1324, 1342.
.
n=5 case addition mod n and reversal
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.
n=5 case rotation and complement
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.
		

Links

• Wikipedia, Hamiltonian path.
• Wikipedia, Necklace (combinatorics).
• Gus Wiseman, Inequivalent representatives of the a(5) = 12 path necklaces.
• Gus Wiseman, Inequivalent representatives of the a(6) = 54 path necklaces.

Crossrefs

Cf. A000939, A000940, A002619, A089066, A262480 (other symmetry classes of permutations).

Cf. A193651 (inspiration for a(2n)).

Cf. A000031, A006125, A008965, A059966, A060223, A192332, A323858, A323870, A324461.

Programs

Mathematica

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

Formula

(Conjecture). If n odd a(n)=((n - 1))!/2. If n even a(n)= 1/2 (n - 2)!! (1 + ( n - 1)!!).