Mostrando que $\sum\limits_{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$

Question

Estoy tratando de mostrar que $n! = \binom{n}{0}D_n + \binom{n}{1}D_{n-1}+...+\binom{n}{n-1}D_1 + \binom{n}{n}D_0$ donde $D_k$ es el número de alteraciones de $k$ objetos.

Sin embargo, el último paso de mi prueba requiere de mí para demostrar que

$\sum\limits_{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$.

Estoy completamente atascado aquí como estoy teniendo un tiempo difícil conceptualizar el doble de la suma. Sé que en el interior de la suma tiene un límite de $1 \over e$, y el uso de esa información, podríamos expresar el límite de lo que

${1 \over e} \sum\limits_{r=0}^\infty {1 \over r!}$.

Ahora también sé que el límite a la anterior $\sum\limits_{r=0}^\infty {1 \over r!} = e$.

Así que por mi sueltos ideas y argumentos sobre la prueba podría ser completos, ${1 \over e} \cdot e = 1$.

Pero, ¿cómo puedo poner estas ideas en una forma más matemática y forma sólida?

Answer 1

Con respecto a su identidad, $$ \ sum_ {r = 0} ^ n ({1 \ over r!} \ Sum_ {s = 0} ^ {nr} {(- 1) ^ s \ over s!}) = \ sum_ {r = 0} ^ n \ sum_ {s = 0} ^ {nr} {(- 1) ^ {s} \ binom {r + s} {r} \ over (r + s)!} \\ = \ sum_ {r = 0} ^ n \ sum_ {m = 0} ^ {n} {(- 1) ^ {mr} \ binom {m} {r} \ sobre m!} = \ sum_ {m = 0} ^ {n} {(- 1) ^ m \ sobre m!} \ sum_ {r = 0} ^ m (-1) ^ {r} \ binom {m} {r} = 1+ \ sum_ {m = 1 } ^ {n} {(- 1) ^ m \ sobre m!} (1-1) ^ m = 1. $$ Sin embargo, creo que su problema original sobre los desajustes se puede resolver de una manera más fácil.

Answer 2

El problema original$n! = \binom{n}{0}D_n + \binom{n}{1}D_{n-1}+...+\binom{n}{n-1}D_1 + \binom{n}{n}D_0$ se puede resolver notando que el número de permutaciones con exactamente k puntos fijos es$\binom{n}{k}D_{n-k}$.

Sin embargo, su identidad$\sum_\limits{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$ se puede probar de forma rutinaria al intercambiar el orden de la suma.

En realidad, utilizando su problema original y el método de la función de generación, uno puede derivar la fórmula explícita para el número de desajustes (la otra forma es usar la fórmula inclusiva-exclusiva)

Answer 3

Tienes que$\displaystyle \sum_{s=0}^k \frac{(-1)^s}{s!}$ es el coeficiente de$x^k$ en el producto de$\exp(-x)$ por$\displaystyle \frac{1}{1-x}$. Por lo tanto, su expresión es el coeficiente de$x^n$ en el producto de$\exp(x)$ por$\displaystyle \frac{\exp(-x)}{1-x}$, es decir, es el coeficiente de$x^n$ en$\displaystyle \frac{1}{1-x}$, por lo tanto igual a$1$.