It is Question 70 on page 176 in Ross's book (Introduction to Probability Models-11th edition)
Let N denote the number of cycles that result in the match problem.
Original Match Problem(Example 3.26 on page 120)
At a party n men take off their hats. The hats are then mixed up and each man randomly selects one.
(d)Find the probability that $1,2,...,k$ is a cycle.
To build a cycle of size k. I think it can be done in the following way.
Step 1:
Man 1 chooses 1 hat from hats $2,...,k$.
Step 2:
If hat 2 is chosen ,then man 2 choose 1 hat from the left hats except the hat of the man 1, then the owner of the hat which chosen by man 2, continues to choose 1 hat from the left hat except the hat of man 1.
Final Step:
Finally,the last man chooses the hat of man 1.
In case of there are 4 people, the possible ways to build a cycle is $(4-1)!$ .
owner:1 2 3 4
3 1 4 2 #man 1 chooses man 2's hat,man 2 chooses man 4's hat, man 4 chooses man 3's hat, man 3 chooses man 1's hat.
4 1 2 3
2 4 1 3
4 3 1 2
3 4 2 1
2 3 4 1
Let A denotes 1,2,...,k is a cycle.
For each possible way of forming a cycle, the other hats can be a full permutation of size $(n-k)$
So that $P(A)$ = $(k-1)! * (n-k)!/n!$
But the Solution says: $P(A)$ = $(n-k)!/n!$
I am not sure which is correct. Any Help will be greatly appreciated.
