# What's the General Expression For Probability of a Failed Gift Exchange Draw

My family does a gift exchange every year at Christmas. There are five couples and we draw names from a hat. If a person draws their own name, or the name of their spouse, all the names go back in a hat and we re-draw names. This happens maybe 7 times out of 8.

Using a computer, I know that the probability of this happening is

1 - (440192 / 10!)


(It's been too long since I took combinatorics) What's a general expression for n couples?

Edit Oct 19, 2011: I was so impressed with the answer, I wrote a blog post about it: http://michaeljswart.com/2011/10/secret-santa-as-a-puzzle/

-
This is related to derangements. –  Charles Oct 17 '11 at 14:05
That comment is more helpful than you know. It gives me something to research (Google). Thanks. –  Michael J Swart Oct 17 '11 at 14:08
Michael: How do you know this is more helpful than @Charles knows since you do not know how much he knows? More to the point, you could have a peek at this. –  Did Oct 17 '11 at 14:30
@Didier, It's an English expression. I'm telling Charles that he helped a lot. And thanks for your link Didier. –  Michael J Swart Oct 17 '11 at 14:41
Michael: I know. I pretended to understand literally what you wrote, simply to use know four times in the same sentence. Small pleasures... –  Did Oct 17 '11 at 14:50

By assigning a letter to each couple, this can be reduced to the problem of finding the number $a_n$ of anagrams of a word with $n$ different letters, each occurring twice, with no letters fixed. The desired number of permutations is then $2^na_n$, since each of the $n$ couples can be assigned in two ways to the two instances of its letter. Wikipedia mentions this problem as a generalized derangement problem. The general formula given for a word with numbers $n_1,\dotsc,n_r$ of $r$ different letters is

$$\int_0^\infty L_{n_1}(x)\cdots L_{n_r}(x)\mathrm e^{-x}\mathrm dx\;,$$

where $L_k(x)$ is the $k$-th Laguerre polynomial. In the present case, $r=n$ and $n_i=2$, so we only need the second Laguerre polynomial, which is $L_2(x)=\frac12(x^2-4x+2)$. The $n$ factors of $\frac 12$ cancel with the $n$ factors of $2$, so the probability of success is

$$\frac1{(2n)!}\int_0^\infty\left(x^2-4x+2\right)^n\mathrm e^{-x}\mathrm dx\;,$$

where $(2n)!$ counts the total number of permutations. For $n=5$, Wolfram|Alpha gives $440192/(10!)$, as you calculated.

We can also recover Ross' estimate $\mathrm e^{-2}$ from this result in the limit $n\to\infty$:

$$\begin{eqnarray} \frac1{(2n)!}\int_0^\infty\left(x^2-4x+2\right)^n\mathrm e^{-x}\mathrm dx &=& \frac1{(2n)!}\int_0^\infty\left((x-2)^2-2\right)^n\mathrm e^{-x}\mathrm dx \\ &\approx& \frac1{(2n)!}\int_2^\infty\left((x-2)^2-2\right)^n\mathrm e^{-x}\mathrm dx \\ &=& \frac{\mathrm e^{-2}}{(2n)!}\int_0^\infty\left(x^2-2\right)^n\mathrm e^{-x}\mathrm dx \\ &=& \frac{\mathrm e^{-2}}{(2n)!}\int_0^\infty\sum_{k=0}^n\binom nk(-2)^kx^{2(n-k)}\mathrm e^{-x}\mathrm dx \\ &=& \frac{\mathrm e^{-2}}{(2n)!}\sum_{k=0}^n\binom nk(-2)^k\int_0^\infty x^{2(n-k)}\mathrm e^{-x}\mathrm dx \\ &=& \frac{\mathrm e^{-2}}{(2n)!}\sum_{k=0}^n\binom nk(-2)^k(2(n-k))! \\ &=& \frac{\mathrm e^{-2}}{(2n)!}(2n)!\left(1-\frac1{2n-1}+\dotso\right) \\ &\approx& \mathrm e^{-2}\;. \end{eqnarray}$$

-
This is brilliant, thanks so much. Can I quote your answer in a blog post? I'll be sure to provide links back. –  Michael J Swart Oct 17 '11 at 16:13
@Michael: You're welcome. Sure, go ahead :-) –  joriki Oct 17 '11 at 16:15
@Michael, if it isn't too much trouble, could you edit your question to link to your blog post on this? :) –  Guess who it is. Oct 19 '11 at 13:07
Yep, the blog post goes live at noon today. When that happens, I'll do it :-) –  Michael J Swart Oct 19 '11 at 13:22
@J.M.: Thanks for fixing the notation for the Laguerre polynomials -- I'd thought of writing it that way but then decided to keep the notation in line with the Wikipedia article I linked to. –  joriki Oct 19 '11 at 14:09

If we pretend the events are independent, each person fails with probability $1/n$. The chance that nobody fails is then $\left(\frac{n-1}{n}\right)^{2n}\to \left(\frac{1}{e}\right)^2\approx 0.135$. For your five couples, Alpha gives $89.3\%$ in this approximation, not far off your exact computation.

-
Nice answer Ross, I'm also impressed by your math typography skills. Looks very professional. I'm not sure what the expression with e means (is that as n approaches infinity?) But you're right. The function is pretty close. –  Michael J Swart Oct 17 '11 at 14:46
@MichaelJSwart: yes, as $n \to \infty$ it converges there. It looks like it takes a while. For typesetting, you put $\LaTeX$ between dollar signs. You can right click and Show Source to see how anything was done. –  Ross Millikan Oct 17 '11 at 15:38
I think you mean $\left({n-1 \over n}\right)^{2n} \to (1/e)^2$, which seems to agree better with numerical results. –  Michael Lugo Oct 17 '11 at 16:01
@MichaelLugo: Right. Fixed. –  Ross Millikan Oct 17 '11 at 16:15
I added a derivation of the limit $\mathrm e^{-2}$ to my answer. –  joriki Dec 12 '11 at 10:44