# hat-cycle probability in hat-match problem

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.

The book is considering that the cycle must be specifically $1 \to 2 \to 3 \ldots k \to 1$. You are considering all possible orders of those numbers that form a cycle. You are both right for the problem you are trying to solve.

• I guess you are right. Thanks Commented Mar 15, 2018 at 4:15