Santa secreto Perfecta problema de Bucle de

Question

1. (n) la gente pone su nombre en un sombrero.
2. Cada persona elige un nombre fuera de el sombrero para comprar un regalo para.
3. Si una persona elige a sí mismos que poner el nombre en el sombrero.
4. Si la última persona que puede elegir sólo de sí mismos, entonces el bucle no es válido y bien
   . empezar de nuevo
   . ni un paso atrás hasta que un válido bucle puede ser alcanzado.

¿Cuál es la probabilidad de que si n es de 33 que la cadena se crea un bucle perfecto?

Un ejemplo de un bucle perfecto donde n es 4:

• Un da a la B
• B le da a a C
• C da a D.
• D da a la A.

Un ejemplo válido, pero no es perfecto bucle donde n es 4:

• Un da a la B
• B le da a Un
• C da a D.
• D da a C.

Answer 1

Usted está solicitando la posibilidad de un solo ciclo, dado que disponemos de un trastorno. Para $n$ de la gente, el número de alteraciones es el entero más cercano a $\frac {n!}e$ A tener un ciclo, la persona $1$ $n-1$ opciones, entonces esa persona ha $n-2$ opciones, entonces esa persona ha $n-3$, etc. Así que hay $(n-1)!$ ciclos. Las probabilidades son entonces () $\frac e{n}$

Answer 2

Deje $P_N$ la probabilidad de obtener un perfecto bucle con $N$ participantes.

$ A \rightarrow C \rightarrow B \rightarrow D \rightarrow A $
$ A \rightarrow B \rightarrow D \rightarrow C \rightarrow A $
$ C \rightarrow A \rightarrow B \rightarrow D \rightarrow C $
son perferct bucles.
Podemos ver que el segundo y el tercero describe el mismo bucle, por lo que podemos contar el número total de perfectos bucles contando todas las permutaciones posibles de C, B y D. De la misma manera, nos encontramos con que el número de perfecto lazos con el N de participantes es $(N-1)!$

Por lo tanto, $P_N = \frac{(N-1)!}{n(\Omega)} $

El espacio muestral son todos los posibles bucles como todo el mundo ha sido le asigna un nombre diferente de la propia, que es en otras palabras, el número total de posibles derangments.

El número de derangments de n elementos, $d(N)$, está dada por

$d(N) = N! \sum_o^N\frac{(-1)^i}{i!}$

Y así,

$P_N = \frac{(N-1)!}{d(N)} = \frac{1}{N \sum_o^N\frac{(-1)^i}{i!}} $

Para $N = 33$,

$P_N = \frac{8222838654177922817725562880000000}{3194414033122656019847107490716704992}$

Answer 3

Con el fin de contar el número de perfectos bucles con $n$ de la gente, tenemos que contar el número de los distintos etiquetados de un ciclo en $n$ vértices, decir $c(n)$. Aunque no tengo una prueba todavía, creo que el número está dado por $$ c(n)=\frac{1}{2n-3}\binom{3n-6}{n-2}. $$ Por otro lado, para contar el número de bucles queremos saber el número de formas de partición de la $n$ que no incluye el 1, decir $p'(n)$. Que está dada por la generación de la función $$ \sum_{n=1}^\infty p'(n)x^n=\prod_{n=2}^\infty\frac{1}{1-x^n}. $$ A continuación, para cada partición que sería necesario para contar el número de perfectos bucles admitió usar nuestra ecuación anterior.

Por ejemplo, el número de bucles que implica 5 personas serían $$\binom{5}{3}c(3)\binom{2}{2}c(2).$$ Y por lo que la probabilidad de selección de un perfecto lazo de 5 personas desde el número de bucles en la 5 de la gente sería $$ \frac{c(5)}{c(5)+\binom{5}{3}c(3)\binom{2}{2}c(2)}. $$

La buena suerte se extiende de este a $n=33$.