Quiero demostrar esta fórmula de recursión para los números de Stirling del primer tipo:
$$s_{n+1,k+1} = \sum_{i=k}^{n} \binom{i}{k} s_{n,i}$$
Pero me falta una idea útil. ¿Quizás alguien pueda inspirarme?
Saludos cordiales.
Respuestas
¿Demasiados anuncios?
Una pista: Utilizando la fórmula del factorial descendente , tenga en cuenta que
$$(x)_{n+1} = x \cdot (x-1)_n \; .$$
Desarrollar el factorial descendente en términos de números de Stirling del primer tipo y potencias de $(x-1)^k$ . A continuación, utiliza la fórmula binomial de Newton para expandir las potencias $(x-1)^k$ . Un poco de reordenación de los términos termina la prueba.
De (nota que he modificado un poco su fórmula, verás que es más fácil reconocer el resultado final)
$$\sum_{i=0}^{n}\sum_{k=0}^{i} s(n,i)\binom{i}{k} (-1)^{i-k} x^{k+1}$$
se puede reordenar como
$$\sum_{k=0}^{n}\sum_{i=k}^{n} s(n,i)\binom{i}{k} (-1)^{i-k} x^{k+1} \; .$$
Si no lo ves, resuelve algunos términos de esta doble suma explícitamente, debería ser obvio. Entonces el lado izquierdo de la ecuación factorial descendente es
$$(x)_{n+1}=\sum_{k=0}^{n+1} s(n+1,k) x^k = \sum_{k=0}^{n} s(n+1,k+1) x^{k+1}$$
Igualando el lado izquierdo y el derecho, obtenemos
$$s(n+1,k+1) = \sum_{i=k}^{n} s(n,i)\binom{i}{k} (-1)^{i-k} \; .$$
Ahora bien, esto puede parecer diferente de la fórmula que se le pidió que derivara, pero eso es sólo porque yo derivé una fórmula para los números Stirling con signo del primer tipo, mientras que la suya era probablemente para los que no tienen signo. Sin embargo, no hay problema, basta con multiplicar ambos lados de las ecuaciones por $(-1)^{k-n}$ y según la definición de la página web, obtendrá el resultado final.
Martin OConnor
Puntos
116
Aquí hay otros tres enfoques de prueba.
En primer lugar : Demuestre que ambos lados satisfacen la recurrencia $R(n,k) = n R(n-1,k) + R(n-1,k-1)$ con la condición de límite $R(0,k) = 1$ si $k = 0$ y $0$ de lo contrario.
Si $R(n,k) = s_{n+1,k+1}$ entonces la recurrencia se satisface claramente, ya que se trata de la recurrencia estándar para los números de Stirling del primer tipo.
Para el lado derecho, con $R(n,k) = \sum_{i=k}^n \binom{i}{k} s_{n,i}$ , utilice de nuevo la recurrencia de Stirling, reindexe una de las sumas y aplique la recurrencia del coeficiente binomial.
Después sólo queda comprobar las condiciones de contorno.
Segundo : Utilice la función generadora $$\sum_{n=0}^{\infty} s_{n,k} \frac{z^n}{n!} = \frac{\left(\ln \left( \frac{1}{1-z} \right) \right)^k}{k!}.$$ (Véase, por ejemplo, Matemáticas concretas (7.50) en la página 351.) Comience con la versión para $s_{n+1,k+1}$ , diferenciar ambos lados, expandir el factor de $\frac{1}{1-z}$ utilizando la serie de Taylor para $e^{\ln (1/(1-z))}$ y aplicar de nuevo la función generadora. (Este argumento se encuentra en la obra de Charalambides Combinatoria Enumerativa , p. 296.)
Tercero : Utiliza un argumento combinatorio. El lado izquierdo cuenta el número de permutaciones de $\{0, 1, \ldots, n\}$ con exactamente $k+1$ ciclos. El lado derecho cuenta el número de permutaciones de $\{1, 2, \ldots, n\}$ con cualquier número de ciclos y en el que $k$ de los ciclos se distinguen de alguna manera. Establece una correspondencia uno a uno entre los dos conjuntos combinando los ciclos no distinguidos del lado derecho en un ciclo e insertando un $0$ en el lugar correcto. (Véase, por ejemplo, Benjamin y Quinn, Pruebas que realmente cuentan (Identidad 190, p. 102).
Jorrit Reedijk
Puntos
129
Esto debería ir como comentario, no como respuesta (no aporta pruebas adicionales), pero es demasiado largo para la caja de comentarios y puede ser interesante de todos modos.
Su relación dada describe un desplazamiento de la matriz de los números de Stirling de tipo 1 por una postmultiplicación de la matriz de Pascal: $ S1_0 * P_0 = S1_1 $ donde el índice indicaba una reducción diagonal. Ver las matrices $S1_0, P_0,S1_1$ abajo: $$ \small \begin{matrix} & & & S1_0 & & & | & & & & P_0 & & & | & & & S1_1 & & & \\ 1 & . & . & . & . & . & | & 1 & . & . & . & . & . & | & 1 & . & . & . & . & . \\ -1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . & | & . & 1 & . & . & . & . \\ 2 & -3 & 1 & . & . & . & | & 1 & 2 & 1 & . & . & . & | & . & -1 & 1 & . & . & . \\ -6 & 11 & -6 & 1 & . & . & | & 1 & 3 & 3 & 1 & . & . & | & . & 2 & -3 & 1 & . & . \\ 24 & -50 & 35 & -10 & 1 & . & | & 1 & 4 & 6 & 4 & 1 & . & | & . & -6 & 11 & -6 & 1 & . \\ -120 & 274 & -225 & 85 & -15 & 1 & | & 1 & 5 & 10 & 10 & 5 & 1 & | & . & 24 & -50 & 35 & -10 & 1 \end{matrix} $$ Esto se puede iterar, por lo que $ S1_{k+1} = S_k * P_k $
Entonces la parte superior izquierda del resultado se convierte -con el aumento de k - la identidad y podemos formular el límite donde $n \to \infty$ que se extiende a la matriz de identidad. Pero esto significa, que ese producto de las Pascalmatrices desplazadas hacia abajo es igual a la inversa de $S1$ (hasta la dimensión n) y, por otro lado, la inversa no es más que la matriz de los números de Stirling del 2º tipo. Así que obtenemos, denotando el segmento superior izquierdo de esa matriz $S2$ hasta la dimensión $n$ como $$S2 = \prod_{k=0}^n P_k $$ y los tres segmentos de nivel superior son $P, P*P_1 , P*P_1*P_2 $ y la tercera de las tres matrices de abajo tiene sus tres columnas izquierdas idénticas a la matriz de los números de Stirling del 2º tipo: $$ \small \begin{matrix} & & & P_0 & & & | & & & & P_0* &P_1 & & | & & P_0* & P_1* & P_2 & & \\ 1 & . & . & . & . & . & | & 1 & . & . & . & . & . & | & 1 & . & . & . & . & . \\ 1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . \\ 1 & 2 & 1 & . & . & . & | & 1 & 3 & 1 & . & . & . & | & 1 & 3 & 1 & . & . & . \\ 1 & 3 & 3 & 1 & . & . & | & 1 & 7 & 5 & 1 & . & . & | & 1 & 7 & 6 & 1 & . & . \\ 1 & 4 & 6 & 4 & 1 & . & | & 1 & 15 & 17 & 7 & 1 & . & | & 1 & 15 & 25 & 9 & 1 & . \\ 1 & 5 & 10 & 10 & 5 & 1 & | & 1 & 31 & 49 & 31 & 9 & 1 & | & 1 & 31 & 90 & 52 & 12 & 1 \end{matrix} $$
Las dos representaciones de productos que implican a las Pascalmatrices desplazadas dan entonces una bonita generalización de tu identidad inicial a productos/sumas de binomios anidados (de profundidad arbitraria) para los números Stirling de 1ª y 2ª clase (un bonito e inagotable recurso para los deberes, por cierto ;-) )
[actualización] Traté de relacionarme con la segunda identidad de Mike Spivey. Sorpresa, obtenemos los números de Bernoulli, escalados por factoriales en lugar de binomios.
Denote la matriz diagonal de los factoriales $F=diagonal(0!,1!,2!,...)$ y $f=F^{-1}$ y luego la matriz factorialmente escalada de los números de Stirling del primer tipo, cuya columna c's proporciona los coeficientes de la serie de potencias para $\ln(1+x)^c$ , como $fS1F = f* S1 * F $ (se trata de una escala de similitud de $S1$ ) y la matriz de números Bernoulli de escala factorial como $fBF$ entonces obtenemos un desplazamiento inverso col/fila por $ fS1F_1 * fBF = fS1F_0 $
$$ \small \begin{matrix} & & & fS1F_1 & & & | & & & & fBF & & & | & & & fS1F_0 & & & \\ 1 & 0 & 0 & 0 & 0 & 0 & | & 1 & 0 & 0 & 0 & 0 & 0 & | & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & | & -1/2 & 1 & 0 & 0 & 0 & 0 & | & -1/2 & 1 & 0 & 0 & 0 & 0 \\ 0 & -1/2 & 1 & 0 & 0 & 0 & | & 1/12 & -1/2 & 1 & 0 & 0 & 0 & | & 1/3 & -1 & 1 & 0 & 0 & 0 \\ 0 & 1/3 & -1 & 1 & 0 & 0 & | & 0 & 1/12 & -1/2 & 1 & 0 & 0 & | & -1/4 & 11/12 & -3/2 & 1 & 0 & 0 \\ 0 & -1/4 & 11/12 & -3/2 & 1 & 0 & | & -1/720 & 0 & 1/12 & -1/2 & 1 & 0 & | & 1/5 & -5/6 & 7/4 & -2 & 1 & 0 \\ 0 & 1/5 & -5/6 & 7/4 & -2 & 1 & | & 0 & -1/720 & 0 & 1/12 & -1/2 & 1 & | & -1/6 & 137/180 & -15/8 & 17/6 & -5/2 & 1 \end{matrix} $$
