Igualdad de números Stirling

Question

Cómo demostrar que $\left\{{n}\atop{k}\right\} = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [1\le i_1\le i_2 \le \ldots \le i_{n-k}\le k]\ $ y $\left[{n}\atop{k}\right] = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [0< i_1 < i_2 < \ldots < i_{n-k} < n]$ ? Lo siento, pero no sé ni cómo empezar...

Answer 1

SUGERENCIA: Los números de Stirling del segundo satisfacen la recurrencia

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}\;.$$

Dejemos que

$$f(n,k)=\sum_{i_1,\ldots,i_{n-k}}[1\le i_1\le\ldots\le i_{n-k}\le k]\prod_{j=1}^{n-k}i_j\;;$$

la idea es demostrar que $f(n,k)$ satisface la recurrencia

$$f(n+1,k)=kf(n,k)+f(n,k-1)$$

con los mismos valores iniciales. Los productos $\prod_{j=1}^{(n+1)-k}i_j$ con $1\le i_1\le\ldots\le i_{(n+1)-k}\le k$ pueden dividirse en dos conjuntos: los que tienen $i_{(n+1)-k}=k$ y los que tienen $i_{(n+1)-k}<k$ .

• Demuestre que la suma de los productos del primer conjunto es $kf(n,k)$ .
• Demuestre que la suma de los productos del segundo conjunto es $f(n,k-1)$ .
• Comprueba los valores iniciales.

Para la otra parte del problema, recordemos que los números de Stirling del primer tipo satisfacen la recurrencia

$${{n+1}\brack k}=n{n\brack k}+{n\brack{k+1}}\;.$$

Answer 2

Su segunda fórmula se deduce directamente de la comparación de los coeficientes en la conocida identidad $$x(x-1)\dots (x-n+1)=\sum_{k=0}^n(-1)^{n-k}\left[{n}\atop{k}\right]x^k.$$ No estoy seguro de cómo hacer la primera fórmula sin inducción.