Sobre y buzones

Question

Supongamos que $n$ y $p$ son dos enteros positivos.

A) ¿De cuántas formas se pueden dividir $p$ sobres idénticos en $n$ buzones? (Cada buzón puede contener varios sobres a la vez)

B) ¿De cuántas formas se pueden dividir $p$ sobres distintos en $n$ buzones?

C) ¿De cuántas formas se pueden dividir $p$ sobres idénticos en $n$ buzones, de modo que ningún buzón quede vacío? (se asume que $p$ es mayor o igual que $n$)

¿Alguna idea?

Answer 1

A y C) Si tienes $n$ buzones diferentes, deja que $x_i$ sea el número de sobres en el buzón $i$. El número de formas en que puedes poner $m$ sobres idénticos en $n$ cajas es el número de soluciones de la siguiente ecuación: $$ x_1+x_2+...+x_n=m $$ Si $x_i>0$, el número de formas es $\binom{m-1}{n-1}$, de lo contrario si $x_i\geq 0$, el número de formas es $\binom{n+m-1}{n-1}.

Prueba: Cuando $x_i>0$, Cada caso de colocar sobres en buzones puede ser representado por una secuencia de $m$ veces la letra $A$ y $n-1$ veces la letra $B$ de tal manera que no haya dos $B$ juntas. Por ejemplo, si tenemos $m=5$ sobres y $n=3$ buzones, y si hay respectivamente $1,1,3$ en cada caja podemos representarlo como: $$ A\,\,\,\,\,B\,\,\,\,\,A\,\,\,\,\,B\,\,\,\,\, AAA $$ En esta representación, el problema es equivalente a colocar cada $B$ solo en uno de los $m-1$ lugares entre dos $A$ consecutivas (Sin $B$ al principio y al final de la secuencia) y no tener dos $B$ en el mismo lugar, por lo tanto tenemos que elegir $n-1$ lugares de $m-1$. Cuando $x_i\geq 0$, es suficiente reemplazar $x_i=y_i-1$ y el problema se convierte en el anterior.

B) Si tienes $m$ sobres distintos y $n$ cajas diferentes, entonces debes multiplicar los números anteriores por $m!$.

Prueba: La prueba sigue básicamente la misma idea con la diferencia de que los $A$s son distintos y hay $m!$ formas diferentes de ponerlos como una secuencia.