There are N people. All with their own, unique hat. Each throw his hat into a pile, and mix it. The number of ways for n < N to get their hats is ( N-n)!. Why?

Printable View

- Dec 19th 2010, 08:56 PMphillipshwongProblem of hats
There are N people. All with their own, unique hat. Each throw his hat into a pile, and mix it. The number of ways for n < N to get their hats is ( N-n)!. Why?

- Dec 19th 2010, 09:07 PMpickslides
To understand these problems I take N to be a smallish number i.e. N=3, then find the number of arrangements for n=1,2.

Then take N=4 and find the number of arrangements for n=1,2,3

Finally take N=5 and find the number of arrangements for n=1,2,3,4 you'll start to see the pattern.

;D - Dec 20th 2010, 12:10 AMmr fantastic
- Dec 20th 2010, 06:10 AMSoroban
Hello, phillipshwong!

The problem is badly worded.

Perhaps it was written by an amateur, a student . . .

Quote:

$\displaystyle \text{There are }N\text{ people, each with a unique hat.}$

$\displaystyle \text{The hats are mixed and returned to them at random.}$

$\displaystyle \text{The number of ways for }n\text{ people to get their hats is }(N-n)!\;\text{ Why?}$

II understand their reasoning . . .*think*

$\displaystyle \,n$ people get their hats back.

The other $\displaystyle N-n$ peopleget their hats back.*may or may not*

. . And there are $\displaystyle (N-n)!$ ways to return those hats.

This is very sloppy work!

If they meant$\displaystyle \,n$ get their hats,*exactly*

. . the problem is more complicated.

$\displaystyle \text{There are: }\:_NC_n \:=\:{N\choose n}\text{ ways to select the }n \text{ lucky people.}$

The original problem did not consider this.

The other $\displaystyle N-n$ people mustget their own hats.*not*

. . This isof the $\displaystyle N-n$ hats,*derangement*

. . which can be written: $\displaystyle d(N-n).$

Example:

. . 8 people, 8 hats.

. . Find the number of ways that**exactly 3**get their hats.

There are: .$\displaystyle _8C_3 \:=\:{8\choose3} \:=\:56$ choices of the 3 people.

The other 5 people mustget their own hats.*not*

. . There are: .$\displaystyle d(5) \:=\:44$ ways. .**

Therefore, there are: .$\displaystyle 56\cdot44 \:=\:2464$ ways.

**

The Derangement Formula is a topic best left for a separate lesson.

Or you can do a search for "derangement".

- Dec 22nd 2010, 04:51 PMphillipshwong
- Dec 22nd 2010, 09:10 PMmr fantastic
- Dec 23rd 2010, 10:07 AMphillipshwong
That is ok, since I don 't have time for a course, or that concern with d(i). I already figure out why it is ( N-n)!