5
$\begingroup$

An equivalence class of permutations has come up in my research, and I'm wondering if anybody knows if it's named or has been studied before. If so, I'd appreciate being pointed towards more information.

Specifically, two permutations are considered equivalent if they have the same cycle decomposition, up to inverses of the cycles. So, for example, the permutations:

$(123)(456) \equiv (132)(456) \equiv (123)(465) \equiv (132)(465)$

And generally, if the $\sigma_{i}$ are disjoint cycles, then all permutations

$\sigma_{1}^{\pm}\sigma_{2}^{\pm} \cdots \sigma_{k}^{\pm}$

are equivalent. As I said, if anybody has seen this before and could point me towards information about it, I'd be most appreciative. Thank you!

$\endgroup$
  • 3
    $\begingroup$ So two permutations are equivalent if and only if the underlying undirected graphs of their cycle digraphs are identical. But no, I haven't met this before. $\endgroup$ – darij grinberg Mar 3 '19 at 8:24
7
$\begingroup$

If $f(n)$ is the number of equivalence classes, then $$ \sum_{n\geq 0} f(n)\frac{x^n}{n!} = \frac{\exp\left(\frac x2+ \frac{x^2}{4}\right)}{\sqrt{1-x}}. $$ This goes back to Frobenius. It is also the number of distinct monomials in the expansion of the determinant of an $n\times n$ generic symmetric matrix. See Enumerative Combinatorics, vol. 2, Example 5.2.9. Exercise 5.18 is similar.

$\endgroup$
  • $\begingroup$ Thank you, Prof Stanley. And yes, the distinct monomials in the expansion of the determinant of an $n \times n$ generic symmetric matrix is the context under which I'm seeing this. $\endgroup$ – Dylan Zwick Mar 3 '19 at 16:55

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.