Si tenemos $m$ indistinguible objetos de cuántas maneras es posible ponerlos en $n$ indistinguihable posiciones?

Question

si tenemos $m$ indistinguibles de los objetos, de cuántas maneras es posible ponerlos en $n$ indistinguibles de las posiciones? (para los 2 casos 1: sin posición vacía permitido 2: posiciones vacías están permitidos.)

Ya sabemos que si los objetos eran distintos y las posiciones son idénticos en ambos casos, el número se llama número de Stirling $S(m,n)$ (sin posiciones vacías permitido).

Answer 1

La elaboración de @Andre respuesta, vamos a $p_k(n)$ denotar el número de maneras de escribir el número natural $n$ como la suma de exactamente $k$ números naturales, en nonincreasing orden. Por ejemplo, $p_2(3)=1$ porque $3=2+1$ es el único de dicha suma. $p_2(4)=2$ porque $4=3+1$ $4=2+2$ son los dos de tales sumas. También tenemos $p_3(3)=1$ desde $3=1+1+1$ es el único de dicha suma, y $p_3(4)=1$ desde $4=2+1+1$ es el único de dicha suma. Tenemos $p_4(3)=0$, dado que no se suma con cuatro partes. Podemos llamar a estas funciones particiones de $n$ a $k$ partes. También podemos añadir hasta $p_1(n)+p_2(n)+p_3(n)+\cdots$ para obtener todas las particiones de $n$ (en cualquier número de partes). Esto es representado por $p(n)$.

Ahora voy a explicar por qué estas funciones son relevantes para su problema. Supongamos que tengo $m$ idénticas a las canicas, y $n$ idénticos en los cuencos. Pongo las canicas en los tazones. Luego, desde las canicas son idénticos, todo lo que puedo decir acerca de cada plato es cuántas canicas están dentro de él. Así, tal vez yo tenga un recipiente con 4 canicas, un recipiente con 2 canicas, un cuenco con 7 canicas. Sin embargo, los cuencos todos tienen el mismo aspecto, con lo que puede que así organizar los tazones para que cada plato tiene al menos tantas canicas como el siguiente plato. Es decir, voy a poner el tazón con 7 canicas en primer lugar, luego el recipiente con 4 canicas, entonces el recipiente con 2 canicas. Podemos pensar en esto como $13=7+4+2$. Si queremos poner nuestro $13$ canicas en exactamente tres copas, y cada plato que se presenta al menos una de mármol, entonces este es bijective con particiones de $13$ exactamente $3$ partes, es decir,$p_3(13)$. Si por el contrario queremos poner nuestro $13$ canicas en exactamente tres copas, y algunos cuencos puede estar vacía, entonces queremos recuento $13=7+4+2$, pero también se $13=9+4 (+0)$. Por lo tanto, este caso es contada por $p_3(13)+p_2(13)+p_1(13)$. Por último, si tenemos un número ilimitado de tazones a nuestra disposición (aunque nunca la vamos a necesitar más de 13 años), entonces queremos $p_1(13)+p_2(13)+p_3(13)+p_4(13)+\cdots =p(13)$.

Muchas identidades se sabe acerca de estas funciones de partición, aunque en mi opinión no tantas como para los coeficientes binomiales. Usted puede leer acerca de algunos de ellos en la Wikipedia. Algunos ejemplos son:

• La secuencia de $p(n)$ tiene la generación de la función $\prod_{k\ge 1}=\frac{1}{1-x^k}$

• Si $n\equiv 4\pmod{5}$, $p(n)$ es un múltiplo de a $5$ (debido a Ramanujan)

• $p(n)\approx \frac{1}{4n\sqrt{3}}e^{\left(\pi \sqrt{2n/3}\right)}$ $n\rightarrow \infty$ (también debido a Ramanujan, pero con Hardy y de forma independiente por Uspensky)

• El número de particiones en las que la mayor parte tiene un tamaño exactamente $k$ es igual a $p_k(n)$.

Answer 2

Que nos llame a $A_k(n)$ el número de particiones de $n$ objetos idénticos en $k$ cajas idénticas permitiendo que las cajas vacías. Si no permitimos que las cajas vacías, simplemente tenemos $A_k(n-k)$ desde el primero ponemos un objeto en cada cuadro y, a continuación, partición del resto sin ningún tipo de restricciones.

Ahora, además, considerar el número de $A_{k,l}(n)$ que es el número de particiones de $n$ objetos en $k$ cajas que caben no más de $l$ objetos cada uno. Este es el número de Jóvenes de los diagramas de de $n$ cuadrados que caben en un $k\times l$ rectángulo. Por eso, $A_{k,l}(n)=A_{l,k}(n)$.

Para calcular el $A_{k,l}(n)$ considera en primer lugar la elección de cómo muchos objetos para colocar en la caja con la mayoría de los objetos. Digamos que decidimos poner $j$ objetos en la caja. Para contar la cantidad de opciones que nos han dado esa opción simplemente necesitamos $A_{k-1,j}(n-j)$, ya que contamos con $j$ menos objetos para poner en cajas, menos una casilla para colocar objetos, y sabemos que ninguno de estos cuadros tiene más de $j$ objetos. Por lo tanto, tenemos la siguiente relación de recursividad:

$$A_{k,l}(n) = \sum_{j=1}^{l} A_{k-1,j}(n-j)\text.$$

Tenga en cuenta que $A_k(n)=A_{k,n}(n)$ así que tenemos nuestra respuesta.