Número de formas de distribución $n$ objetos idénticos entre $r$ grupos

Question

Encontré esta fórmula en una lista: El número de formas de distribuir $n$ objetos idénticos entre $r$ grupos tales que cada grupo puede tener $0$ o más $(\le n)$ objetos

Sé que la forma estándar de hacerlo es resolver el problema de distribuir n objetos idénticos y $(r-1)$ particiones entre sí, lo que puede hacerse en $C(n+r-1,r-1)$ maneras.

Pero soy incapaz de demostrarme a mí mismo por qué no es $(r+1)^n$ . Porque cada uno de los n objetos tiene r+1 opciones, o grupo1, grupo2,... grupo r o ninguna.

Answer 1

El puesto cita la expresión estándar para el número de formas de distribuir $n$ objetos idénticos entre $r$ grupos. La formulación utilizada parece indicar que conoce el argumento de recuento que conduce a esta expresión. En caso de que me equivoque al respecto, consulte la Wikipedia Estrellas y barras artículo.

¿Qué significa "probarme a mí mismo por qué no es $(r+1)^n$ ?" Escribiré sobre esta pregunta durante un tiempo, y hacia el final describiré razonamientos que puede conectarse con su $(r+1)^n$ .

Veamos primero una cuestión más sencilla, demostrando que no es $(r+1)^n$ . Si puedes encontrar aunque sea un solo par $(r, n)$ de enteros para los que la expresión $(r+1)^n$ da una respuesta errónea, sabrá que $(r+1)^n$ no es (siempre) correcto.

Para ello, basta con seguir la excelente sugerencia de Gerry Myerson. Mira un ejemplo pequeño, como $r=2$ , $n=2$ . ¿De cuántas maneras se puede distribuir $2$ gominolas idénticas entre dos personas, $A$ y $B$ ? Tal vez $A$ se queda con los dos. Tal vez $B$ hace. Tal vez $A$ recibe una y $B$ consigue uno. Eso es todo, el número total de formas es $3$ .

Si la expresión $(r+1)^n$ era correcto para $r=2$ , $n=2$ el número de vías sería $3^2$ que claramente no es igual a la respuesta correcta $3$ de la que estemos absolutamente seguros. (Estamos completamente seguros porque el recuento es tan sencillo, tan directo, que es imposible que nos hayamos equivocado). Por cierto, si lo compruebas, verás que la expresión $C(n+r-1,r-1)$ da la respuesta correcta, ya que $C(3,1)=3$ .

Cuando intentas resolver un problema combinatorio, es importante experimentar, intentar buscar casos pequeños en los que puedas hacer la cuenta "a mano". A menos que el problema sea muy estándar, ésa es la forma correcta de empezar. Y cualquier recuento concreto que hagas puede servirte después como comprobación.

Así que sabemos que $(r+1)^n$ al menos a veces, da la respuesta equivocada. (En realidad, suele dar una respuesta que es mucho mayor que la verdad).

A continuación trataremos por qué $(r+1)^n$ da una respuesta errónea. ¿Hay alguna buena razón para pensar que debería dar la respuesta correcta? Piensa que podría haberla. Busquemos un problema para el que $(r+1)^n$ es la respuesta correcta.

Tengo $n$ distinto regalos para repartir, para $r$ personas, salvo que yo decida no repartir algunos de los regalos y quedármelos para mí. Para cualquier regalo, tengo $r+1$ opciones de qué hacer con él. Luego están $(r+1)^n$ formas de hacer regalos. Es crucial que los regalos sean distintos.

No veo ninguna relación directa entre esta entrega de regalos y el problema de distribuir $n$ idéntico objetos entre $r$ personas.

Si los dones son distintos, y no puedo quedarme con ninguno de ellos, hay $r^n$ formas de hacer la distribución. Uno podría pensar que entonces se podría ajustar esto por el hecho de que los regalos son todos idénticos. Ese tipo de ajuste se puede hacer cuando se cuenta el número de $6$ -palabras" que puedes formar con todas las letras de "CANADA". Primero imagina que las A son distintas, obteniendo $6!$ y dividir por $3!$ para hacer frente al hecho de que las A no son distintas. Pero esta estrategia no funcionará para nuestro problema de distribución de objetos idénticos. Supondría un gran exceso de recuento.

Cualquier estrategia para contar pensando en repartir los objetos de uno en uno se topa rápidamente con problemas. Suele exagerar mucho el número de formas. Por ejemplo, ¿de cuántas maneras podemos distribuir $n$ gominolas entre $2$ personas, $A$ y $B$ ? Persona $A$ puede conseguir $0$ o $1$ o $2$ y así sucesivamente hasta $n$ un total de $n+1$ posibilidades. Ahí es donde probablemente su intuición sobre la $+{}1$ aunque lo hayas aplicado a $r$ no a $n$ .

¿Qué pasa con $n$ gominolas y $3$ ¿Gente? Se podría pensar que hay $n+1$ maneras de decidir cuántos $A$ recibe, y luego $n+1$ maneras de decidir cuántos $B$ obtiene, con $C$ conseguir el resto. Ese argumento daría un recuento de $(n+1)^2$ . Pero ese recuento sería incorrecto . Si tiene $3$ personas, y $8$ gominolas, y han dado $6$ a $A$ entonces no puedes dar $5$ a $B$ . Así que aunque hay $n+1$ opciones para elegir a cuántos dar $A$ no es cierto que por cada una de estas opciones haya $n+1$ maneras de decidir a cuántos dar $B$ .

Answer 2

Consideremos que hay $r-1$ bloquea por lo que, habrá $r$ espacios a rellenar (incluyendo la izquierda del bloque más a la izquierda y la derecha del bloque más a la derecha). Ahora, $n$ cosas idénticas deben rellenarse en estos espacios. Hay $n+r-1$ cosas en esa línea ahora, que se pueden organizar en $(n+r-1)!$ maneras.

Pero, debemos evitar los acuerdos entre los $n$ cosas y $r-1$ ya que son idénticos.

Así pues, la respuesta final es $$\frac{(n+r-1)!}{n! (r-1)!} = C(n+r−1,r−1).$$

Answer 3

$C(n+r-1, r-1)$ es la respuesta para la distribución de $n$ objetos idénticos entre $r$ personas. No para los grupos, porque los grupos son considerados como idénticos no tienen nombre. Ejemplo: dos bolas idénticas pueden ser distribuidas entre dos personas de tres maneras: $\left\{ (2,0), (0,2), (1,1)\right\}$ . Pero cuando vamos por grupos, $(2,0)$ y $(0,2)$ se consideran iguales, por lo que ahora la respuesta será sólo dos.

Answer 4

Que haya lugares para colocar el objeto numerados como 1,2,3,4,......,n. Sean distintos r objetos: A,B,C,D,....... Ahora supongamos que los objetos a distribuir son distintos. ahora que tengo r+1 opciones para poner cada objeto en un lugar digamos que al distribuir, B y D fueron puestos en el lugar número 2 es decir 2 obtiene dos objetos pero 2 también podría haber obtenido A C o E F o cualquier otro par. Si todos los objetos fueran idénticos, por ejemplo A,A,A,A,A,A,....(r), todos los pares BD AC EF se convertirían en AA AA AA ... por lo tanto, repitiendo los casos en los que 2 obtuvieron el par AA, (r+1)^n le daría un valor mayor.

Answer 5

$(r+1)^n$ es incorrecto porque si lo haces estás dando a cada objeto una identidad diferente y el orden de los grupos es importante para ti pero aquí todos los objetos son idénticos y el orden no es importante.