Combinatorics question getting a probability Question:

A dealership has $n$ cars. An employee with a sense of humor takes all $n$ keys, puts one of them in each car at random, then locks the doors of all cars. When the owner of the dealership discovers the problem, he calls a locksmith. He tells him to break into a car, then use the key found in that car to open another, and so on. If and when the keys already recovered by this procedure cannot open any new cars, the locksmith is to break into another car. This algorithm goes on until all cars are open.
(a) What is the probability that the locksmith will only have to break into one car?
(b) What is the probability that the locksmith will have to break into two cars only?


HINTS: Number the cars from $1$ to $n$ arbitrarily. Give each key the same number as the car to which it belongs. The employee’s prank results in a permutation $\pi$ of $\{1,\dots,n\}$ in which Car $k$ contains Key $\pi(k)$. Write $\pi$ as a product of disjoint cycles.
Now say that the locksmith initially breaks into Car $1$; he will then be able to get into every car whose number is in the cycle containing $1$. Thus, he will need to break into only one car if and only if the permutation is a cycle. Similarly, he will need to break into two cars if and only if the permutation is a product of two disjoint cycles.


*

*How many permutations of $\{1,\dots,n\}$ are there?

*How many of them are cycles?

*How many of them are a product of two disjoint cycles?
Added: Here’s a little more help with the third question. To get a permutation with two cycles, you have to split $\{1,\dots,n\}$ into two non-empty subsets. Then you have to order each of these subsets to make it a cycle. You already know from (2) how many ways there are to order a set as a single cycle. Be a little careful, though: $(135)(24)$ and $(24)(135)$ are the same permutation.
