¿Cuál es la Expresión General Para la Probabilidad de Error de Intercambio de Regalos Sorteo

Question

Mi familia hace un intercambio de regalos cada año en Navidad. Hay cinco parejas y sacamos los nombres de un sombrero. Si una persona saca su propio nombre, o el nombre de su cónyuge, todos los nombres de volver en un sombrero y nos re-dibujar nombres. Esto ocurre tal vez 7 veces 8.

El uso de un ordenador, sé que la probabilidad de que esto ocurra es

1 - (440192 / 10!)

o alrededor de un 88%.

(Ha pasado mucho tiempo desde que yo asumí la combinatoria) ¿Qué es una expresión general para n parejas?

Edición 19 de Octubre de 2011: yo estaba tan impresionado con la respuesta, escribí un post en el blog sobre esto: http://michaeljswart.com/2011/10/secret-santa-as-a-puzzle/

Answer 1

Mediante la asignación de una letra a cada pareja, esto puede ser reducido al problema de encontrar el número de $a_n$ de los anagramas de una palabra con $n$ letras diferentes, cada uno de los que ocurren dos veces, sin letras fijo. El número de permutaciones, a continuación,$2^na_n$, ya que cada una de las $n$ de las parejas puede ser asignado en dos formas a las dos instancias de su carta. Wikipedia menciona este problema como un trastorno generalizado del problema. La fórmula general dado por una palabra con números de $n_1,\dotsc,n_r$ $r$ cartas diferentes es

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

donde $L_k(x)$ $k$- ésimo polinomio de Laguerre. En el presente caso, $r=n$$n_i=2$, así que sólo necesitamos el segundo polinomio de Laguerre, que es $L_2(x)=\frac12(x^2-4x+2)$. El $n$ factores de $\frac 12$ cancelar con el $n$ factores de $2$, por lo que la probabilidad de éxito es

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

donde $(2n)!$ cuenta el número total de permutaciones. Para $n=5$, Wolfram|Alpha da $440192/(10!)$, como se calcula.

También podemos recuperar Ross cálculo de $\mathrm e^{-2}$ a partir de este resultado en el límite de $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} $$

Answer 2

Si pretendemos que los eventos son independientes, cada persona produce un error con una probabilidad de $1/n$. La posibilidad de que nadie falla entonces es $\left(\frac{n-1}{n}\right)^{2n}\to \left(\frac{1}{e}\right)^2\approx 0.135$. Para sus cinco parejas, Alfa da $89.3\%$ en esta aproximación, no muy lejos de su cálculo exacto.