Exactamente la mitad de los elementos de $\mathcal{P}(A)$ son de tamaño impar

Question

Que $A$ ser un conjunto no vacío y el número de elementos en $n$, es decir, $A$ $n:=|A|$.

Sé que el número de elementos del conjunto potencia de $A$ $2^n$, es decir $|\mathcal{P}(A)|=2^n$.

Me encontré con el hecho de que exactamente la mitad de los elementos de $\mathcal{P}(A)$ contienen un número impar de elementos y la mitad de ellos un número par de elementos.

¿Alguien puede probar esto? ¿O indirecta en una prueba?

Answer 1

Fijar un elemento $a\in A$ (este es el punto donde es necesario $A\ne\emptyset$). Entonces $$S\mapsto S\operatorname{\Delta}\{a\}$ $ (diferencia simétrica) es una biyección del conjunto de subconjuntos impares para el conjunto de subconjuntos incluso.

Answer 2

Sugerencia: se puede demostrar esto por inducción sobre el tamaño de $A$. Supongo que era cierto para conjuntos de tamaño $n$ y deje $A=\{a_1,\ldots,a_{n+1}\}$. A continuación, cada subconjunto de $A$ es un subconjunto de a $\{a_1,\ldots,a_n\}$ o es una copia de dicho subconjunto con la adición de $\{a_{n+1}\}$. El uso de la inducción de la hipótesis a la conclusión de que los conjuntos que no se contienen a $a_{n+1}$ tienen esta propiedad (con respecto a $\{a_1,\ldots,a_n\}$, agregando $a_{n+1}$ enviar exactamente el mismo número impar de conjuntos, incluso el tamaño de los conjuntos, y viceversa; por lo tanto, la relación sigue siendo cierto para $A$.

Answer 3

Para $n\in\Bbb Z^+$ deje $[n]=\{1,2,\dots,n\}$. Claramente $[1]$ tiene uno, incluso subconjunto y uno impar subconjunto. Supongamos que $[n]$ tiene el mismo número de pares e impares subconjuntos para algunos $n\in\Bbb Z^+$. Incluso los subconjuntos de a $[n+1]$ son de dos tipos:

• incluso los subconjuntos de a $[n]$; y
• los conjuntos de la forma $A\cup\{n+1\}$ donde $A$ es una extraña subconjunto de $[n]$.

Por la hipótesis de inducción hay el mismo número de series del segundo tipo, ya que hay de la primera, por lo $[n+1]$ tiene dos veces como muchos subconjuntos como $[n]$. Pero $[n+1]$ también tiene dos veces la cantidad de subconjuntos en total como $[n]$, por lo que debe tener el doble número impar subconjuntos así, lo que claramente implica que tiene igual número de pares e impares subconjuntos.

Answer 4

Al $n$ es impar, mira a cada conjunto y su complemento: uno tendrá un número de elementos y el otro, el extraño (porque el número impar sólo puede ser escrita como una suma de un extraño y un número par).

Al $n$ es incluso, eliminar un elemento para obtener un conjunto con un número impar de elementos. Por la primera parte, la mitad de sus subconjuntos incluso han cardinalidad y la mitad impar. Ahora para formar el total $\mathcal P(A)$, necesitamos unir la remainin elemento a cada uno de los anteriores subgrupos: aquellos con cardinalidad impar con convertirse incluso, y viceversa.

Answer 5

Supongamos que $n=|A|$. Entonces hay % $ $$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}=2^{n-1}$establece con cardinalidad aún. Por lo tanto, hay exactamente la mitad de los conjuntos con un número par de elementos.