suma de términos de la cardinalidad todos los posibles subconjuntos de un conjunto dado

Question

Que estoy enfrentando el problema de computar la suma $$\sum_{L\subset S}(-1)^{|S|-|L|},$ $ donde $|S|$ denota la cardinalidad de un conjunto de $S$ es finita y $L$ es un subconjunto apropiado de $S$. ¡Gracias!

Answer 1

Dado que el cardinallity ${L\subset S: |L| = j}$ es $\binom{|S|}{j}$, tenemos: $$\sum{L\subsetneq S}(-1)^{|S|-|L|} = \sum{j=0}^{|S|-1}\sum{L\subset S,\|L|=j}(-1)^{|S|-|L|} = \ = \sum{j=0}^{|S| - 1}\binom{|S|}{j}(-1)^{|S|-j} $ $

¿Esto parece familiar?

Answer 2

Encontrar un subconjunto de $|S|$ $|L|$ de la cardinalidad es igual que encontrar un subconjunto de cardinalidad $|S|-|L|$ solo tenemos que escribir la suma como $$\sum_{L\subset S}(-1)^{|L|}.$ $ ahora, hay exactamente ${|S|}\choose{|L|}$ subconjunto de tamaño $|L|$ $S$. Así que la suma se convierte en %#% $ de #% utilizando la fórmula binomial del neutonio.