Prueba de que $ \sum_ {k=1}^n(-1)^k(k-1)!{n \brace k} = 0$ en uso la interpretación combinatoria

Question

Prueba de que $$ \\\sum_ {k=1}^n(-1)^k(k-1)!{n \brace k} = 0 \\ $$ donde $n > 1$ . Sé cómo se puede hacer con los métodos algebraicos estándar:

Solución

$$ \begin {align*} \sum ^n_{k=1}(-1)^k(k-1)!{n \brace k} &= \sum ^n_{k=1}(-1)^k(k-1)! \left (k{n-1 \brace k} + {n-1 \brace k-1} \right ) = \\ &= \sum ^n_{k=1}(-1)^k k!{n-1 \brace k} + \sum ^n_{k=1}(-1)^k (k-1)!{n-1 \brace k-1} \end {align*} $$

Podemos describir ambas sumas: $$ \begin {align*} &=&&- 1!{n-1 \brace 1} + 2!{n-1 \brace 2} - 3!{n-1 \brace 3} + \dots + (-1)^{n-1}(n-1)!{n-1 \brace n-1} + (-1)^{n}n!{n-1 \brace n} + \\ &&&- 0!{n-1 \brace 0} + 1!{n-1 \brace 1} - 2!{n-1 \brace 2} - \dots + (-1)^{n-1}(n-2)!{n-1 \brace n-2} + (-1)^{n}(n-1)!{n-1 \brace n-1} \\ \end {align*} $$

Vemos que los elementos de ambas sumas se reducen para que podamos escribir eso como: $$ = -0!{n-1 \brace 0} + (-1)^{n} \cdot n! \cdot {n-1 \brace n} = 1 \cdot [n-1 = 0] + (-1)^{n} \cdot n! \cdot 0 = 0 + 0 = 0 $$
Pero estoy realmente interesado en la prueba combinatoria. Sé que debo encontrar la bijección entre los elementos pares e impares, pero no sé cómo se puede hacer.

Answer 1

Gracias por mostrar el método algebraico. Mi respuesta a continuación está inspirada en él / una interpretación de él, y no habría tenido éxito sin sus ecuaciones. :)

Deje que $[n] = \{1, 2, \dots , n\}$ ser la base.

• Por definición, ${n \brace k} = $ no. de las formas de partición $[n]$ en un conjunto de $k$ subconjuntos no vacíos.

• Así que $k! {n \brace k} = $ no. de las formas de partición $[n]$ en un secuencia de $k$ subconjuntos no vacíos. (Secuencia significa orden de la materia de los subconjuntos.)

• Más allá, $(k-1)! {n \brace k} = $ no. de las formas de partición $[n]$ en una secuencia de $k$ subconjuntos no emitentes, pero donde el subconjunto que contiene un elemento distinguido, lo llaman $1$ es el último. (Exigir que llegue al final significa que sólo puedes permutar el resto $(k-1)$ subconjuntos.)

Para la taquigrafía, defina un foobar de longitud $k$ para ser una forma de dividir $[n]$ en una secuencia de $k$ subconjuntos no vacíos, donde el subconjunto que contiene $1$ es la última. Así, $(k-1)! {n \brace k} =$ no. de foobares de longitud $k$ .

Ahora considera todos los foobares posibles, de cualquier longitud. Estos vienen en dos tipos: o bien el último subconjunto es el singleton $\{1\}$ o contiene algún otro elemento además de $1$ . Los dos tipos de foobares están en bijección:

$$ (S_1, S_2, \dots , S_k, \{1\}) \iff (S_1, S_2, \dots , S_k \cup \{1\}) $$

En cada uno de estos pares, un foobar tiene longitud de impar y el otro foobar tiene longitud uniforme. Por lo tanto, el número de foobares de longitud uniforme $=$ el no. de los foobares de longitud imperial, que es exactamente la fórmula que estamos tratando de probar. $ \square $

---

Por qué esta es una interpretación de su método algebraico: En su recurrencia ${n \brace k} = k {n-1 \brace k} + {n-1 \brace k-1}$ el segundo término cuenta los casos en los que $1$ es por sí mismo, y el primer término cuenta los casos en los que $1$ está en un subconjunto con otro elemento. Y entonces demostraste que este $2$ -La clasificación de las vías lleva a muchas cancelaciones, así que tuve que encontrar una bijección que se basara en esta clasificación.