Difficult permutation and inclusion-exclusion principle problem.

Question

An Engineering student is given 5 glasses, each containing a different type of beer. He is told the names of the beers but not which glasses they are in. After drinking each beer he names it. In how many ways can he get every answer wrong?

The answer to this problem is 44:

This question has me completely stumped. I know that you have to find all the possible ways he/she guesses the beer, which is just 5! = 120. But that's pretty much all I know, and after that, I have no idea what to do or how the inclusion-exclusion principle comes in.

Answer 1

Since it is difficult to count how many ways he get all guesses wrong, let us count the complement: how many ways he get at least one guess correct.

By PIE, it is $\sum_{i=1}^{5}{-(-1)^{i}\binom{5}{i}\times(5-i)!}=76$. Subtracting this from $120$ gives us $44$

Answer 2

This is called a derangement: a permutation in which every object changes position (here actual beer name and guessed name).

The number of ways is known as the subfactorial of $n$ or the $n$-th derangement number or $n$-th de Montmort number. It is denoted $!n$, where $!2 = 1$, $!3=2$ and in general:

$$!n = (n-1)(!(n-1) + !(n-2))$$

Indeed, $!5 = 44$, as you can check yourself.