Contar el número de formas de repartir papeles entre cuatro personas

Question

Esta es una pregunta que tuve en un examen hoy:

Cuatro personas están revisando 230 exámenes. ¿De cuántas maneras se pueden repartir los entre los cuatro si quieres que cada uno revise al menos 15?

Así que, después de comprobar $4 \cdot 15$ papeles nos quedamos con 170 y así el resultado es $$\binom{170+(4-1)}{4-1}=\binom{173}{3}$$ Y aquí está el giro: Siguiendo la última pregunta, de cuántas maneras se pueden dividir los papeles entre los cuatro, sólo que ahora los papeles son diferentes y es importante contar quién comprueba cuántos. Significado - El número de formas de dividir 230 elementos a 4 grupos diferentes.

Mi intento inicial fue $$\sum_{x_1,x_2,x_3,x_4=230}\binom{230}{x_1,x_2,x_3,x_4}=4^{230}$$ Pero eso es obviamente un error ya que no estaba contando los primeros 60 papeles correctamente. Creo que probablemente implica el uso de la inclusión-exclusión, pero no estoy seguro de cómo.

Me encantaría escuchar algunas ideas. Gracias.

Answer 1

No veo una manera fácil de hacer esto analíticamente.

Numéricamente es posible mirando cada una de las 848.046 formas de dividir el número de trabajos y sumando los coeficientes multinomiales. Incluso esto no es trivial, ya que $230!$ puede ser demasiado grande para algunos sistemas, por lo que puede ser sensato utilizar logaritmos en algún momento. Por ejemplo, en R, utilizando

require(partitions)
papers <- compositions(230 - 4*15, 4) + 15
sum(  exp( lfactorial(230) - colSums(lfactorial(papers)) )  )   

da

[1] 2.977131e+138

que está cerca de $4^{230}$ y la diferencia se acerca a la precisión del cálculo.

¿Cómo de cerca? Un enfoque similar, pero teniendo en cuenta que al menos uno de los examinadores obtiene estrictamente menos de 15 trabajos, daría 1.233.110 patrones de números y 5.015953e+125 formas de distribución de los diferentes papeles. Así que en cierto sentido "muy cerca".

Answer 2

Considere todas las formas posibles de dividir $230$ objetos etiquetados entre $4$ etiquetados, y para $i=0$ , $\ldots$ , $3$ y $j=0$ , $\ldots$ , $14$ , dejemos que $A_{ij}$ sea el conjunto de formas en que la persona $i$ recibe exactamente $j$ objetos. Queremos contar el tamaño de $S$ , donde $S$ es el complemento de $\bigcup_{i,j} A_{ij}$ . Observe que $A_{ij}\cap A_{ik}=\emptyset$ si $j\ne k$ . Esto implica que cualquier intersección de cinco o más distintos $A_{ij}$ debe estar vacía; de hecho, cualquier intersección de cuatro $A_{ij}$ también deben estar vacías, ya que aparte de las que tienen repeticiones $i$ cualquier intersección será de la forma $$A_{0j}\cap A_{1j'} \cap A_{2j''} \cap A_{3j'''},$$ que está vacía ya que requiere que cada persona obtenga como máximo $14$ objetos, pero $4\cdot 14<230$ . Por lo tanto, la aplicación del principio de inclusión-exclusión dará $$ \#S=4^{230}-\sum_{i,j} \#A_{ij}+\sum_{i,j,i',j': i<i'} \#(A_{ij}\cap A_{i'j'}) $$ $$ -\sum_{i,j,i',j',i'',j'': i<i'<i''} \#(A_{ij}\cap A_{i'j'}\cap A_{i''j''}). $$ Sin embargo, $\#A_{ij}$ es el número de formas de elegir $j$ objetos etiquetados fuera de $230$ para dar a la persona $i$ y dividir el resto entre $3$ gente, así que $$\# A_{ij}=\binom{230}{j} 3^{230-j}.$$ De la misma manera, $$\# (A_{ij}\cap A_{i'j'})=\binom{230}{j\ \ j'\ \ 230-(j+j')}2^{230-(j+j')}$$ y $$\# (A_{ij}\cap A_{i'j'}\cap A_{i''j''})= \binom{230}{j\ j'\ j''\ 230-(j+j'+j'')} ,$$ así que $$ \#S =4^{230}-4 \sum_{0\le j\le 14} \binom{230}{j} 3^{230-j} +\binom{4}{2} \sum_{0\le j, j'\le 14} \binom{230}{j\ j'\ 230-(j+j')} 2^{230-(j+j')} $$ $$ -\binom{4}{3} \sum_{0\le j, j', j''\le 14} \binom{230}{j\ j'\ j''\ 230-(j+j'+j'')}, $$ que puede calcularse como

2977131414714304228375163768128492513800825122727620839102462174397915143246224081981112746784016599181459879137390109633489003108916312960.

Como dice Henry, esto está muy cerca de $4^{230}$ : $$1-\frac{\#S}{4^{230}}\approx 1.6848\cdot 10^{-13}.$$