1
$\begingroup$

I want to know about the properties of permutations when you ignore the specific elements that were permuted and instead look out how they were permuted.

For example, with permutations of the digits 1, 2, 3 we have six

  • 123 A
  • 132 B
  • 213 B
  • 231 C
  • 312 C
  • 321 B

But I want to group them in equivalence classes according to the letters. A is the identity, B is a single swap, and C is a rotation. In this case you can look at the number of fixed points to get the equivalence classes, but for larger numbers that doesn't work. For example for four we have two classes with no fixed points

  • 2143
  • 2341

Another way to think of it is as digraphs where every node has indegree=outdegree=1 and graphs are equivalent if they are isomorphic.

Is there a name for this kind of permutation? I'm having great difficulty looking it up.

$\endgroup$
  • $\begingroup$ There are two (and probably more) important gradings of permuatations. Firstly by the number of cycles giving the Stirling numbers of the first kind en.wikipedia.org/wiki/… Secondly by the number of ascents, giving the Euler numbers en.wikipedia.org/wiki/Eulerian_number#Basic_properties $\endgroup$ – Donald Splutterwit Nov 1 '17 at 20:41
  • $\begingroup$ @DonaldSplutterwit number of cycles is necessary but not sufficient for determining equivalence so Stirling is out, and ascents are sensitive to the kind of relabeling I'm thinking about so Eulerian numbers don't fit either $\endgroup$ – Max Nov 1 '17 at 20:56
2
$\begingroup$

$S_4$ (the set of permutations of 4 elements) has:

an identity

6 single transpositions. eg $2134$

3 double transpositions. eg $2143$

8 "3 cycles" or elements of order 3. i.e. one number is stabilized and there are two ways to exchange the remaining 3 elements. eg $3124$

6 elements of order 4. eg $2341$

These are called conjugacy classes.

For any element in a class, conjugation with any element in the group will take you to another element in the conjugacy class. i.e. $gAg^{-1} = A$

Sounds like you want to look up conjugacy classes of symmetric groups.

$\endgroup$
  • $\begingroup$ I agree, but I'm looking for the general term so I can research this further. S3 has three such classes, S4 has five as you have pointed out. What do you call them and how does it generalize? $\endgroup$ – Max Nov 1 '17 at 20:48
  • $\begingroup$ Some more terminology to look up for this specific case: the conjugacy classes of $S_n$ can be put into a canonical bijection with the set of partitions of $n$. One definition of a partition of $n$ would be as a multiset of positive integers whose sum is $n$. (So it's also equivalent to a sequence $(\pi_1, \ldots, \pi_n)$ such that $\sum_{k=1}^n k \pi_k = n$.) $\endgroup$ – Daniel Schepler Nov 1 '17 at 20:56
  • $\begingroup$ Max, look up cycle notation for permutations, if you aren't familiar with it. It makes the notions of conjugacy classes and relabeling very transparent, in a way that writing the permutations as linear orderings does not. $\endgroup$ – Ned Nov 2 '17 at 0:06
  • $\begingroup$ Also, a common generalization of "relabeling" permutations is "conjugation" in groups and other contexts, if you want a term to search. $\endgroup$ – Ned Nov 2 '17 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.