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,4

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

Links

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

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.

Formula

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

Example

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.

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

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.

Sequence in context: A353452 A071769 A221667 * A222612 A339134 A000843

Adjacent sequences: A275524 A275525 A275526 * A275528 A275529 A275530

Keyword

nonn,more

Author

Olivier Gérard, Jul 31 2016

Status

approved