16
$\begingroup$

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/

  • 1
    This is related to derangements.2011-10-17
  • 0
    That comment is more helpful than you know. It gives me something to research (Google). Thanks.2011-10-17
  • 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](http://math.stackexchange.com/questions/73007/probability-of-matching-events/73038#73038).2011-10-17
  • 3
    @Didier, It's an English expression. I'm telling Charles that he helped a lot. And thanks for your link Didier.2011-10-17
  • 0
    Michael: I know. I pretended to understand literally what you wrote, simply to use *know* four times in the same sentence. Small pleasures...2011-10-17
  • 0
    Didier, Being able to use "know" four times in a sentence. Very nice, I actually smiled at that.2011-10-17
  • 0
    @DidierPiau Go for six uses by adding on ".. or how much he knows he knows." -:)2011-10-17
  • 0
    @Dilip, suggestion accepted, thanks! Maybe adding *nor whether he knows why he knows what he knows* would be too much? Or maybe not (who knows).2011-10-17
  • 0
    Also relevant: Integer sequence "Number of permutations with no hits on 2 main diagonals." http://oeis.org/A0003162011-10-19
  • 0
    Wow, thanks for the extra bounty :-)2011-12-07

2 Answers 2

18

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} $$

  • 0
    This is brilliant, thanks so much. Can I quote your answer in a blog post? I'll be sure to provide links back.2011-10-17
  • 0
    @Michael: You're welcome. Sure, go ahead :-)2011-10-17
  • 0
    @Michael, if it isn't too much trouble, could you edit your question to link to your blog post on this? :)2011-10-19
  • 0
    Yep, the blog post goes live at noon today. When that happens, I'll do it :-)2011-10-19
  • 0
    @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.2011-10-19
  • 0
    See question text for a link to my blog post on this.2011-10-19
  • 0
    @Michael: Thanks! Nice post :-)2011-10-19
  • 0
    Why in the **world** do we have second-order LDE's and indefinite integrals for what appears to be a typical, discrete combinatorics problem!? I can't even imagine how those would arise in the solution O_O2013-10-28
  • 1
    @MichaelJSwart: Since you enjoyed this answer so much, you might like [this one](http://math.stackexchange.com/a/1358019), too :-)2015-07-12
4

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.

  • 0
    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.2011-10-17
  • 0
    @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.2011-10-17
  • 0
    I think you mean $\left({n-1 \over n}\right)^{2n} \to (1/e)^2 $, which seems to agree better with numerical results.2011-10-17
  • 0
    @MichaelLugo: Right. Fixed.2011-10-17
  • 0
    I added a derivation of the limit $\mathrm e^{-2}$ to my answer.2011-12-12