Derangement, gift exchange

Question

Five people have each bought their own Christmas gift. They put the gifts in a sack which then everyone can pull their gift from. In how many ways can the gifts be distributed so that no one gets the Christmas gift they have bought themselves?

So I have figured $93$ combinations in which only $1$ and then $2, 3$ or $4$ and $5$ get their gift but I haven't figured out how to calculate that other people don't get their gift. For example

If $2$ people get their gifts how do I count that the other $3$ don't get their own gifts etc? I have read about derangement and seen different formulas but I haven't quite understood the logic.

Answer 1

You can use the concept of derangement. It is derived from Principle of exclusion and inclusion, For example if there are two tasks- $A$ and $B$, let $A$: Getting right gift for person $1$ and $B$ be getting right gift for person $2$. Then you want: $U-(A \cup B)$

Which can also be expressed as total ways of $U - (A + B - A \cap B)$ i.e. total ways - number of ways in which Event $A$ happens- Event $B$ + Ways where $A$ and $B$ occur simultaneously. This whole process for a general scenario becomes $n!\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\cdots+ \frac{(-1)^n}{n!}\right)$.

Answer 2

the logic behind the formula for number of derangement is based on recurrence relations. assume Dn is the number of derangements for n objects. Dn=En+Fn where En= number of derangements in which the nth object swaps with one of the other n-1 objects and Fn= number of derangements in which the nth object doesn't swap with other objects. for example on 4 elements: 2 1 4 3 in this case the fourth element has swapped with the 3rd one hence it is counted as En. but in 4 3 2 1 a swap has not happened and it is counted as Fn. now it is time to calculate En and Fn. for En we have n-1 choices for the object we want to swap with the nth object and after we have chosen that, n-2 objects will be left which can freely have their own derangement, therefore: En=(n-1).Dn-2 now for Fn: since n doesn't swap with anything, some r goes to the nth place and there are obviously n-1 choices for r, now you are left with n-1 objects than can have their own derangement, so: Fn=n-1.Dn-2 and therefore, Dn=(n-1).(Dn-2 + Dn-1) what it left now is finding the closed form you have probably seen somewhere based on this recurrence relation. by doing some operations on the relation you can simply get Dn - n.Dn-1 = -(Dn-1 - (n-1).Dn-2) a crucial point you have to notice in here is that the expression on the left is the negative of the expression on the right (check for yourself) and by iterating on that we will get Dn - n.Dn-1 = (-1)^n. divide all terms by n! :

source: a first course in discrete mathematics, Ian Anderson

Answer 3

It sounds like you're reading an inclusion-exclusion argument, but are misunderstanding it. We number these people $1$ through $5$, and let $[5]$ denote the set $\{1,2,3,4,5\}$. For a subset $X$ of $[5]$, let $f(X)$ count the number of permutations such that every person in $X$ gets their own gift, and every person outside of $X$ gets someone else's gift. In other words, $f(X)$ counts the number of derangements of $[5]\setminus X$. In particular, $f(\varnothing)$ counts the number of derangements of $[5]$, which is what we want to count. The idea of this argument is that $f(X)$ is in general hard to compute, so we'll count it using a function that's easier to compute.

For $X\subseteq [5]$, let $g(X)$ count the number of permutations such that every person in $X$ gets their own gift, but people outside of $X$ may also get their own gift. While $f(X)$ counts the permutations where $X$ is exactly the set of people who get their own gift (in other words, permutations where $X$ is the set of fixed points), while $g(X)$ counts the permutations where at least everyone in $X$ gets their own gift (permutations such that the set of fixed points contains $X$).

While $f(X)$ is difficult to compute, $g(X)$ is easy to compute- we let everyone in $X$ get their own gift, and let everyone else in $[5]\setminus X$ get any of the remaining gifts, so $g(X)=(5-|X|)!$. Now we use the principle of inclusion-exclusion. To use inclusion-exclusion, we think of counting objects with certain properties. In this example, the objects are permutations of $[5]$, and the properties are that $1$ is a fixed point, $2$ is a fixed point, etc, so we have $5$ properties to consider. One phrasing of inclusion-exclusion is that if $f(X)$ counts objects with exactly the properties in $X$, and $g(X)$ counts objects with at least the properties in $X$, then we can relate $f$ and $g$ through the equation $$f(X)=\sum_{Y\supseteq X} (-1)^{|Y|-|X|}g(Y).$$

I won't go into detail on how this works, but it sounds like this is the type of proof that you're reading. We'll use the formula above, setting $X=\varnothing$ to count the number of derangements. We already know that $g(Y)=(5-|Y|)!$, so we can use that to solve for $f(\varnothing)$. Furthermore, since $g(Y)$ only depends on the size of $Y$, we can write $g(i)=g(Y)$ where $|Y|=i$. Then instead of iterating over all $Y\subseteq [5]$, we can just consider all $i$ from $0$ to $5$. For each $i$, we have $g(i)=(5-i)!$, and there are ${5\choose i}$ subsets of $[5]$ with size $i$. Thus, we have $$f(\varnothing)=\sum_{Y} (-1)^{|Y|}g(Y)=\sum_{i=0}^5 (-1)^i{5\choose i}(5-i)!=\sum_{i=0}^5 (-1)^i \frac{5!}{i!}.$$

The last equality uses the definition of ${5\choose i}$.