# How to count the ways to induce a permutation?

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?

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.

• Great answer. Thank you so much. Feb 7 '15 at 22:16