October | 2009 | Spin Foam

Contar la cantidad de formas en que pueden distribuirse $n$ elementos en $k$ cajas es bastante simple, una vez que descubrimos el truco de pensarlo como asignarle un número de caja a cada elemento. Claramente esto nos da $k^n$ posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja $k^n/k!$ formas.
[Nota 22/7/13: este análisis es incorrecto, como indica Jon abajo. El análisis correcto de este se encuentra en una nueva página.]

Este problema se hace más difícil si agregamos la restricción de que ninguna caja puede permanecer vacía y, de hecho, recuerdo haber esquivado resolver este problema en más de una ocasión (y no soy el único 😀 ). Pero en Wikipedia encontré una solución elegante y, tal vez, lo suficientemente memorable para que la recuerde en caso de encontrarme nuevamente con este problema…

Denominemos

$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$

al número de distintas formas en las que podemos distribuir $n$ elementos en $k$ cajas sin dejar ninguna vacía y sin distinguir entre cajas (o sea el número de distintas particiones de $\{1,2,...,n\}$ en $k$ subconjuntos). Entonces podemos dividir las formas de efectuar esta distribución en dos clases: las que ponen al elemento $n$ solo en una caja y las que no lo hacen.

Una vez situado el elemento $n$ en una caja, las distribuciones serán equivalentes a $n-1$ elementos en $k-1$ cajas. Por lo tanto, habrá

$\left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\}$

formas de efectuar la distribución dejando solo al elemento $n$ .

Por otro lado, si el elemento $n$ no se encuentra solo, el problema es equivalente a distribuir $n-1$ elementos en $k$ cajas sin dejar ninguna vacía y luego insertar el elemento $n$ en alguna de ellas (distinguibles por tener distintos subconjuntos de los elementos). En consecuencia habrá

$k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}$

formas de efectuar la distribución sin dejar al elemento $n$ solo en una caja.

En conjunto eso nos deja la relación de recurrencia

$\left\{\begin{matrix} n \\ k \end{matrix}\right\} = \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} + k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}$