¿De cuántas maneras se pueden disponer m objetos elegidos cuando hay n objetos en total, y algunos son indistintos?

Question

Tengo $n$ diferentes tipos de objetos, donde cada miembro de un tipo es indistinguible de cualquier otro miembro.

Hay $k_1$ del primer tipo, $k_2$ del segundo tipo, y así sucesivamente, hasta $k_n$ de la $n$ el tipo.

Quiero elegir sólo algunos de estos objetos, llamarlos $m$ , donde $m \le \sum\limits_{i=1}^{n}k_i$ .

En el caso de que $m = \sum\limits_{i=1}^{n}k_i$ la fórmula es $\frac{m!}{k_1!k_2!...k_n!}$

¿Cuál es la fórmula si no me llevo todos los objetos? Más bien, $m$ es estrictamente menor que $\sum\limits_{i=1}^{n}k_i$

EDIT: He tratado de pensar en ello de una manera directa, como la derivación de la fórmula que di. Hay una buena explicación en otra pregunta aquí: Combinación y permutación de objetos indistintos .

Pero siempre me encuentro con el problema de que la cantidad de cada tipo es fija y no se puede utilizar en su totalidad. Últimamente, he tratado de pensar en ello como poner $m$ objetos en $n$ cajas, donde las cajas tienen diferentes capacidades máximas. Yo también me quedo atascado ahí.

Answer 1

Desde entonces he hecho un curso de combinatoria y he decidido compartir lo que he aprendido.

Se utilizan funciones generadoras. Primero, examinar el caso en el que el orden de elección de los objetos no importa . Si tienes 3 objetos rojos, 5 verdes y 4 azules, podemos representar la pregunta como un polinomio, concretamente

$(1+x+x^2+x^3)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4)$

donde el primer factor representa los objetos rojos, el segundo el verde y el tercero el azul. Después de multiplicar el polinomio y combinar los términos similares, simplemente mira el coeficiente del término correcto. Si quieres saber cuántas formas de elegir $n$ objetos, se miraría el coeficiente del $x^n$ término. En este ejemplo, el polinomio expandido y luego simplificado es

$1+3x+6x^2+10x^3+14x^4+17x^5+18x^6+17x^7+14x^8+10x^9+6x^{10}+3x^{11}+x^{12}$

Así que si queremos saber de cuántas maneras se pueden escoger 6 objetos en los que el orden de los mismos no importa, miraríamos el $x^6$ coeficiente, que en este caso es de 18.

Obsérvese que el coeficiente de $x^{12}$ es 1. Esto tiene sentido porque al elegir doce se eligen todos los objetos, y como el orden es irrelevante, sólo existe una forma, es decir, elegirlos todos. En general este método funciona porque al multiplicar el polinomio se obtienen todas las formas posibles de sumar cada grado. Así, para $x^6$ estamos viendo el caso en el que hay 3 rojos, 3 verdes y 0 azules (multiplicar el $x^3$ término de los rojos, el $x^3$ término de los verdes, y el término 1 de los azules) que se suma al caso en el que hay dos de cada uno (multiplicando el $x^2$ término de cada factor), que se suma a todas las demás formas posibles de sumar hasta 6 utilizando los números que tenemos a mano.

Para el proceso general que se pide en la pregunta, busque el coeficiente de $x^m$ en el polinomio

$(1+x+x^2+...+x^{k_1})(1+x+x^2+...+x^{k_2})(1+x+x^2+...+x^{k_3})...(1+x+x^2+...+x^{k_n})$

Para el caso de que el orden sea importante que era lo que realmente pedía la pregunta, se utiliza una función generadora exponencial. La principal diferencia es que cada $x^n$ se divide por $n!$ (para que cada término se vea como $\frac{x^n}{n!}$ ). También se observa el coeficiente de $\frac{x^m}{m!}$ Es igual que el primer ejemplo y el razonamiento es similar. El $x^3$ sigue representando los casos en los que se eligen 3 objetos de esa categoría, pero ahora tiene un bit adicional que dice cuántas formas diferentes hay de ordenar esos tres objetos.

El primer ejemplo reescrito para cuando el orden importa tiene el siguiente aspecto:

$(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!})$

Así que para ser claros, la respuesta a cuántas formas hay de elegir $m$ objetos de este pool donde el orden que importa es el coeficiente de $\frac{x^m}{m!}$ , que es como pedir el coeficiente de $x^m$ y multiplicándolo por $m!$ .

Obsérvese que el coeficiente de $\frac{x^{12}}{12!}$ en este ejemplo es $\frac{12!}{3!5!4!}$ que corresponde a la fórmula publicada en la pregunta donde $m=\sum_{i=1}^{n}k_i$ .

Para el proceso general que se pide en la pregunta, busque el coeficiente de $x^m$ en el polinomio

$(1+x+\frac{x^2}{2!}+...+\frac{x^{k_1}}{k_1!})(1+x+\frac{x^2}{2!}+...+\frac{x^{k_2}}{k_2!})(1+x+\frac{x^2}{2!}+...+\frac{x^{k_3}}{k_3!})...(1+x+\frac{x^2}{2!}+...+\frac{x^{k_n}}{k_n!})$

y multiplicar la respuesta por $m!$

Answer 2

Puede ser una respuesta decepcionante, pero no creo que haya una mejor. Lo que hay que hacer es reducir este problema al caso en que $m = \sum k_i$ aunque acabará siendo bastante feo.

Para cualquier arreglo dado que estemos contando, existirá $(r_1,r_2,\ldots,r_n)$ s.t. tenemos precisamente $r_i$ objetos de tipo $i$ . Para cualquier elección de $(r_1,\ldots ,r_n)$ sabemos exactamente cuántos arreglos podemos tener con $r_i$ objetos de $i$ : $\frac{m!}{r_1! r_2! \cdots r_n!}$ . A continuación, tenemos que sumar todos los posibles $(r_1,\ldots,r_n)$ es decir, tenemos que contar con todos los $(r_1,\ldots,r_n)$ donde $r_i \geq k_i$ y $\sum r_i = m$ . Por lo tanto, tenemos que el número total de arreglos es $$ \sum\limits_{\substack{r_1 + r_2 + \ldots + r_n = m \\ r_i \geq k_i}}^n \frac{m!}{r_1! r_2! \cdots r_n!}. $$

No creo que esta suma (o respuesta) se pueda simplificar: en el caso de $n = 2$ esto se reduce a una suma parcial de coeficientes binomiales, que tiene no se conoce ninguna forma cerrada (útil) .