Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!)

or about 88%.

(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/

share|improve this question
1  
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
1  
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
3  
@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

2 Answers 2

up vote 13 down vote accepted
+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} $$

share|improve this answer
    
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? :) –  J. M. 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.