Número de formas de dividir un conjunto en un conjunto de conjuntos

Question

En realidad se trata de dos preguntas relacionadas. En primer lugar, me parece que dado un conjunto de $n$ objetos se puede dividir en un conjunto de subconjuntos de $a_1$ conjuntos que contienen $n_1$ objetos, $a_2$ conjuntos que contienen $n_2$ y así sucesivamente, de forma que $a_1\cdot n_1 + a_2\cdot n_2 + \cdots + a_m\cdot n_m = n$ de la siguiente manera:

$$\frac{\binom{n}{n_1}\cdot\binom{n-n_1}{n_1}\cdots\binom{n-(a_1-1)n_1}{n_1}\cdot\binom{n-a_1n_1}{n_2}\cdots\binom{n-a_1n_1-(a_2-1)n_2}{n_2}\cdots\binom{n-a_1n_1-a_2n_2\cdots}{n_m}}{a_1!a_2!\cdots a_m!}$$

Un ejemplo sería dividir un conjunto de 13 objetos distintos en 2 conjuntos de 2 objetos y 3 conjuntos de 3:

$$\frac{\binom{13}{2}\binom{11}{2}\binom{9}{3}\binom{6}{3}\binom{3}{3}}{2!3!}$$

Sin embargo, derivado de otra pregunta de mi libro parece haber otra fórmula general para calcular esto cuya explicación combinatoria no entiendo muy bien:

$$\frac{n!}{a_1!a_2!\cdots a_m!(n_1 !)^{a_1} \cdot (n_2 !)^{a_2} \cdots (n_m !)^{a_m}}$$

Basándome en mi ejemplo anterior obtendría:

$$\frac{13!}{2!(2!)^2 3!(3!)^3}$$

En primer lugar, ¿es correcta esta fórmula general y, en caso afirmativo, cómo se explica?

Espero que la explicación de la primera parte quede clara.

Answer 1

Su primera fórmula aunque no se da con todo detalle, es correcta si se hace una interpretación razonable de lo que usted quiere decir con $\dots$ . No se da ninguna explicación sobre la primera fórmula: no se menciona el razonamiento que condujo a ella. Aunque el razonamiento real es fácil de adivinar por la estructura de la fórmula, debería darse alguna explicación. Damos una justificación de la segunda fórmula .

Supongamos que todos los $n_i$ son distinto . Esto no se mencionó explícitamente, pero es una necesario suposición. En caso contrario, el resultado es falso.

Imagínese organizar nuestro $n$ objetos seguidos. Ahora agrupa el primer $n_1$ juntos, luego el siguiente $n_1$ y así sucesivamente hasta obtener $a_1$ grupos de $n_1$ miembros cada uno. A continuación, haga lo mismo con $n_2$ etc.

Haga esto para cada uno de los $n!$ permutaciones de nuestro $n$ objetos. Obtendremos todas las divisiones del tipo que busca. El único problema es que obtenemos cada división de más de una manera. Pero por suerte cada división se obtiene en la mismo varias maneras.

Cada división en grupos de $n_1$ se produce en $a_1!(n_1!)^{a_1}$ formas. Esto se debe a que cada una de las $a_1$ pequeños grupos pueden permutarse internamente en $n_1!$ formas, para un total de $(n_1!)^{a_1}$ formas. Entonces cada de la $a_1$ pueden permutarse como bloques en $a_1!$ maneras. La misma consideración se aplica a todos los $i \le m$ . Por lo tanto, tenemos que dividir $n!$ por $$\left[a_1!a_2!\cdots a_m!\right]\left[(n_1!)^{a_1}(n_2!)^{a_2}\cdots (n_m!)^{a_m}\right].$$