1
$\begingroup$

I'm reading a recreational book about combinatorics, that discusses, in passing, the ways to 'induce' a permutation of the index set {1,2,3,4}.

The book notes that there is exactly:

  • 1 way to induce a permutation by an identity
  • C(4,2) = 6 ways to induce a permutation by interchanging exactly 1 pair of indices:
  • 1/2 C(4,2) = 3 ways to induce a permutation by interchanging exactly 2 pairs of indices:
  • 4*2 = 8 ways to induce a permutation that leaves 1 index unchanged
  • 4!/4 = 6 ways to induce a permutation by a cyclic permutation of all four indices,

which exhausts all 24 permutations of a 4 element set.

Question How do the authors calculate these numbers? Is there a way to generalise this approach to larger sets, for example 6 or 20 elements, and what would be the right terminology to use?

$\endgroup$
3
$\begingroup$

Let $n$ be the size of your set. Effectively the question you are asking is how many elements of each cycle type are in the permutation group $S_n$. If you want a permutation consisting of $C_j$ $j$-cycles when written as the product of disjoint cycles, with $k$ being the longest cycle length, then there are $$ \frac{n!}{\prod_{j=1}^k j^{C_j} C_j!} \qquad \star$$ distinct permutations of this form. If you don't like the group theory direction of my explanation, you can still check the formula works. But a little bit of group theory will go a long way in helping you understand the formula, the basic theory of $S_n$ will be in the first few chapters of any good introductory group theory book.

To go back to your example, set $n=4$.

The identity permutation is the unique element in $S_4$ that is the disjoint product of four $1$-cycles, it looks like $(1)(2)(3)(4)$, so it is a $1,1,1,1$-cycle. If you plug this cycle type description into the formula $\star$, you get $$ \frac{4!}{ 1^{4}\cdot 4!} =1$$

The number of $3$-cycles ("leave $1$ index unchanged") $$ \frac{4!}{ 1^{1}\cdot 1! \cdot 3^1\cdot 1!}= 8$$ because a general example of a $3$-cycle in $S_4$ is $(1\; 2\; 3)(4)$ The number of $4$-cycles ("induce a permutation by a cyclic permutation of all four indices") is $$ \frac{4!}{ 4^{1} 1!}=6 $$ The number of $2,2$-cycles ("induce a permutation by interchanging exactly 2 pairs of indices") is $$ \frac{4!}{ 2^{2}\cdot 2!}=3$$ The number of $2$-cycles ("induce a permutation by interchanging exactly 1 pair of indices") is $$ \frac{4!}{1^2\cdot 2^{1}\cdot 1!\cdot 2!}=6$$

To summarise, break your permutation down into disjoint parts, each index is written in one part of the cycle, including $1$-cycles. So $(1\; 2\; 3)(4)(5\; 6 )$ rather than $(1\; 5\; 2\; 3)(4\; 2)(5\; 6 )$ (not that these elements are the same!). You can always write a permutation as disjoint cycles. Then plug into $\star$ to get the number of permutations of that form.

$\endgroup$
1
  • $\begingroup$ Great answer. Thank you so much. $\endgroup$
    – m_cole
    Feb 7 '15 at 22: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.