Interpretación combinatoria de la fórmula explícita para los números de Stirling de segunda clase

$\begin{Bmatrix} n\\ k \end{Bmatrix}$es el número de formas de distribuir$n$objetos distintos en$k$cajas idénticas sin permitir cajas vacías/cada caja contiene al menos$1$objeto. Primero consideraremos las distribuciones en$k$cajas distintas.

El número total de formas de distribuir$n$objetos distintos en$k$casillas distintas con casillas vacías permitidas es:

$$k^n$$

Dejar$A_i$sea ​​el número de formas de realizar la distribución con la condición de que la casilla$i$debe ser una caja vacía. No hay restricciones en las otras cajas. (Esto es equivalente a distribuir el$n$objetos en el resto$k-1$cajas, cajas vacías permitidas.)

Por ejemplo$A_1$es el número de formas de distribuir los objetos en el$k$cajas con la caja 1 vacía y es equivalente a distribuir los objetos en el resto$k-1$cajas, cajas vacías permitidas.

$$\implies |A_1| = (k-1)^n$$

Ahora notamos que$|A_1|=|A_2|=|A_3|=\dots$ya que no importa qué casilla esté vacía. (Siempre estamos distribuyendo en el resto$k-1$cajas).

sabemos que hay$\binom{k}{1}$posible$A_i$

$$\sum_{i=1}^k|A_i| = \binom{k}{1}(k-1)^n$$

Usando un argumento similar,$|A_i\cap A_j|=(k-2)^n$porque implica la distribución en$k-2$cajas restantes. Además, utilizando el hecho de que$|A_1\cap A_2|=|A_1\cap A_3|=|A_1\cap A_4|...$y que hay$\binom{k}{2}$tales términos,

$$\sum_{1\leq i,j\leq k}|A_i\cap A_j| = \binom{k}{2}(k-2)^n$$

En una nota similar, tratamos de extender esto a cuando$l$Las cajas deben estar vacías:

$$\sum_{1\leq i,j\dots l\leq k}|A_i\cap A_j\cap \dots\cap A_l| = \binom{k}{l}(k-l)^n$$

$|A_1\cup A_2\cup \dots \cup A_k|$es el número de formas de distribuir$n$objetos distintos en$k$casillas distintas con al menos una casilla vacía.

Estamos tratando de encontrar la distribución sin casillas vacías:

$$|\overline{A_1\cup A_2\cup \dots \cup A_k}|=k^n -|A_1\cup A_2\cup \dots \cup A_k|$$

Por el principio de inclusión y exclusión,

$$=k^n-(|A_1|+|A_2|+|A_3|+...)+(|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+...)-...$$

$$=k^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n-\binom{k}{3}(k-3)^n+\dots +(-1)^l\binom{k}{j}(k-j)^n$$

$$=\sum_{l=0}^{k}(-1)^l\binom{k}{l}(k-l)^n$$

Dejar$j=k-l$, cuando$l=0$,$j=k$. Cuando$l=k$,$j=0$.

$$=\sum_{j=k}^{0}(-1)^{k-j}\binom{k}{k-(k-j)}j^n (\text{this is technically wrong notation})$$

Esto es solo la suma al revés. Entonces tenemos:

$$=\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

Ahora dividimos por$k!$ya que estamos tratando con cajas idénticas:

$$\begin{Bmatrix} n\\ k \end{Bmatrix} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$