Número de parejas sentadas en la misma mesa

Question

Número de parejas sentadas en la misma mesa

Vicente Tjeng

El problema
$ab$ las parejas están sentadas en $a$ mesas con $2b$ asientos cada uno. Llama a una pareja "buena" pareja si están sentados en la misma mesa.

(1) ¿Cuál es la probabilidad de que, en total, haya exactamente $k$ ¿"buenas" parejas?

Mi enfoque hasta ahora
Relaciones de recurrencia Un enfoque posible es establecer una relación de recurrencia, con $p_{a,b,n}$ que denota la probabilidad de tener exactamente $k$ parejas "buenas". Sin embargo, el problema con esto es la ecuación de recurrencia entre $p_{a+1,b,k}$ y $p_{a,b,k}$ no será simple ya que habrá que considerar las diferentes combinaciones de personas en la mesa adicional.
Principio de inclusión y exclusión Otro enfoque posible es utilizar PIE. denotamos $P_S$ como la probabilidad de que sólo las parejas en $S$ son buenas. Mientras $P_S$ para $|S|=1$ es fácil ( $P={b-1}/{ab}$ ), no estoy seguro de cómo proceder.

Ewan Delanoy

Cuando

a = 2

$a=2$ ,

p_{2, b, k}

$p_{2,b,k}$ es exactamente

(\binom{2 b}{k}) (\frac{1}{4})^{k} (\frac{3}{4})^{2 b - k}

$\binom{2b}{k} \big(\frac{1}{4}\big)^k\big(\frac{3}{4}\big)^{2b-k}$ (ley binomial).

Iván Loh

Esto es incorrecto. Cuando

a = 2

$a=2$ , el número de buenas parejas necesariamente debe ser par. Conseguir

p_{a, b, k}

$p_{a,b,k}$ para pequeños valores de

a, b

$a,b$ es relativamente fácil, el problema es cómo generalizar esto.

Alejandro Gruber

Una reformulación podría ser tomar una permutación aleatoria de

1, \dots, 2 a b

$1,\ldots,2ab$ y calcule la probabilidad de que, si

n

$n$ es par, las posiciones de

n

$n$ y

n + 1

$n+1$ son mod congruentes

2 b

$2b$ .

joriki

@Alexander: Pero esa parte es fácil; lo que dificulta esta pregunta es que pide la probabilidad de que haya exactamente

k

$k$ buenas parejas, no sólo por la probabilidad de que una determinada pareja sea buena.

Alejandro Gruber

@joriki Claro: solo estaba señalando que esto podría verse como un problema de permutación, lo que podría ser útil. No tengo una respuesta para esa parte.

Sean Ballentine

Estaba pensando en este problema en clase hoy y me di cuenta de que no sé la respuesta a un problema mucho más simple que parece ser un primer paso obvio. Podría multiplicar el número de formas de elegir k parejas por el número de formas de colocar k parejas al azar entre las mesas y luego cronometrar el número de formas de sentar al resto de manera que ninguna pareja se siente en la misma mesa. Aunque la última parte parece difícil de resolver, estoy más interesado en la parte media. ¿De cuántas maneras puedes colocar k cosas en las ranuras a cuando las ranuras tienen capacidad b?

Vicente Tjeng

@SeanBallentine No creo que haya una forma general de expresar lo que necesita. Sin embargo, dado

k

$k$ distintos objetos para ser colocados en

n

$n$ ranuras distintas, cada una con una capacidad de

b

$b$ , donde el orden dentro de cada ranura no es importante, lo que necesitamos encontrar es el coeficiente de

x^{k}

$x^k$ en

{(\sum_{i = 0}^{b} \frac{X^{i}}{i!})}^{norte}

$\left(\sum^{b}_{i=0} \frac {x^{i}}{i!}\right)^n$ Esto se puede convertir en una relación de recurrencia, donde, si la cantidad deseada se denota como

C (n, k)

$C(n,k)$ por dado

b

$b$ , la recurrencia es

C (norte, k) = \sum_{i = 0}^{b} \frac{C (norte - 1, k - i)}{i!}

$C(n,k)=\sum^{b}_{i=0} \frac {C(n-1,k-i)}{i!}$

usuario66151

Publicado en mathoverflow.net/questions/127864/…

Vicente Tjeng

solo un comentario: ese "tjeng" no soy yo, ¡y no estoy seguro de quién es! Soy mathoverflow.net/users/23976/vincent-tjeng en mathoverflow

nelson

¿Por qué se eliminó esta pregunta en mathoverflow? Creo que tengo una "respuesta", aunque se trata de un montón de sumas de la forma

\sum_{k_{1} + \dots + k_{a} = k} f (k_{1}, \dots, k_{a})

$\sum_{k_1+\cdots+k_a=k} f(k_1,\ldots,k_a)$ . En mi opinión, es mejor que nada, y quizás un punto de partida para mejorar.

Respuestas (1)

Número de parejas sentadas en la misma mesa

