¿Cuántos$S\subseteq\mathcal{P}(A)$ contienen cada elemento de$A$ un número par de veces?

Question

Deje $A=\{1,2,...,n\}$. Deje que el powerset de $A$ ser $\mathcal{P}(A)$.

Llamamos a $S\subseteq \mathcal{P}(A)$ un emparejado de la familia de subconjuntos de si $\forall a\in A$, el número de elementos de a$S$ que contengan $a$ es incluso.

Para $|A|=n$, ¿cuántas $S\subseteq \mathcal{P}(A)$ están vinculados?

Answer 1

La respuesta es $2^{2^n-n}$.

Te voy a dar dos (moralmente el mismo) de las pruebas.

Prueba Usando Álgebra Lineal

La identificación de subconjuntos con indicador de funciones, podemos ver todos los $\mathcal{S}\subseteq\mathcal{P}(A)$ como un elemento de la $\mathbb{F}_2$-vectorspace $(\mathbb{F}_2)^{\mathcal{P}(A)}$. Para cada una de las $a\in A$, definir un $\mathbb{F}_2$-lineal mapa de $p_a\colon (\mathbb{F}_2)^{\mathcal{P}(A)}\to\mathbb{F}_2$por $$S\in\mathcal{P}(A)\mapsto \begin{cases}1 & a\in S\\0 & a\notin S\end{cases}$$ por lo $p_a$ es el recuento si $a$ aparece en número par o impar de elementos $S\in\mathcal{S}\subseteq\mathcal{P}(A)$ (exactamente como en la condición de los pares de las familias). Así que contando vinculados a las familias se convierte en un problema de conteo de elementos en el núcleo común de todos los $p_a$'s.

El conjunto $\{p_a\mid a\in A\}$ es linealmente independiente (fácil de comprobar), por lo tanto, hay $n$ linealmente independientes de las condiciones que se ponga en $(\mathbb{F}_2)^{\mathcal{P}(A)}$. Para el común de kernel tiene dimensión $\lvert\mathcal{P}(A)\rvert-n=2^n-n$ sobre $\mathbb{F}_2$, lo $2^{2^n-n}$ vinculado a las familias.

Prueba Usando El Simple Conteo/Probabilidad

Sin pérdida de generalidad, vamos a $A=\{1,2,3,\dots,n\}$. Supongamos que hacemos la pregunta: ¿Cuál es la proporción de familias que contendrá $1$ número par de veces? Podemos argumentar que la respuesta es la mitad por la siguiente observación: en parejas los elementos de $\mathcal{PP}(A)$ como $\mathcal{S},\mathcal{S}\triangle\{\{1\}\}$, es decir, los pares de ponerse de acuerdo sobre todos los subconjuntos de a$A$ excepto el singleton $\{1\}$. Exactamente un miembro de cada par contendrá $1$ número par de veces.

Continuando con este argumento para $2$, exactamente uno de cada $$\mathcal{S},\mathcal{S}\triangle\{\{2\}\}$$ tendrá incluso número de $2$'s. Por otra parte, esto es independiente de que el número de $1$s, así que una cuarta parte de las familias tienen tanto en número de $1$'s y $2$'s.

Repita el procedimiento para $3,\dots,n$ por lo tanto nos da la probabilidad de cada elemento de $1,2,\dots,n$ apareciendo incluso el número de veces que es $2^{-n}$, porque tenemos $\{1\},\{2\},\dots,\{n\}$ todos pueden aparecer (o no) de manera independiente.

Por lo que el número total de pares de familias es $2^{-n}\cdot\lvert\mathcal{PP}(A)\rvert=2^{2^n-n}$.