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.
Best Answer
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.