Número de subconjuntos con un número par de elementos

Question

Dejar $|X|=n$. ¿Cómo encontrar todo el número de subconjuntos$X$ que consiste en un número par de elementos?

Answer 1

He aquí un rápido método combinatorio.

Si $n=0$, entonces claramente no es $1$ tal subconjunto, es decir, el conjunto vacío de sí mismo.

Si $n>0$, lista de los elementos de $X$ $$x_1, x_2, \dots, x_n$$ Un subconjunto $S \subseteq X$, con un número par de elementos está determinado por su intersección con la a $\{ x_1, \dots, x_{n-1} \}$: si la intersección tiene un número par de elementos, a continuación,$x_n \not \in S$, y si tiene un número impar de elementos, a continuación,$x_n \in S$.

Por tanto, el número de subconjuntos de a $X$ con un número de elementos es igual al número de subconjuntos de a $\{ x_1, \dots, x_{n-1} \}$, es decir,$2^{n-1}$.

---

Alternativamente, usted convencer de que el número de subconjuntos con un número par de elementos es $$\frac{1}{2} \left( \sum_{k=0}^n \binom{n}{k} + \sum_{k=0}^n (-1)^k \binom{n}{k} \right)$$ y aplicar el teorema del binomio.

Answer 2

Son en total $2^n$ subconjuntos de a $X$.

Si $n$ es impar, entonces existe una correspondencia uno a uno entre conjuntos, incluso con cardinalidad y conjuntos de cardinalidad impar. Subconjunto $S$ se corresponde con su complemento. Por consiguiente, el número de subconjuntos, incluso con cardinalidad es igual al número de subconjuntos con cardinalidad impar. Así que este número es $\frac122^n=2^{n-1}$.

Si $n$ es incluso, a continuación, poner un elemento $x_0\in X$ a un lado. Con el truco descrito anteriormente, encontramos que $X-\{x_0\}$ $2^{n-2}$ subconjuntos, incluso con cardinalidad y también a $2^{n-2}$ subconjuntos con cardinalidad impar. Los subconjuntos de a $X-{x_0}$ con cardinalidad impar convertido en subconjuntos $X$, incluso con cardinalidad si el elemento $x_0$ es añadido a cada uno de ellos. Esto nos da $2^{n-2}+2^{n-2}=2^{n-1}$ subconjuntos de a$X$, incluso con la cardinalidad.

Así que en ambos casos la respuesta es $2^{n-1}$.

Answer 3

Sugerencia

No es $\displaystyle\binom{n}{2k}$ diferentes conjuntos de tamaño $2k$$1 \leq k \leq n/2$.

Formular, a continuación, su resultado como una suma y de una simplificación.