¿Cómo recordar la diferencia entre "estrellas y barras" y coeficientes multinomiales?

Question

Explicación: Me resulta fácil recordar verbalmente la diferencia entre los coeficientes de permutación y los coeficientes de combinación: se dice que los primeros

"is the number of ways of choosing $k$ things from $n$ options without replacement where order matters"

y que este último

"is the number of ways of choosing $k$ things from $n$ options without replacement where order doesn't matter" .

Pregunta: ¿Cómo se puede describir rápidamente (verbalmente) la diferencia entre los coeficientes multinomiales y las "estrellas y barras" (que en adelante se llamarán coeficientes de los conjuntos múltiples )? ¿Para qué importa el orden? ¿Para qué no importa el orden? ¿Para qué es la elección con/sin sustitución?

Intento: Ambos implican un proceso de recuento con dos consideraciones: (i) dividir los objetos de $n$ tipos en $i$ contenedores, ii) cada contenedor con $k_i$ puntos, por lo que la asignación de $k = \sum_i k_i$ objetos de la $n$ diferentes tipos. Así que parece que puede haber cierta ambigüedad, cuando uno dice "con/sin sustitución" o "el orden importa/no importa", ¿se refiere a (i) o a (ii)?

Así que parece que hay al menos cuatro posibilidades distintas:

1. Asignar $n$ tipos de objetos en $i$ contenedores, donde el orden de los contenedores no lo hace materia, con $k = \sum_i k_i$ puntos en total, donde el orden dentro de cada contenedor no lo hace asunto.
2. Asignar $n$ tipos de objetos en $i$ contenedores, donde el orden de los contenedores no lo hace materia, con $k = \sum_i k_i$ puntos en total, donde el orden dentro de cada contenedor hace asunto.
3. Asignar $n$ tipos de objetos en $i$ contenedores, donde el orden de los contenedores hace materia, con $k = \sum_i k_i$ puntos en total, donde el orden dentro de cada contenedor no lo hace asunto.
4. Asignar $n$ tipos de objetos en $i$ contenedores, donde el orden de los contenedores hace materia, con $k = \sum_i k_i$ puntos en total, donde el orden dentro de cada contenedor hace asunto.

SI esto es cierto, entonces ¿cuál de estas opciones corresponde a los coeficientes multinomiales, y cuál de estas opciones corresponde a los coeficientes de conjuntos múltiples?

Actualización: Creo que la diferencia es ésta: "los coeficientes de los conjuntos múltiples son el número de formas de distribuir las bolas en cajas, donde (i) el número total de bolas es fijo, (ii) el número de bolas en cada contenedor es no fijo, (iii) las bolas son indistinguibles (su orden no importa, sólo el número en cada contenedor), (iv) las cajas son distinguibles (es decir, su orden hace materia)". (Para (iv), por ejemplo $x^2 y \not= x y^2$ .) Mientras que los "coeficientes multinomiales son el número de formas de distribuir las bolas en las cajas, donde (i) el número total de bolas es fijo porque (ii) el número de bolas en cada caja es fijo (iii) las bolas son indistinguibles (de ahí la relación con los coeficientes binomiales), y (iv) las cajas son distinguible (pero no importa en el caso de los binomios porque la solución de la ecuación diofantina $k_1 + k_2 = k$ ya está determinada una vez $k_1$ es elegido)".

Así que TL;DR: en ambos casos, las bolas son indistinguibles (su orden no importa), las cajas son distinguibles (su orden hace importa), el número total de bolas es fijo, pero (a) en el caso de los coeficientes multinominales, el número de bolas en cada caja no se fija de antemano, mientras que (b) en el caso de los coeficientes multinominales el número de bolas en cada caja es arreglado de antemano.

Por lo tanto, la diferencia estriba en si se fija de antemano cuántas bolas se van a colocar en cada caja.

Answer 1

Un coeficiente multinomial se suele escribir de la forma $$ \binom{n}{k_1,k_2,\ldots,k_m} $$ donde $k_1+k_2+\cdots+k_m = n.$ Debido a esta última ecuación, el $n$ es redundante. Los coeficientes binomiales también son técnicamente coeficientes multinomiales, pero en lugar de escribir $\binom{n}{k_1,k_2}$ donde $k_1+k_2 = n,$ solemos escribir $\binom{n}{k_1}$ o $\binom{n}{k_2}.$ Todo esto significa exactamente lo mismo: $$ \binom{k_1+k_2}{k_1,k_2}=\binom{k_1+k_2}{k_1} =\binom{k_1+k_2}{k_2} = \frac{(k_1+k_2)!}{k_1!\,k_2!}. $$

Un coeficiente multinomial puede surgir en un problema de recuento de la siguiente manera:

• Usted tiene $m$ contenedores, con tamaños $k_1, k_2, \ldots, k_m$ respectivamente.
• Usted tiene $n = k_1+k_2+\cdots+k_m$ objetos distinguibles, que son los justos para llenar cada contenedor cuando se extrae del $n$ objetos sin reemplazarlos.
• El orden de los contenedores es importante.
• El orden de los objetos dentro de cada contenedor no importa.

---

El coeficiente de un conjunto múltiple puede surgir de la siguiente manera:

