Spaghetti aros combinatoria variación

Question

Usted puede haber oído acerca de los clásicos espaguetis aros de combinatoria problema, que ha sido declarado como este:

"Tiene N piezas de cuerda en un cubo. Alcanzar y agarrar un extremo de la pieza, a continuación, llegar y agarrar el otro extremo de la pieza, y atar los dos juntos. ¿Cuál es el valor esperado del número de bucles en el cubo?"

La solución es sencilla y consiste en la definición de dos eventos: evento que cierra el bucle, frente a caso de que usted acaba de ampliar el camino, sin formar un bucle.

---

Mi pregunta es ¿qué sucede cuando podemos generalizar esto un poco, así que los objetos que ya no necesita tener 2 extremos?

Para simplicty digamos que los objetos de todos los que todavía tienen el mismo número de $E$ de las estaciones. Pero algunas cosas interesantes que suceda: si $E$ es impar, los objetos no pueden cerrar sobre sí mismos, por ejemplo, para la $E$=2 caso de un bucle formulario para conectar un solo objeto para sí mismo, pero ahora eso no puede suceder. Cuando $E$=incluso, ahora esto puede suceder de nuevo.

Así, en concreto, vamos a definir un "enredo" como la generalización de un bucle, es decir, un "enredo" es un grupo de objetos conectados, por lo que cada objeto en la maraña está conectado por al menos 1 de borde a otro al menos un objeto en esa maraña. Vamos a llamar el "tamaño" de la maraña el número de objetos que se encuentran en la maraña.

Mi pregunta es: dado $N$ objetos, por número de estaciones por objeto $E\geq3$, ¿cuál es el número esperado de "enredos"? Los puntos de bonificación si se le puede dar el número esperado de los enredos de un tamaño dado, $S$?

Answer 1

Enfoque posible? No una respuesta, pero demasiado largo para un comentario.

El estado del sistema queda completamente descrita por el vector $(a_0, a_1, ...)$ donde $a_j = $ el no. de los enredos con $j$ extremos (suelto). Esta es una Cadena de Markov. El inicio ha $a_E = N$ (y todos los otros $a_j = 0$). En cada paso de tiempo, tienes que elegir dos extremos y conectar con ellos. E. g., si tienes que elegir una estación perteneciente a enredar con 4 estaciones, y el otro extremo de la pertenencia a enredar B con 6 puntos finales, y conectarlos, que crea un nuevo enredo con $4+6-2 = 8$ extremos, por lo que los cambios de estado son: $a_4(t+1) = a_4(t) - 1$, $a_6(t+1) = a_6(t) -1$, e $a_8(t+1) = a_8(t) + 1$. Otro ejemplo: si usted elige dos extremos de un enredo con $j$ estaciones, los cambios de estado son: $a_j(t+1) = a_j(t) - 1$, e $a_{j-2}(t+1) = a_{j-2}(t) + 1$.

Esto parece ser una Cadena de Markov con un gran espacio de estado y de difícil solución. Por suerte:

• Deje $T = \sum_j (j \ a_j) = $ el número total de estaciones. Esta cantidad disminuye por $2$ cada intervalo de tiempo.

• La Cadena termina cuando se $T(t) < 2$, por lo que se ejecuta exactamente $\lfloor T(0) / 2 \rfloor$ intervalos de tiempo, donde $T(0) = NE = $ el número de partida de cabos sueltos.

• Cuando termina, $a_j = 0 \ \forall j \ge 2$, e $a_1 < 2$. (Si $NE$ es impar, entonces $a_1 = 1$ al término del contrato, es decir, hay un cabo suelto de la izquierda; de lo contrario $a_1 = 0$ en la terminación.)

• El resultado deseado es $E[a_0 + a_1]$ al momento de la terminación.

Así que a menos que usted tiene una cantidad finita de tiempo para trabajar, y la Cadena es concebible soluble en muy complicado forma cerrada. Esto es especialmente cierto si podemos establecer recurrencias en $E[a_j(t)]$, pero no estoy seguro de que es posible.

El caso de $E$ tiene más conveniente propiedades, aunque no sé cómo sacar provecho de ellos. En este caso, $a_j = 0$ para todos los impares $j$, por lo que no tiene que preocuparse acerca de $a_1$. Cualquier incremento en $a_0$ debe venir, obviamente, de conectar dos extremos de la misma maraña con sólo dos cabos sueltos. En cualquier momento $t$ con $a_2(t)$ tales enredos, y $T(t) = NE - 2t$ total cabos sueltos, la probabilidad de que el evento es exactamente $a_2(t) / {T(t) \choose 2} = a_2(t) / {NE - 2t \choose 2}$. Y ya que las expectativas son aditivos, $E[a_0]$ en la terminación es igual a $\sum_t E[a_2(t)] / {NE - 2t \choose 2}$. Por desgracia, yo no puedo pensar en ninguna manera fácil de calcular $E[a_2(t)]$ porque $a_2$ evolución se ve afectada por $a_4$, el cual es afectado por $a_6$, etc. Así por ejemplo, no podemos aglutinen todas las $a_j$ donde $j> 2$, y estamos de vuelta a la misma gran espacio de estado.