Una identidad para la función factorial

Question

Un amigo mío estaba garabateando con números dispuestos de una manera que recordaba al Triángulo de Pascal, donde la primera fila era $ 1^{n-1} \ 2^{n-1} \dots n^{n-1} $ y las filas subsiguientes se calcularon tomando la diferencia de los términos adyacentes. Conjeturó que el número que obtenemos al final es $ n! $ pero no he sido capaz de probar o refutar esto. Los primeros cálculos se dan a continuación: $$ \begin {pmatrix} 1 \\ \end {pmatrix} $$

$$ \begin {pmatrix} 1 & & 2 \\ & 1 & \\ \end {pmatrix} $$

$$ \begin {pmatrix} 1 & & 4 & & 9 \\ & 3 & & 5 & \\ & & 2 & & \\ \end {pmatrix} $$

$$ \begin {pmatrix} 1 & & 8 & & 27 & & 64 \\ & 7 & & 19 & & 37 & \\ & & 12 & & 18 & & \\ & & & 6 & & & \\ \end {pmatrix} $$

$$ \newcommand\pad [1]{ \rlap {#1} \phantom {625}} \begin {pmatrix} 1 & & 16 & & 81 & & 256 & & 625 \\ & 15 & & 65 & & 175 & & 369 & \\ & & 50 & & 110 & & 194 & & \\ & & & 60 & & 84 & & & \\ & & & & 24 & & & & \\ \end {pmatrix} $$

Intenté escribir el término general y traté de reducirlo a la forma requerida. El término general resultó ser ( corregido ) $$ \sum_ {i=0}^n (-1)^{n-i} \binom {n}{i} i^{n}. $$

Intenté aplicar varias identidades de los coeficientes del binomio, pero apenas estoy progresando. Cualquier ayuda sería apreciada.

Answer 1

Las filas superiores están hechas de hecho de los poderes $i^n=P_n(i)$ que son polinomios de grado $n$ con el coeficiente principal $1$ .

En la siguiente fila se toma la diferencia de primer orden. Por la fórmula del binomio, tenemos

$$P_{n-1}(i)=P_n(i+1)-P_n(i)=i^n+ni^{n-1}+\cdots-i^n=ni^{n-1}+\cdots$$

que es un polinomio de grado $n-1$ con el coeficiente principal $n$ .

Para la siguiente fila, $$P_{n-2}(i)=P_{n-1}(i+1)-P_{n-1}(i)=n(n-1)i^{n-2}+\cdots$$ y así sucesivamente.

En la última fila, tenemos un polinomio de grado $0$ con el coeficiente principal $n!$ y todo lo demás se ha desvanecido.

---

En realidad, se hará la misma observación a partir de cualquier polinomio en $i$ el valor final es $p_nn!$ , donde $p_n$ es el coeficiente inicial principal. Y si se amplía la tabla a la derecha, la fila inferior permanece constante.

Por ejemplo

$$2i^3+i\\\Delta_1=6i^2+6i+3\to2\cdot3\,i^2\\\Delta_2=12i+4\to2\cdot3\cdot2\,i^1\\\Delta_3=12\to2\cdot3\cdot2\cdot1\,i^0.$$

Answer 2

Esta es otra forma de demostrar que $$ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n = n!$$

Consideramos el conjunto $S$ formado por todas las cadenas de longitud $n$ compuesto por los símbolos $a_1, a_2, \cdots, a_n$ con repetición permitida.

Entonces tenemos claramente que $|S|=n^n$ porque hay $n$ para cada símbolo de la cadena.

Ahora dejemos que $A_k$ es el conjunto de todas las cadenas que no contienen el símbolo $a_k$ .

Para cualquier número natural $i_1, i_2, \cdots, i_k$ (donde $k\leq n$ es algún número natural) tal que $$ 0 < i_1 < i_2 < i_3 \cdots < i_k \leq n$$ podemos calcular la cardinalidad del conjunto $$ A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} $$

Hay $(n-k)$ para cada símbolo de alguna cadena en la intersección anterior, ya que dicha cadena puede consistir (y sólo puede consistir) en cualquiera de los símbolos que no son $a_{i_1}, a_{i_2}, \cdots, a_{i_k}$ .

Así, vemos que $$ \left|A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} \right| = (n-k)^n $$

Ahora podemos aplicar el principio de inclusión-exclusión para encontrar la cardinalidad del conjunto $$ A_1\cup A_2\cup A_3 \cup\cdots\cup A_n $$

Tenemos que $$ \left|A_1\cup A_2\cup A_3 \cup\cdots\cup A_n \right| = \sum_{k=1}^{n} (-1)^{k+1} \left(\sum_{0<i_1<i_2<\cdots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} \right|\right) $$

Para cada $k$ Hay $\binom{n}{k}$ formas de elegir los números $i_1, i_2, i_3, \cdots, i_k$ por lo que vemos que la suma anterior es igual a $$ \sum_{k=1}^{n} (-1)^{k+1}\binom{n}{k} (n-k)^n = \sum_{k=0}^{n-1} (-1)^{n-k+1} \binom{n}{k} k^n $$

