Utiliza el método "raro" para explicar por qué las cantidades de subconjuntos con elementos pares/Impares son iguales.

Question

Me dieron esta identidad para $n > 0$ , $$\sum_{k=0}^{n} (-1)^k {n \choose k} = 0$$

Tengo que explicar por qué, utilizando el método "raro", hay exactamente tantos subconjuntos con un número par de elementos como subconjuntos con un número impar de elementos, y luego dar una prueba combinatoria de la identidad.

Estoy atascado en la puesta en marcha del método "raro". ¿Alguien puede poner en marcha el uso de este método?

Answer 1

He buscado en Google. Según tengo entendido, utilizar el método del "bicho raro" significa que elegimos un elemento específico, "el bicho raro", y hacemos un seguimiento de dónde va. Por lo tanto, dejemos que $x \in U_n$ ser raro, donde $U_n$ representa cualquier conjunto de $n$ elementos. Sea $E_n$ sea el número de subconjuntos pares de $U_n$ y $O_n$ sea el número de particiones de tamaño impar de $U_n$ .

Primero considere $E_n$ . Podemos elegir todos los subconjuntos de tamaño impar de $U_n - \{x\}$ (de tamaño $n-1$ ) y añadir el elemento $x$ o podemos elegir todos los subconjuntos de tamaño par que no incluyan $x$ (de tamaño $n-1$ ). Por lo tanto, $E_n = O_{n-1} + E_{n-1}$

Entonces considere $O_n$ . Del mismo modo, podemos elegir todos los subconjuntos pares de $U_n - \{x\}$ (de tamaño $n-1$ ) y añadir el elemento $x$ o podemos elegir todos los subconjuntos de impar que no incluyan $x$ (de tamaño $n-1$ ). Por lo tanto, $O_n = E_{n-1} + O_{n-1}$ .

Así, $E_n = O_n$ .

En cuanto a la identidad, observe que $E_n = \sum_{k = 0, k \ \mathrm{even}}^{n}{n \choose k}$ y $O_n = \sum_{k=1, k \ \mathrm{odd}}^{n} {n \choose k}$ y utilizar $E_n = O_n$ .

Answer 2

Bueno, conozco un método extraño para probar esto. Dejemos que $V$ sea un espacio vectorial de dimensión finita de dimensión $1$ sobre un campo $k$ , con generador $e_1$ . Se puede formar el complejo $0\to S(V)\to S(V)\to 0$ donde $S(V)$ es el álgebra simétrica en $V$ y la única flecha no nula es la multiplicación por $e_1$ . Este es un $S(V)$ -resolución libre de la trivial $S(V)$ módulo, $V$ . Llama a este complejo $C$ . Las fórmulas de Künneth muestran que el $n$ -producto tensorial doble de complejos $C(n)=C\otimes \cdots \otimes C$ tiene homología trivial en grados positivos y homología $k$ en grado cero. Esto significa que el complejo aumentado $C(n)\to k\to 0$ es acíclico. Pero $\dim_k C(n)_j = \binom nj$ y como la característica de Euler de un complejo es igual a la característica de Euler de su homología, obtenemos $$0=\sum (-1)^j \dim_k C(n)_j = \sum(-1)^j \binom nj$$

Answer 3

Si $n$ es impar, entonces {conjuntos de tamaño $m$ } y {conjuntos de tamaño $n-m$ } biyecto por el mapa "tomar el complemento".

Si $n$ es par, considere el conjunto con un elemento eliminado en su lugar. Los subconjuntos de $[n] = \{1, 2, \dots, n \}$ son precisamente los subconjuntos de $[n-1]$ junto con los subconjuntos de $[n-1]$ cada uno con $n$ adyacentes; entre los primeros, even e impar biyectan (por el primer caso), mientras que entre los segundos, even e impar biyectan igualmente. Por lo tanto, se biparticipan cuando ambos se combinan.