On cardinality of involutions

149 Views Asked by At

Denote $S_n$ symmetric group on $n$ letters.

Denote $C_n$ to be set of cycles in $S_n$ of length $n$.

Denote $I_n$ to be set of involutions in $S_n$.

What are the cardinalities of $C_n$, $I_n$ and $I_n\cap C_n$?

What is the probability that a random member of $S_n$ is an involution?

1

There are 1 best solutions below

8
On BEST ANSWER

Each cycle of length $n$ corresponds to $n$ permutations of the $n$ letters, one for each of the $n$ possible points at which to break open the cycle. There are $n!$ permutations of the $n$ letters, so there are $\frac{n!}n=(n-1)!$ cycles of length $n$.

Suppose that $\sigma=(p_1p_2\ldots p_n)$ is an involution. Clearly

$$\sigma^2=(p_1p_3\ldots p_np_2p_4\ldots p_{n-1})$$

if $n$ is odd, and

$$\sigma^2=(p_1p_3\ldots p_{n-1})(p_2p_4\ldots p_n)$$

if $n$ is even. Suppose that $n\ge 3$; in both cases we have $p_1=\sigma^2(p_1)=p_3$, contradicting the assumption that $n\ge 3$, so $n\le 2$. I’ll leave the details of the cases $n=1$ and $n=2$ to you.

For $|I_n|$, try to show that the involutions are precisely the permutations that can be expressed as products of pairwise disjoint transpositions. Thus, you get one involution for every partition of $[n]=\{1,2,\ldots,n\}$ into sets of cardinality $1$ and $2$. To form such a partition, first choose a subset $S$ of $[n]$ whose members will be the fixed points of the permutation, and then count the partitions of $[n]\setminus S$ into pairs; this question and its answers may be helpful. You may want to consider separately the cases of odd and even $n$. You may also find that you have to leave the answer in the form of a summation.