¿Cuántas formas hay de elegir 3 subconjuntos A, B, C de un conjunto {1,2,3 ... n} de manera que$ A \cap B \cap C = \emptyset $

Question

Creo que esta es una muy simple pregunta en términos de la combinatoria.

Suponiendo que tenemos el siguiente conjunto $\{ {1,2,3...n} \}$

De cuántas maneras podemos escoger 3 subgrupos (a,B,C) tal que la intersección entre todos ellos está vacío?

$ A \cap B \cap C = \emptyset $

Bueno, lo que tengo hasta ahora es la siguiente:

Para nosotros ha $ 2^n $ opciones (donde n es el tamaño del conjunto) Entonces, para B, el resto de las opciones son exactamente $ 2^{n-|A|} $ ya que podemos elegir sólo de los subconjuntos que no tiene elementos en común con A. Y, finalmente, C, dado que ya tenemos una intersección vacía, podemos elegir cualquier subconjunto queremos y conseguir el resultado esperado $ \emptyset $.

Pero por alguna razón se siente como los números son demasiado grandes. Si tomamos, por ejemplo, el conjunto {1,2}, entonces, según mi "fórmula", el número de opciones debe ser:

$ \binom{4}{1} * \binom{2}{1} * \binom{2}{1} = \frac{4!}{3!} * \frac{2!}{1!} * \frac{2!}{1!} = 16 $

¿Tiene sentido?

Answer 1

Piénsalo de esta manera: para cada $i\in\{1,\cdots,n\}$, $i$ puede ser en la mayoría de los dos conjuntos. Por lo tanto, $i$ podría estar en ninguno de los conjuntos, $i$ podría ser exactamente de uno de $A$, $B$, o $C$ o $i$ podría ser exactamente dos de $A$, $B$, y $C$. Esto le da a $7$ situaciones posibles para cada una de las $i$. Desde la establece para cada una de las $i$ puede ser elegido de forma independiente, esto da $7^n$ maneras de definir $A$, $B$, y $C$.

Esto funciona para $n=1$. En este caso, son:

• $A=B=C=\emptyset$.

• ( $A=\{1\}$ $B=C=\emptyset$ ) o ( $B=\{1\}$ $A=C=\emptyset$ ) o ( $C=\{1\}$ $A=B=\emptyset$)

• ( $A=B=\{1\}$ $C=\emptyset$ ) o ( $A=C=\{1\}$ $B=\emptyset$ ) o ( $B=C=\{1\}$ $A=\emptyset$)

Answer 2

Para cada$x\in\{ {1,2,3...n} \}$ hay 4 opciones:$$x\in A\ strong \ or\ x\in b\ strong \ or\ x\in C strong \ or\ x\notin A\bigcup B \bigcup C$ $ y todas las opciones similares le dan$A,B,C$ como desee. Entonces el número de opciones es$4^n$.