Como prometí en mi respuesta a Byron, aquí está mi muy parcial de progreso para
fecha en este problema. Aunque de largo aliento, que no suma mucho.
Todavía estoy en busca de una respuesta para el caso general, o a otros especiales
de los casos (como $n=2$ o $c=2$) o incluso mejores estimaciones. Yo también soy
interesados en saber acerca de cualquier aplicable combinatoria herramientas, incluso sin
una respuesta completa.
En primer lugar, una advertencia: Los gráficos que voy a utilizar no están relacionados con la
los gráficos en general en la formulación de la pregunta original. Ignorar
los gráficos y el solo pensar de los estudiantes y los salones de clase!
Deje $G$ un gráfico con un vértice para cada estudiante, $cn$ vértices en todos.
Decir que un determinado año de asignación de los estudiantes a las aulas
respeta $G$ si cada borde en $G$ se une a dos estudiantes que se
asignadas a los diferentes salones de clase. Es decir, $G$ codifica las restricciones en
asignaciones; cada borde en $G$ representa a dos estudiantes que deben mantenerse
aparte. Deje $R(G)$ la probabilidad de que una asignación aleatoria de los
los estudiantes a las aulas respeta $G$. Tenga en cuenta que$R(G)$, que no depende
en $y$ ya que la definición de "respeta" se refiere a un solo año
de asignación.
Ahora vamos a $e(G)$ el número de aristas en $G$. Entonces la probabilidad de que
después de $y$ años cada par de alumnos tiene en algún momento compartieron un
el aula es exactamente
$$\sum (-1)^{e(G)} (R(G))^y$$
donde la suma se toma sobre todos los gráficos de $G$.
Este resultado se sigue de una aplicación directa de
Inclusión/Exclusión. Es muy bonita (al menos yo así lo creo) pero inútil
si desea una respuesta real. El problema no es encontrar a $R(G)$; esto es tedioso
pero puede ser automatizado. La verdadera dificultad es que usted tiene que manejar
$2^{cn\choose 2}$ gráficos, lo cual es mucho, demasiado. Los gráficos que vienen en
isomorfo racimos (por ejemplo, hay un $cn\choose 2$ uno filo gráficos que todos los
tienen la probabilidad de ser respetado) y usted no tiene que manejar la mayoría de los gráficos con muchas aristas desde $R(G) = 0$ para cualquier gráfico de $G$ que no es $c$-partita. Pero esto no ayuda lo suficiente.
Tenemos un poco de uso fuera de este miserable fórmula por la generalización de la
problema. Supongamos que pedimos, dadas las mismas condiciones, por la probabilidad de
que cada alumno de un grupo dado de $p$ a los estudiantes en algún momento ve
cada uno de los otros estudiantes en el grupo. La fórmula anterior nos da el
respuesta exacta si se le suma sobre todos los gráficos con $p$ vértices, cada uno de los etiquetados
con un estudiante en el grupo. Por ejemplo, con $p = 2$ la fórmula
da la probabilidad de que dos estudiantes en algún momento de ver a cada
otros:
$$1 - \left(\frac{n(c-1)}{cn-1}\right)^y$$
(Por supuesto que podemos obtener este resultado mediante una simplificación de la ruta). Para $p=3$ el
la fórmula da
$$1 - \left(\frac{N-n+1}{N(N-1)}\right)^y(3(N-1)^y - 3(N-n)^y + (N-2n+1)^y)$$
donde $N = cn-1$. He luchado a través de la fórmula de la $p$ hasta 6, pero
se hace imposible rápidamente.
Ahora algunas aproximaciones. Definir $U_m$ a la probabilidad de que un
estudiante $S$ es que en algún momento en un salón de clases con cada estudiante en un
conjunto dado de $m$ los estudiantes que no contengan $S$. Otro sencillo
solicitud de inclusión/exclusión se da
$$U_m = \sum_{j=0}^m(-1)^j{m\choose j}{N-j\choose n-1}^y \bigg/ {N\choose n-1}^y$$
donde $N = cn-1$ como antes. $U_N$ es la probabilidad de que una sola
dado estudiante verá todos los demás. Este es un muy débil límite superior
en la probabilidad de que todos los alumnos ven a todos los demás, aunque en
casos triviales un estudiante viendo todos los demás implica que todos ellos
hacer! $U_m$ es bastante fácil de calcular; con los parámetros originales,
por ejemplo, $U_{74}$ resulta ser un poco menos de 1/7792. Nota, por CIERTO,
que $U_1$ correctamente da el mismo resultado que el $p=2$ respuesta anterior.
Si "estudiante $A$ considera que todos los otros" eran independientes de "estudiante $B$
ve a todos los demás", entonces tendríamos la respuesta que buscamos: $(U_N)^{cn}$.
Pero, por supuesto, estos eventos son poco probables a ser independiente. Si muchos
que los estudiantes hayan visto todos los demás, entonces seguramente la probabilidad aumenta
que todos han visto los demás. Por lo $(U_N)^{cn}$ puede ser un límite inferior en
la verdadera respuesta, si uno débil. Edit: en Realidad, creo que no puede ser un límite inferior, ya que estoy bastante seguro de que podemos encontrar un caso en el que un estudiante puede ver a todos los demás, pero es imposible que todos los estudiantes a hacerlo.
He aquí otra forma de estimar la respuesta: Un grupo de $p$ estudiantes
todos ven unos a otros si y sólo si (a) un particular uno de estos
los estudiantes ve que todos los otros $p-1$ a los estudiantes, y (b) el otro $p-1$
los estudiantes de todos vean el uno al otro. La probabilidad de que (a) es exactamente
$U_{p-1}$. Deje $C_{p-1}$ denotar la probabilidad de (b). Si los acontecimientos (a)
y (b) son independientes, entonces la respuesta exacta a la pregunta original
sería $U_{p-1}C_{p-1}$. Pero por idéntico razonamiento, $C_{p-1} =
U_{p-2}C_{p-2}$. Continuando de esta manera, la respuesta exacta a la original
la pregunta sería
$$U_NU_{N-1}U_{N-2}\ldots U_2U_1$$
Como en el anterior, los eventos en cuestión no son susceptibles de ser independiente. Pero
la mayoría del tiempo están cerca, a la derecha? Con los parámetros originales,
el hecho de que un grupo de cinco estudiantes de todos los ver cada uno de los otros tiene muy
poco impacto en el nivel de sexto estudiante ve a cada uno de los cinco, aunque
se debe aumentar la probabilidad de que un poco. Esto haría que el
la expresión por encima de un límite inferior en el real de la respuesta, aunque no sé
qué bueno es.
