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

 A: 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
$$
A: 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.
