Números de Stirling, coeficientes binomiales

Question

Me podrían ayudar a probar el siguiente:

$$\left\{n\atop k\right\} = \frac{1}{k!} \cdot \sum^{k}_{j=0} {k\choose j} \cdot j^{n} \cdot (-1)^{k-j}$$

Se ve muy aterrador para mí. He buscado en Graham, Knuth, Patashnik "Concreto de las Matemáticas", pero no lo he encontrado. Todo lo que sé sobre números de Stirling es que podemos utilizarlas como coeficientes en $x^{(n)(n-1)...(n-k+1)}$ en la suma de $ x^k, \ 0 \le k \le n$

o en $x^n$ cuando queremos expresar como una suma de $x^{(n)(n-1)...(n-k+1)}$. Pero no creo que esto me ayudaría en cualquier forma.

Creo que dividir la suma en el lado izquierdo por $k!$ porque cuando elegimos subconjuntos orden no importa. Entonces quizá ${k\choose j}$ significa que elegimos $j$ elementos a nuestro $k$ -elemento del subconjunto y podemos elegir en $j^n$ (?) formas y $(-1)^{k-j}$ debe significar la inclusión\principio de exclusión.

Por favor, ayudar.

Answer 1

$\left\{n\atop k\right\}$ es la cantidad de formas de poner$n$ objetos distinguibles en exactamente$k$ cuadros indistinguibles. Si damos las identidades de los recuadros, se pueden permutar en$k!$ formas, por lo que$\sum_{j\ge 0}\binom{k}jj^n(-1)^{k-j}$ debe ser el número de maneras de poner$n$ objetos distinguibles en$k$ cuadros distinguibles a la condición de que ninguna caja esté vacía. En otras palabras, debe ser el número de supresiones de$[n]$ a$[k]$, y de hecho lo es, mediante un argumento de inclusión-exclusión directo.