N people play Secret Santa. They draw their names out of a box where:
- A person draws a name from the box
- If they draw their own name the game is failed
- Else the next person draws a name and this process repeats
I am trying to find how many failed games occurred for N people.
At first I thought this could be simply calculated by doing permutations – derangements, however this has extra permutations with numbers/people after the collision (which does not need to be accounted for since the game has failed and should start again)
I then looked at permutations with a single fixed point however the same issue arises.
Example:
For 2 people either the first person draws the others name and second draws the first players name OR the first person pick there name and the game fails. Hence for N=2, the number of failed games is 1.
Does anyone know how I could exclude these extra combinations from my approach or perhaps another way I could solve this problem?
Best Answer
Suppose the players are numbered $1$ to $n$, they draw their names in numerical order, and player number $k+1$ is the first player to draw their own name. The number of ways the first $k$ people can choose numbers so that none of them draw their own name, and none of the draw name number $k+1$, can be found using the principle of inclusion-exclusion, similar to how the number of derangements are counted. The result is $$ \sum_{i=0}^k(-1)^i\binom{k}i \frac{(n-1-i)!}{(n-1-k)!} $$ Therefore, the total number of failed sequences is found by summing that over all possible values of $k$: $$ \boxed{\text{# failed sequences} = \sum_{k=0}^{n-1}\sum_{i=0}^k(-1)^i\binom{k}i\frac{(n-1-i)!}{(n-1-k)!}}\tag1 $$ As you noted, a shifted version of this sequence appears in OEIS, with a different definition. The OEIS entry gives the simpler formula $$ \sum_{k=0}^{\lfloor(n-1)/2\rfloor}\tag2 {(n-1-k)!\over k!} $$ $(1)$ and $(2)$ appear to be equal for all $n$ (confirmed up to $n=150$), but I do not know how to prove this. I cannot see how $(2)$ directly relates to your failed secret Santa problem.