cp's OEIS Frontend

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

%I A275527 #17 Mar 04 2019 23:08:23
%S A275527 1,1,1,4,12,64,360,2544,20160,181632
%N A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.
%C A275527 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 A275527 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 A275527 It seems probable that a(2n+1) = (2n)!/2
%C A275527 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 A275527 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 A275527 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>.
%H A275527 Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>.
%H A275527 Gus Wiseman, <a href="/A275527/a275527.png">Inequivalent representatives of the  a(5) = 12 path necklaces</a>.
%H A275527 Gus Wiseman, <a href="/A275527/a275527_1.png">Inequivalent representatives of the  a(6) = 54 path necklaces</a>.
%F A275527 (Conjecture). If n odd a(n)=((n - 1))!/2. If n even a(n)= 1/2 (n - 2)!! (1 + ( n - 1)!!).
%e A275527 Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.
%e A275527 n=4 case addition mod n and reversal
%e A275527 1234, 1243, 1324, 1423.
%e A275527 n=4 case rotation and complement
%e A275527 1234, 1243, 1324, 1342.
%e A275527 .
%e A275527 n=5 case addition mod n and reversal
%e A275527 12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.
%e A275527 n=5 case rotation and complement
%e A275527 12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.
%t A275527 rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
%t A275527 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 A275527 Cf. A000939, A000940, A002619, A089066, A262480 (other symmetry classes of permutations).
%Y A275527 Cf. A193651 (inspiration for a(2n)).
%Y A275527 Cf. A000031, A006125, A008965, A059966, A060223, A192332, A323858, A323870, A324461.
%K A275527 nonn,more
%O A275527 1,4
%A A275527 _Olivier Gérard_, Jul 31 2016