¿Cuántas formas hay de poner $mn$ bolas de $n$ diferentes colores en $n$ ¿diferentes cajas?

Question

Esta es una generalización del ejercicio número $60$ en el capítulo $2$ de Hugh Gordon Probabilidad discreta .

Tenemos $m$ bolas de cada uno de $n$ diferentes colores. También tenemos $n$ cajas, cada una con una forma diferente. ¿De cuántas maneras se pueden distribuir las bolas entre las cajas para que cada caja contenga $m$ ¿Bolas?

Por lo que leo, hay un total de $mn$ bolas. Si ordenamos las cajas (lo que podemos hacer sin cambiar los resultados porque tienen formas diferentes) entonces podemos encontrar el número de posibilidades para la primera $m$ bolas (es decir, la primera caja). Como podemos tener cualquier color de bola en cualquier cantidad en la primera caja, podemos utilizar estrellas y barras para encontrar el número de posibilidades. Imaginamos las posibilidades de color como los espacios entre "barras", por lo que tenemos $n-1$ barras, y las bolas (sin colorear) como "estrellas", por lo que tenemos $m$ estrellas. Esto da el número de posibilidades sólo para la primera caja como $$\binom{m+n-1}{n-1}$$

Sin embargo, el número de la segunda caja varía mucho dependiendo de la configuración de la primera caja, así que no creo que este método siga funcionando. Tiene que haber una forma mejor y elegante de resolver esto.

Answer 1

Al parecer, esto no es tan fácil. Reformulemos la pregunta. Usted tiene $n$ cajas, numeradas de $1$ a $n$ y tienes $n$ colores, también numerados de $1$ a $n$ (decir). Digamos que tiene un $n\times n$ matriz cuadrada cuya $(i,j)$ -la quinta entrada es el número de bolas de color $i$ contenida en la caja $j$ . La pregunta es entonces:

Cuántos $n\times n$ hay matrices enteras con entradas no negativas tales que la suma de los números de cada fila y de cada columna es $m$ ?

Esto ya se preguntó aquí . La respuesta que se da allí apunta a varios trabajos de investigación; uno de ellos, El polinomio de Ehrhart del politopo de Birkhoff de Matthias Beck y Dennis Pixton, dice en su introducción que el número que buscamos (llamado $H_n(m)$ en ella) es un polinomio en $m$ de grado $(n-1)^2$ y proporciona una forma (computacionalmente pesada) de calcularla. Los resultados de $n\leq 9$ se puede encontrar en Página web de Dennis Pixton .