Cuando $a=2$ , $p_{2,b,k}$ es exactamente $\binom{2b}{k} \big(\frac{1}{4}\big)^k\big(\frac{3}{4}\big)^{2b-k}$ (ley binomial).
Esto es incorrecto. Cuando $a=2$ , el número de buenas parejas necesariamente debe ser par. Conseguir $p_{a,b,k}$ para pequeños valores de $a,b$ es relativamente fácil, el problema es cómo generalizar esto.
Una reformulación podría ser tomar una permutación aleatoria de $1,\ldots,2ab$ y calcule la probabilidad de que, si $n$ es par, las posiciones de $n$ y $n+1$ son mod congruentes $2b$ .
@Alexander: Pero esa parte es fácil; lo que dificulta esta pregunta es que pide la probabilidad de que haya exactamente $k$ buenas parejas, no sólo por la probabilidad de que una determinada pareja sea buena.
@joriki Claro: solo estaba señalando que esto podría verse como un problema de permutación, lo que podría ser útil. No tengo una respuesta para esa parte.
Estaba pensando en este problema en clase hoy y me di cuenta de que no sé la respuesta a un problema mucho más simple que parece ser un primer paso obvio. Podría multiplicar el número de formas de elegir k parejas por el número de formas de colocar k parejas al azar entre las mesas y luego cronometrar el número de formas de sentar al resto de manera que ninguna pareja se siente en la misma mesa. Aunque la última parte parece difícil de resolver, estoy más interesado en la parte media. ¿De cuántas maneras puedes colocar k cosas en las ranuras a cuando las ranuras tienen capacidad b?
@SeanBallentine No creo que haya una forma general de expresar lo que necesita. Sin embargo, dado $k$ distintos objetos para ser colocados en $n$ ranuras distintas, cada una con una capacidad de $b$ , donde el orden dentro de cada ranura no es importante, lo que necesitamos encontrar es el coeficiente de $x^k$ en ${(\sum_{i = 0}^{b} \frac{X^{i}}{i!})}^{norte}$ $\left(\sum^{b}_{i=0} \frac {x^{i}}{i!}\right)^n$ Esto se puede convertir en una relación de recurrencia, donde, si la cantidad deseada se denota como $C(n,k)$ por dado $b$ , la recurrencia es $C (norte, k) = \sum_{i = 0}^{b} \frac{C (norte - 1, k - i)}{i!}$ $C(n,k)=\sum^{b}_{i=0} \frac {C(n-1,k-i)}{i!}$
solo un comentario: ese "tjeng" no soy yo, ¡y no estoy seguro de quién es! Soy mathoverflow.net/users/23976/vincent-tjeng en mathoverflow
¿Por qué se eliminó esta pregunta en mathoverflow? Creo que tengo una "respuesta", aunque se trata de un montón de sumas de la forma $\sum_{k_1+\cdots+k_a=k} f(k_1,\ldots,k_a)$ . En mi opinión, es mejor que nada, y quizás un punto de partida para mejorar.

nelson · Answer 1

Recordar: $a$ mesas, $2b$ personas en cada mesa. etiquetar las parejas $1,\ldots,ab$ . Definir el evento $C$ como sigue:

C = {parejas 1, \dots, k son buenos y todos los demas son malos} .

$C = \{\mbox{couples $1,\ldots,k$ are good and all others are bad}\}.$ Por simetría, obsérvese que

PAG (exactamente k buenas parejas) = (\begin{matrix} a b \\ k \end{matrix}) PAG (C) .

$\mathbb{P}(\mbox{exactly $k$ good couples}) = \left(\begin{array}{c} ab \\ k \end{array}\right)\ \mathbb{P}(C).$

calcularemos $\mathbb{P}(C)$ con un argumento de inclusión-exclusión.

Dejar $\pi_n$ Sea la probabilidad de que las parejas $1,\ldots,n$ son buenos (independientemente de si alguna otra pareja es buena). Tenga en cuenta que por simetría de nuevo, $\pi_n$ es la probabilidad de que cualquier conjunto particular de $n$ las parejas son buenas Definir los eventos $A$ y $A_n$ como sigue para $n=k+1,\ldots,ab$ :

\begin{array}{rcl} A & = & {parejas 1, \dots, k son buenas} \\ A_{norte} & = & {parejas 1, \dots, k, y norte son buenas} . \end{array}

$\begin{eqnarray} A &=& \{\mbox{couples $1,\ldots,k$ are good} \} \\ A_n &=& \{\mbox{couples $1,\ldots,k$, and $n$ are good}\}. \end{eqnarray}$ Observar

C = A ∖ ⋃_{i = k + 1}^{a b} A_{i} .

$C = A \setminus \bigcup_{i=k+1}^{ab} A_i.$ Exclusión inclusión:

PAG (C) = PAG (A) - \sum_{t = 1}^{a b - k} \sum_{i_{1}, \dots, i_{t}} (- 1)^{t + 1} PAG (A_{i_{1}} \cap \dots \cap A_{i_{t}}) .

