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

%I #17 Mar 04 2019 23:08:23

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

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

%C 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.

%C 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.

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

%C 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.

%C 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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>.

%H Gus Wiseman, <a href="/A275527/a275527.png">Inequivalent representatives of the a(5) = 12 path necklaces</a>.

%H Gus Wiseman, <a href="/A275527/a275527_1.png">Inequivalent representatives of the a(6) = 54 path necklaces</a>.

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

%e Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.

%e n=4 case addition mod n and reversal

%e 1234, 1243, 1324, 1423.

%e n=4 case rotation and complement

%e 1234, 1243, 1324, 1342.

%e .

%e n=5 case addition mod n and reversal

%e 12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.

%e n=5 case rotation and complement

%e 12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.

%t rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];

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

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

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

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

%K nonn,more

%O 1,4

%A _Olivier GĂ©rard_, Jul 31 2016