• Usted tiene $n$ objetos distinguibles.
• Tienes un único contenedor capaz de albergar $k$ objetos.
• Los objetos se dibujan desde el $n$ objetos con reemplazo, y poner las copias de esos objetos en el contenedor.
• Se siguen poniendo copias de objetos en el contenedor hasta que esté lleno.
• El orden de los objetos en el contenedor no importa.

Un coeficiente multiset puede surgir alternativamente de esta manera:

• Usted tiene $k$ objetos que son indistinguibles o que usted decide no distinguir.
• Usted tiene $n$ contenedores, cada uno con capacidad efectivamente infinita (nunca se llenan).
• Dibuja los objetos sin reemplazarlos y colócalos en los contenedores.
• El orden de los contenedores es importante.
• El orden de los objetos en un contenedor no puede importa, porque por suposición no se puede saber qué objeto es cuál, sólo cuántos hay en cada contenedor.

Se trata de dos formas bastante diferentes de modelar un coeficiente de conjuntos múltiples: en un modelo, el número de objetos es el primer número del coeficiente, mientras que en el otro modelo el número de objetos es el segundo número. Pero hay un simple argumento de recuento que muestra que ambas formas modelan el mismo recuento total: cada vez que se elige uno de los $n$ objetos del primer modelo para ocupar uno de los $k$ lugares desordenados (por lo tanto indistintos) en el contenedor, se elige uno de los $n$ contenedores en el segundo modelo para contener uno de los $k$ objetos indistinguibles. Al igual que el primer modelo le permite elegir el mismo objeto tantas veces como quiera (hasta que todos los espacios del contenedor estén llenos), el segundo modelo te permite colocar objetos en el mismo contenedor tantas veces como quieras (hasta que todos los objetos estén colocados).

Mientras que el término "multiset" se inspira en el primer modelo, el segundo es una aplicación frecuente del método de "estrellas y barras". Es útil saber cómo aplicar el coeficiente de multiset a cualquiera de los dos modelos según sea necesario.

Answer 2

Motivación: Describir el número de monomios de grado $d$ en las variables $x_0, \dots, x_n$ requiere el uso de un multiset coeficiente, no un coeficiente multinomial. Cuando se me olvida el motivo, me cuesta explicarme por qué el coeficiente multiset funciona y por qué el multinomial no.

Antecedentes: Según la Wikipedia, son distintas, pero me cuesta centrarme en los aspectos clave que las diferencian, así como en los aspectos clave que las hacen similares.

A diferencia de lo que ocurre con los coeficientes binomiales, no existe un "teorema de conjuntos múltiples" en el que aparezcan los coeficientes de conjuntos múltiples, y no deben confundirse con los coeficientes multinomiales no relacionados que aparecen en el teorema multinomial. (Fuente)

Los coeficientes de los conjuntos múltiples y de los multinomios son distintos, pero aunque no estén relacionados entre sí, ambos parecen estar relacionados con los problemas de recuento que implican a los conjuntos múltiples.

• n multichoose k viene dada por la sencilla fórmula

$$((n; k))=(n+k-1; k)=(n-1,k)!,$$ donde (n-1,k)! es un coeficiente multinomial. (Fuente)

• Los coeficientes multinomiales $$(n_1,n_2,...,n_k)!=\frac{((n_1+n_2+...+n_k)!)}{(n_1!n_2!...n_k!)} $$ son los términos de la expansión de la serie multinomial. En otras palabras, el número de permutaciones distintas en un subconjunto de k elementos distintos de multiplicidad $n_i (1 \le i \le k)$ es $(n_1,...,n_k)!$ (Skiena 1990, p. 12). (Fuente)

• Un coeficiente multinomial se asocia a cada conjunto múltiple (finito) tomado de el conjunto de los números naturales. Dicho multiconjunto viene dado por una lista $k_1, . . . , k_n,$ donde los números pueden repetirse, y donde el orden no importa ... El número total de tales multiíndices es $(\binom{n}{k})$ . El índice múltiple N determina un conjunto múltiple $k_1, . . . , k_n$ tomada de los números naturales. Este multiconjunto está formado por los valores de la función N. Tiene menos información que el índice múltiple $N$ ya que ha perdido la información sobre qué elementos de $B$ indexar los números. (Fuente)

• El número de combinaciones de conjuntos múltiples es igual al coeficiente multinomial (n multichoose k). (Fuente)

Actualmente entiendo que el coeficiente multinomial es el número de formas de asignar $n$ objetos a $i$ contenedores con $k_i$ puntos cada uno y $k = \sum_i k_i$ puntos totales, donde el orden importa.

Esta explicación tiene sentido para mí en la medida en que explica por qué la suma de todos los coeficientes multinomiales es $i^k = i^n$ cuando $k=n$ . Sin embargo, no tiene sentido para mí en la medida en que los coeficientes multinomiales se supone que están relacionados con los coeficientes binomiales que se supone que dan el número de formas de elegir elementos cuando el orden no lo hace asunto.

Pero si el orden no importa para los coeficientes multinomiales, tampoco importa para los coeficientes de conjuntos múltiples, lo que no deja una forma clara de distinguirlos:

Una k-combinación con repeticiones, o k-multicombinación, o multisubconjunto de tamaño k de un conjunto S está dada por una secuencia de k elementos no necesariamente distintos de S, donde no se tiene en cuenta el orden . (Fuente)