$\mathbb{P}(C) = \mathbb{P}(A) - \sum_{t=1}^{ab-k} \sum_{i_1,\ldots,i_t} (-1)^{t+1} \mathbb{P}(A_{i_1}\cap\cdots\cap A_{i_t}).$ De nuevo por simetría,

P (A_{i_{1}} \cap \dots \cap A_{i_{t}}) = π_{k + t}

$\mathbb{P}(A_{i_1}\cap\cdots\cap A_{i_t})=\pi_{k+t}$ , y aquí están

(\begin{matrix} a b - k \\ t \end{matrix})

$\left(\begin{array}{c}ab - k \\ t\end{array}\right)$ términos de esta forma en la suma anterior. Así, podemos escribir

PAG (C) = \sum_{t = 0}^{a b - k} (- 1)^{t} (\begin{matrix} a b - k \\ t \end{matrix}) π_{k + t} .

$\mathbb{P}(C) = \sum_{t=0}^{ab-k} (-1)^t\ \left(\begin{array}{c}ab - k \\ t\end{array}\right) \ \pi_{k+t}.$ Podemos pasar a la informática.

π_{n}

$\pi_n$ .

Contemos el número de formas en que cada uno de los $2ab$ se pueden asignar mesas a las personas en las que las parejas $1,\ldots,n$ son buenas. Supongamos que entre estos $n$ parejas, $n_1$ están sentados en la mesa 1, $n_2$ en la mesa 2, $\ldots$ , y $n_a$ están sentados a la mesa $a$ . De este modo, $n_1+\cdots +n_a = n$ . Hay $\left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)$ formas de elegir cuál de los $n$ las parejas se sientan en qué mesa. Hay $\left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right)$ maneras de elegir las mesas en las que el resto $2ab-2n$ la gente se sienta Por lo tanto, el número total de formas de asignar personas a las mesas de tal manera que las parejas $1,\ldots,n$ son buenos es

\sum_{{norte}_{1} + \dots + {norte}_{a} = norte} (\begin{matrix} norte \\ {norte}_{1}, \dots, {norte}_{a} \end{matrix}) (\begin{matrix} 2 a b - 2 norte \\ 2 b - 2 {norte}_{1}, \dots, 2 b - 2 {norte}_{a} \end{matrix}) .

$\sum_{n_1+\cdots+n_a=n} \ \left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)\ \left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right).$ El número total de formas de asignar todos

2 a b

$2ab$ la gente es solo

\frac{(2 a b)!}{(2 b)!^{a}}

$\frac{(2ab)!}{(2b)!^a}$ . De este modo,

π_{norte} = \frac{(2 b)!^{a}}{(2 a b)!} \sum_{{norte}_{1} + \dots + {norte}_{a} = norte} (\begin{matrix} norte \\ {norte}_{1}, \dots, {norte}_{a} \end{matrix}) (\begin{matrix} 2 a b - 2 norte \\ 2 b - 2 {norte}_{1}, \dots, 2 b - 2 {norte}_{a} \end{matrix}) .

$\pi_n = \frac{(2b)!^a}{(2ab)!} \sum_{n_1+\cdots+n_a=n} \ \left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)\ \left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right).$ Alternativamente, tenga en cuenta que

π_{n}

$\pi_n$ puede ser escrito

π_{norte} = \frac{(2 b)!^{a} norte! (2 a b - 2 norte)!}{(2 a b)!} C_{norte}

$\pi_n = \frac{(2b)!^a \ n! \ (2ab - 2n)!}{(2ab)!} C_n$ dónde

C_{n}

$C_n$ es el coeficiente de

X^{n}

$X^n$ en el polinomio

{(\sum_{i = 0}^{b} \frac{1}{i! (2 b - 2 i)!} X^{i})}^{a} .

$\left(\sum_{i=0}^b \frac{1}{i! (2b - 2i)!} X^i\right)^a.$

Hola Will: leí tu prueba y creo que funciona. Hará que algunas otras personas lean esto para verificarlo antes de aceptarlo como la respuesta.

Número de parejas sentadas en la misma mesa

Vicente Tjeng

Ewan Delanoy

Iván Loh

Alejandro Gruber

joriki

Alejandro Gruber

Sean Ballentine

Vicente Tjeng

usuario66151

Vicente Tjeng

nelson

Respuestas (1)

nelson

Vicente Tjeng

¿Por qué los límites de esta integral no consideran ambas igualdades?

¿Cuál es la probabilidad de que esté vivo dentro de un mes?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

¿Por qué cambia la probabilidad de un evento en un experimento binomial con el cambio proporcional de éxitos y fracasos?

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

Probabilidad de un resultado con posibilidad de reintentos

Prueba alternativa del teorema de la convergencia dominada aplicando el lema de Fatou a 2g−|fn−f|2g−|fn−f|2g - |f_n - f|?

Una baraja de cartas incluye 40 cartas diferentes. Hay 8 cartas en cada uno de los 5 palos. Se barajan las cartas y un jugador recibe 3 cartas (diferentes).

¿Por qué surge esta relación de recurrencia en la que nnn elige kkk? [duplicar]

Estimación de la desviación estándar de la población con la desviación estándar de la muestra