Inclusion and Exclusion Secret Santa

Question

If I am having a "secret santa" gift exchange with 5 people, how many possibilities for gift exchanges are there if nobody ends up with the same gift?

The answer could be $5!$ , but I don't think it is correct as the first person only has $4$ options for exchanging their gift.

An idea I had is $4*4*3*2*1$ , as the first person has $4$ options to exchange, then the second person should also have $4$ options, because the gift exchange taken by the first person could have been with the second person's gift.

Answer 1

This is known as derangements. It turns out that the number of permutations of $n$ elements such that none ends up in its place is: $$ D_n = n! \sum_{0 \le k \le n} \frac{(-1)^k}{k!} \approx \frac{n!}{e} $$

Answer 2

Consider first all possible assignments of gifts, with as only condition that every person gets one gift. As you guessed this gives $5!=120$ possibilities. But among those there are possibilities where the first person gets her own gift. In fact the number of ways this arises is $4!=24$, since the remaining persons are exchanging gifts among each other, with no restrictions. Butit may also happen that the second person gets his own gift, again in $4!$ ways. Or the third, fourth or fifth person. Taking account of all these forbidden possibilities, there remain $$ 5!-4!-4!-4!-4!-4!= 5! -5\times 4! = 120 - 120 = 0\text{ possibilities.} $$ That's right, we've eliminated as many solutions as there were, so there aren't any left. Or are there? Well we did genuinely rule out a possibility $120$ times, but fortunately they wern't all different. Consider a solution where the first two people get their own gift, but nobody else. That possibility would have been ruled out twice, but it was present only once, so we have to add it back once to get even. We also have to worry about solutions where $3$ people get their own gift, or $5$ (can you see why $4$ cannot happen?), and which would have to ne added back $2$ respectively $4$ times to get even.

We could count and each of these categories exactly, but that would hardly be simpler than the original problem; the philosophy of inclusion-exclusion is to first add back all solutions where the first two (and posibly more) get their own gift, and the same for the first and third, and so forth for all $\binom52=10$ pairs, and then start worrying about solutions where at least three people get their own gift. So we are adding back $10\times3!=60$ solutions here. So far we have computed $$ 5!-\binom51\times4!+\binom52\times3! = 5!-\frac{5!}{1!}+\frac{5!}{2!} =5!(1-\frac11+\frac12)=60. $$ We still need to worry about solutions where for instance the first three all get their own gift; such solutions have been counted once, then subtracted thrice, then added back $\binom32=3$ times, so all in all they have contributed once, although they are not legal solutions. Subtract off $\binom532!$ to get the solutions with exactly three gift returning to their sender accounted for properly.

You should see a pattern emerging here. By the time you get to accounting correctly even the possibility where everybody gets his/her own gift, you will have found the formula cited by vonbrand.

Answer 3

One simple way to get $D_n$, the number of derangements of $n$ elements: If a permutation of $n$ elements has exactly $k$ fixed points, then the other $n - k$ elements are deranged. The fixed points can be selected in $\binom{n}{k}$ ways, so there are $\binom{n}{k} D_{n - k}$ permutations with $k$ fixed points. As all permutations have fixed points (0, 1, ..., $n$ of them), and there are $n!$ permutations in all: $$ n! = \sum_{0 \le k \le n} \binom{n}{k} D_{n - k} = \sum_{0 \le k \le n} \binom{n}{k} D_k $$ To get this recurrence going, $D_0 = 1$ (with no elements, there is no one which could be out of place in the $0! = 1$ ways to reorder them). This gives $1! = D_0 + D_1$, and as $D_1 = 0$ (no way to have 1 element out of place in 1 elements) this checks out.

If you want to go a step further, define the exponential generating function: $$ d(z) = \sum_{n \ge 0} D_n \frac{z^n}{n!} $$ The point is that if $A(z)$ and $B(z)$ are the exponential generating functions of the sequences $\langle a_n\rangle$ and $\langle b_n \rangle$, then: $$ A(z) \cdot B(z) = \sum_{n \ge 0} z^n \sum_{0 \le k \le n} \binom{n}{k} a_k b_{n - k} $$ Take the nice recurrence, multiply by $z^n/n!$ and sum over $n \ge 0$. $$ \frac{1}{1 - z} = e^z d(z) $$ I.e., $$ d(z) = \frac{e^{-z}}{1 - z} $$ Now, if $A(z) = \sum_{n \ge 0} a_n z^n$ then: $$ \frac{A(z)}{1 - z} = \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_k $$ In our case this gives: $$ \frac{D_n}{n!} = \sum_{0 \le k \le n} \frac{1}{k!} $$