3
$\begingroup$

I was going through this link.Suppose that there are n persons who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:

A) Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons and n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).

B) Person i takes the hat 1. Now the problem reduces to n − 2 persons and n − 2 hats.

From this, the following relation is derived: !n = (n - 1) (!(n-1) + !(n-2))

I have a hard time understanding point B and the equation derived. I was trying to understand with an example of 4 people named A, B, C and D and the corresponding hats A, B, C and D. Everyone of them are supposed to wear any hat except their own matching hat i.e. A can wear B, C or D.

If suppose A wears B hat so we will be left with only 3 people and 3 hats. So I can understand "(n-1)!(n-1)" part but what i didn't understand is part B(marked above). Can anyone help?

$\endgroup$
  • 1
    $\begingroup$ This is a math question and belongs to math.se. $\endgroup$ – Yuval Filmus Nov 25 '15 at 14:59
2
$\begingroup$

Suppose person 1 wears hat 2 and person 2 wears hat 1. People 3 up to $n$ have hats 3 up to $n$ remaining to them. The assignment of hats to the first to people can be completed to a derangement by any derangement of people 3 and up. Since there are $n-2$ people 3 and up, the problem reduces to $n-2$ people (people 3 and up) and $n-2$ hats (hats 3 and up).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint:The general formula for dearrangements is $n![1-\frac{1}{1!}+\frac{1}{2!}...\frac{(-1)^n}{n!}]$. now you can plug in your values and get the required answer. Note sometimes we actuallly need to do some mental stuff even if if the formula is available

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I had exactly the same question. but my confusion is why !(n - 1) and !(n - 2) are exclusive. I thought they should be related to each other.

expand on the scenario of 4 helps, following my intuition

!(4) = 3 * !(3) = 3 * 2 = 6 // wrong

expand more.

2 (1 3 4) //suppose 2 is taken as the first 
// !(3) means 1 should not be on 1, 3 not at second and 4 not at third.
// clear that 1 could be at first position 
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.