Find the number of permutations in $S_n$ containing fixed elements in one cycle

Question

Find the number of permutations in $S_n$ such as 1 and 2 belong to one cycle.

Answer 1

Hint

Let $X \subseteq S_n$ be the set of all permutations having $1$ and $2$ in separate cycles and $Y \subseteq S_n$ the set of all permutations having $1$ and $2$ in the same cycle.

Show that the mapping $f : X \to Y$ which "glues together" the two cycles containing $1$ and $2$ (cycles written down such that they start with $1$ and $2$, resp.) is a bijection.

Example in $S_7$: $$f((1,7,4)(2,6)(3,5)) = (1,7,4,2,6)(3,5).$$

Remark

As pointed out by P.. below, the mapping rule of $f$ can be written as $$ \sigma \mapsto (1,2)\sigma $$

Answer 2

We can also compute this by direct enumeration. Suppose we ask about the probability that a random subset $Q$ containing $m$ elements ends up on the same cycle in a permutation of $n$ elements. If the $m$ elements are on a cycle of length $r\ge m$ then we need to choose the remaining $r-m$ elements and interleave the elements of $Q$ with these extra elements. This gives $$\sum_{r=m}^n {n-m\choose r-m} \frac{r!}{r} (n-r)! = \sum_{r=0}^{n-m} {n-m\choose r} (r+m-1)! (n-m-r)!$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now in the present case we clearly have $$A(z) = \sum_{q\ge 0} (q+m-1)! \frac{z^q}{q!} = (m-1)! \sum_{q\ge 0} {q+m-1\choose q} z^q = \frac{(m-1)!}{(1-z)^m}.$$ Furthermore we have $$B(z) = \sum_{q\ge 0} q! \frac{z^q}{q!} = \sum_{q\ge 0} z^q = \frac{1}{1-z}.$$ It follows that the sum is given by $$(n-m)! [z^{n-m}] A(z) B(z) = (n-m)! [z^{n-m}] \frac{(m-1)!}{(1-z)^{m+1}}\\ = (n-m)! (m-1)! {n-m+m\choose n-m} = (m-1)! \frac{n!}{m!} = \frac{n!}{m}.$$ Therefore the desired probability is $$\frac{1}{n!} \frac{n!}{m} = \frac{1}{m}.$$

This can also be done using exponential generating functions as shown at this Wikipedia entry.