1. ## Problem 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?

2. 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

3. Originally Posted by phillipshwong
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?

Partial Derangement -- from Wolfram MathWorld

Rencontres numbers - Wikipedia, the free encyclopedia

4. Hello, phillipshwong!

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

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

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

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

I think I understand their reasoning . . .

$\,n$ people get their hats back.

The other $N-n$ people may or may not get their hats back.

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

This is very sloppy work!

If they meant exactly $\,n$ get their hats,
. . the problem is more complicated.

$\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 $N-n$ people must not get their own hats.
. . This is derangement of the $N-n$ hats,
. . which can be written: $d(N-n).$

Example:
. . 8 people, 8 hats.
. . Find the number of ways that exactly 3 get their hats.

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

The other 5 people must not get their own hats.
. . There are: . $d(5) \:=\:44$ ways. .**

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

**
The Derangement Formula is a topic best left for a separate lesson.
Or you can do a search for "derangement".

5. Originally Posted by Soroban
Hello, phillipshwong!

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

I think I understand their reasoning . . .

$\,n$ people get their hats back.

The other $N-n$ people may or may not get their hats back.

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

This is very sloppy work!

If they meant exactly $\,n$ get their hats,
. . the problem is more complicated.

$\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 $N-n$ people must not get their own hats.
. . This is derangement of the $N-n$ hats,
. . which can be written: $d(N-n).$

Example:
. . 8 people, 8 hats.
. . Find the number of ways that exactly 3 get their hats.

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

The other 5 people must not get their own hats.
. . There are: . $d(5) \:=\:44$ ways. .**

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

**
The Derangement Formula is a topic best left for a separate lesson.
Or you can do a search for "derangement".

I am waiting for that other lesson.

6. Originally Posted by phillipshwong
I am waiting for that other lesson.
You need to understand that what Soroban said was very probably a figure of speech and is code for "I don't have the time and MHF is not the place for teaching a course on combinatorics." I suggest you research these things yourself.

7. 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)!