Por último, consideramos el conjunto $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$

De nuestro trabajo anterior, podemos ver que su cardinalidad es $$\begin{gather} |S| - \left|A_1\cup A_2\cup A_3 \cup\cdots\cup A_n \right| = n^n - \sum_{k=0}^{n-1} (-1)^{n-k+1} \binom{n}{k} k^n \\ = n^n + \sum_{k=0}^{n-1} (-1)^{n-k} \binom{n}{k} k^n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n \end{gather}$$ que es la suma que nos proponemos evaluar. Queremos demostrar que es igual a $n!$ .

Ahora cualquier elemento del conjunto $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ debe contener todos los símbolos $a_1, a_2, a_3, \cdots, a_n$ ya que si no contiene $a_k$ para algunos $k$ entonces sería un elemento de $A_k$ y, por tanto, de $$ A_1\cup A_2\cup A_3\cup\cdots\cup A_n $$

A la inversa, cualquier cadena que contenga todos los símbolos $a_1, a_2, a_3, \cdots, a_n$ es un elemento de $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ ya que dicha cadena está en $S$ pero no en ninguno de los $A_k$ 's.

Vemos que $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ consiste precisamente en las permutaciones de los símbolos $a_1, a_2, a_3, \cdots, a_n$ y por tanto su cardinalidad es $n!$ . Así, hemos demostrado que $$ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n = n!$$ como se desee.

Answer 3

Buena observación. Esto viene de La serie de Newton aplicado a $f(x)=x^n$ .

Es el análogo discreto de $f^{(n)}(x)=n!$ .

Answer 4

Si he entendido bien, quieres la forma cerrada de la suma

$$S_n=\sum_{k=0}^{n}(-1)^{n-k}{n\choose k} k^n$$

Partimos de $$(1-x)^n=\sum_{k=0}^n (-1)^{k} {n \choose k} x^k$$ Reemplazamos $x$ por $\exp(t)$ :

$$(\exp(t)-1)^n=\sum_{k=0}^n (-1)^{n-k}{n \choose k}\exp(kt)$$ y diferenciamos $n$ tiempo con respecto a $t$ y ponemos $t=0$ .

Como $\displaystyle (\exp(t)-1)^n=t^n+t^{n+1}g_1(t)$ para alguna serie $g_1(t)$ obtenemos $\displaystyle (\frac{d}{dt})^n((\exp(t)-1)^n)=n!+tg_2(t)$ y poniendo $t=0$ obtenemos $n!$ . Ahora $$(\frac{d}{dt})^n(\sum_{k=0}^n (-1)^{n-k}{n \choose k}\exp(kt))=\sum_{k=0}^n (-1)^{n-k}{n \choose k}k^n\exp(kt)$$ y sustituyendo $t$ por $0$ da la fórmula.

Answer 5

La respuesta correcta a esto es sin duda la de Yves Daoust, pero aquí hay otra prueba combinatoria que creo que es más fácil que la de Dylan.

Así que, a modo de recordatorio, estamos tratando de mostrar que $\sum_k(-1)^{n-k}\binom{n}{k}k^n=n!$ . Así pues, interpretando el lado izquierdo de la forma más sencilla posible, consideremos configuraciones del tipo siguiente: tenemos una lista de $n$ enteros positivos, algunos de los cuales (llámese el número $k$ ) están escritas en negro y las otras en rojo, y todas son como máximo $k$ . Afirmamos que hay $n!$ más configuraciones de este tipo con un número par de puntos rojos que con un número impar de puntos rojos.

Que "a lo sumo $k$ La condición de "persona" es sugerente. En lugar de usar números, usemos algo más que tenemos $k$ de: las cosas negras de nuestra lista. Así que ahora nuestra configuración se ve así. Tenemos $n$ puntos en una fila, de color rojo o negro. Hay una flecha que va de cada punto a otro punto, y ese otro punto es siempre negro. Y afirmamos que hay $n!$ más configuraciones de este tipo con un número par que con un número impar de puntos rojos.

Hay un conjunto bastante natural de $n!$ configuraciones con un número par de puntos rojos, es decir, aquellas en las que todas las flechas tienen objetivos diferentes. (En este caso, cada punto es el objetivo de alguna flecha y, por tanto, hay no puntos rojos). Entonces, ¿podríamos emparejar todas las demás para que las configuraciones de cada par tengan una "paridad roja" diferente?

Sí, podemos. Elige cualquier configuración de flechas (sin importar el color) en la que algún punto no sea el objetivo de ninguna flecha. Tomemos, de hecho, el punto más a la izquierda. Emparejar cada configuración con la que se obtiene sólo cambiando el color de ese punto. Ya está hecho.

(Creo que hay un sentido en el que esto es equivalente a la prueba de Dylan, en realidad, pero creo que es más fácil de esta manera).