5
$\begingroup$

On the Wikipedia page on derangements, the following description is given about how to count derangements:

Suppose that there are $n$ persons numbered $1,2,\ldots,n$. Let there be $n$ hats also numbered $1,2,\ldots,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 first person takes the hat $i$. There are $n-1$ ways for the first person to choose the number $i$. Now there are 2 options:

A. Person $1$ does not take the hat $i$. This case is equivalent to solving the problem with $n − 1$ persons $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 $1$ takes the hat $i$. Now the problem reduces to $n − 2$ persons and $n − 2$ hats.

Aren't the two bolded statements in contradiction? Isn't the "first person" and "person 1" the same person? Is this explanation misworded?

$\endgroup$

1 Answer 1

6
$\begingroup$

There was a mistake in the article; the people were reversed. It should have read,

A. Person i does not take hat 1. ...

B. Person i takes hat 1. ...

I've fixed it on Wikipedia.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .