Esto a partir de un ejercicio de Aigner del libro , donde uno tiene que evaluar $\sum_{k\ge 0} (-1)^k \binom{n}{k}^2$, usando el signo revertir involuciones. Al $n$ es impar, el problema es trivial : vamos a $[n] = \{1,2,\dots,n\}$ consideran todos los pares de subconjuntos $\{ (A,B) \in 2^{[n]} \times 2^{[n]} : |A| = |B| \}$, e $(A,B)$ tiene signo $(-1)^{|A|}$ y el signo-revertir la involución es $(A,B) \to ([n]-A,[n]-B)$. Consejos sobre cómo abordar este problema incluso para los $n$ será apreciado.
Respuesta
¿Demasiados anuncios?
Considerar el conjunto de pares $(A,B)$ de los subconjuntos de a $\{1,\ldots,n\}$ tal que $|A|+|B|=n$ peso $(-1)^{|A|}$. La excepcional parejas donde la involución no está definido son los donde $A=B$. El uno para el otro par de $(A,B)$ tomar el elemento más pequeño de la diferencia simétrica de a $A$ $B$ y pasa de un grupo a otro. La diferencia simétrica de los dos nuevos conjuntos es la misma, por lo que esta es una involución, y es peso de la inversión.
