Uno de bolas y urnas

Question

Esta es una pregunta que se me ocurrió al leer la descripción de un algoritmo para resolver un clásico del rompecabezas. Yo estoy haciendo esto sólo para satisfacer mi propia curiosidad y tal vez aprender algunas cosas útiles a partir de la combinatoria.

Hay muchas maneras para modelar el problema, pero vamos a usar las bolas y urnas:

Digamos que usted tiene 4 distinguibles de las urnas (vamos a llamarlos $A$, $B$, $C$ y $D$) y 15 bolas de 4 tipos distinguibles (vamos a llamarlos $a$, $b$, $c$ y $d$) que tiene 4 bolas de cada una de las $(a, b, c)$ 3 $d$ bolas. Como se puede ver, uno (natural) forma de colocar las bolas en las urnas es poner los cuatro en Una, las cuatro b en B, y así sucesivamente.

Hasta ahora tan bueno. Ahora aquí está la complicación no sé cómo lidiar con: supongamos que los cuatro urnas fijas capacidad para albergar a un máximo de cuatro bolas. Así, se puede observar que no importa cómo se dividen las bolas en las urnas, siempre habrá 3 urnas completamente lleno, y uno con una sola "vacío" del espacio.

La pregunta es, ¿cuántas maneras diferentes hay para dividir las bolas en las urnas? Hay un número en la URL me hace referencia en el primer párrafo, y supongo que me pudo verificar mediante la escritura de un programa para hacerlo por fuerza bruta, pero me gustaría saber si hay una manera de abordar este problema de puramente con el razonamiento matemático.

Además, ¿qué tal si nos generalizar el problema? En lugar de 4 urnas, tenemos $X$ de las urnas, y tenemos $K$ bolas de $X$ tipos (siéntase libre de asumir cualquier cosa que usted desea para el resto de los detalles de un problema más general).

Gracias.

---

Edit 1: En caso de que ayuda, he aquí algunos detalles más. Como se puede deducir de los link, este problema es algo relacionado con el 15-puzzle. Creo que de las urnas de las filas en el rompecabezas. Creo que una de las bolas como las fichas con los números del 1 al 15. Un "tipo" de pelota representa la fila de un cierto azulejo pertenece; por ejemplo, los azulejos de 1 a 4 pertenecen a la fila 1 (así que son bolas de tipo $a$), baldosas de 5 a 8 pertenecen a la fila 2 (que son bolas de tipo $b$), etc.

El número está en la dirección URL en la sección "la SEMANA (a Poca Distancia)", en el párrafo que dice "El número de tablas distintas...".

También, ciertamente se podría representar con 5 tipos de pelotas, y entonces usted tiene 16 bolas (4 de tipo $a$, 4 $b$, 4 $c$, 3 $d$ y el 1 $e$). La pregunta sigue siendo, ¿cuántas maneras existen para poner todas las bolas dentro de las cuatro urnas, teniendo en cuenta sus capacidades?

Answer 1

He trabajado en algo relacionado con esto. No es lo suficientemente fuerte como para solucionar este problema, pero podría llevarte por el camino correcto.

Esta misma urna de bola modelo resuelve el siguiente problema: Considerar el número de $277830000$,$2^4*3^4*5^4*7^3$. De cuántas maneras existen para escribir este número como el producto de cuatro factores que cada factor por sí mismo no tiene más de cuatro factores primos? Encontré$^*$ resultado para este problema sin la restricción de tamaño.

El número de maneras de escribir $\prod_{j=1}^N p_j^{n_j}$ ($p_j$ prime) como el producto de la $k$ factores es $$\sum_{i=0}^{k-1}\left[ (-1)^i {k \choose i} \prod_{j=1}^N T(n_j\!+\!1,~k\!-\!2\!-\!i)\right]~,$$ donde $T(a,b)$ es el multichoose coeficiente ($a$ multichoose $b$).

Yo no puede proporcionar la prueba de esto ahora mismo, pero está escrito en uno de mis libros en la escuela, así que puedo publicar aquí dentro de 10 días. En cualquier caso, tengo algunas de las grandes ideas:

Interpretamos $i$ a ser el número de factores que son uno, y así el ${k\choose i}$ cuenta las formas de elegir qué factores son uno. El multichoose coeficiente cuenta las maneras de poner las copias de los números primos en los diversos factores finales. Por eso nos tomamos el producto de más de $j$, que es el índice de la cantidad de números primos que tenemos en el número original (lo que significa que el número de filas en el 15-puzzle de interpretación). El -1 obviamente proviene de inclusión-exclusión, pero tengo que admitir que he olvidado por qué es necesario.

Como he dicho, no responde a su pregunta. En particular, que tiene un factor de uno se traduce en una fila vacía, que obviamente no es posible. Aunque yo tendría que ver los detalles de la prueba para estar seguro, creo que eso significa que podemos obligado el número de arriba (mal) por $i=0$ caso: $$\prod_{j=i}^N T(n_j+1,~k-2)$$ En el 15-puzzle de la aplicación, esto funciona a $T(5,2)^3T(4,2)=33750$, que es mayor que la conocida respuesta $24964$. En este caso, también es limitada, incluyendo la $i=1$ de los casos, pero esto parece más probable que sea una coincidencia.

($^*$ Me hizo descubrir de manera independiente, aunque puede ser un conocido resultado)

Answer 2

Como se ha sugerido, añadir un extra de bola tipo a $*$, y la cantidad de bolas de tipo $*$ ya que son necesarios para cubrir todas las urnas a su máxima capacidad. Entonces, codificar una colocación de bolas en urnas como la matriz de $(m_{ij})$ cuyas $(i,j)$th entrada es el número de bolas de tipo $i$ en urna $j$. El problema se convierte entonces en el problema de contar rectangular matrices de números enteros no negativos tales que cada fila tiene una suma determinada (el número de bolas de un tipo determinado) y de tal manera que cada columna tiene una suma determinada (el máximo urna de capacidad).

Muchas personas han mirado este problema y otros problemas similares. Véase, por ejemplo, aquí, aquí, aquí, aquí, y aquí.

Suponiendo que la matriz es $m$$n$, la fila sumas son $r_1$, $\dots$, $r_m$, y la columna de sumas son $c_1$, $\dots$, $c_n$, el conde es el coeficiente de $$ T({\bf x}, {\bf y}):=x_1^{r_1}\dots x_m^{r_m} y_1^{c_1} \dots y_n^{c_n} $$ en la generación de la función $$ G({\bf x}, {\bf y}):=\prod_{i,j} \frac{1}{1-x_i y_j}. $$ Esto es obvio, pero de inmediato puede dar una cota superior: el conde no es más que $$ \inf_{0<x_i<1, 0<y_j<1} \frac{G({\bf x}, {\bf y})}{T({\bf x}, {\bf y})}. $$ Ver la cuarta papel por encima de algunos cálculos.

Answer 3

Podría no añadir una bola del tipo "x" a la colección de distribución anticipada, proceder con la solución al problema más complicado, a continuación, tirar la bola de "x"?