Número de formas de elegir dos subconjuntos $P$ y $Q$ tal que $P\cap Q=\emptyset$

Question

Un conjunto $A$ tiene $n$ elementos. Un subconjunto de $P$ de $A$ se elige (con reemplazo) y otro subconjunto $Q$ es elegido. Encontrar el número de formas de elegir $P$ y $Q$ tal que $P\cap Q=\emptyset$

Si $n(P)=0$ número de subconjuntos $Q=^nC_0+^nC_1+\cdots +^nC_n=2^n$

Si $n(P)=1$ , entonces el número de subconjuntos $Q=^nC_0+^nC_1+\cdots +^nC_{n-1}$

Sumando todos los casos, el número de vías es $(n+1)\cdot^nC_0+n\cdot^nC_1+\cdots ^nC_n$

Pero la respuesta dada es $3^n$ .

(Ya he visto dos posts en SE respecto a la misma pregunta pero no este método. ¿Cuál es el error que estoy cometiendo?)

Answer 1

Para el caso $n(P)=1$ , deberías tener $${{n1}\choose 0}+{{n1}\choose 1}+\cdots+{{n1}\choose {n1}}=2^{n-1}$$ porque no se permite incluir ningún elemento de $P$ (de los cuales hay $1$ ) al elegir elementos para $Q$ . Así que, en general, cuando $n(P)=k$ el número de posibilidades de $Q$ es $${{n-k}\choose 0}+{{n-k}\choose 1}+\cdots+{{n-k}\choose{n-k}}=2^{n-k}$$ porque hay $k$ (los elementos de $P$ ) que debe excluir al elegir los elementos para $Q$ .

Ahora, cuando se suman todos los casos, no está claro de dónde salen las cifras. ¿Cómo se obtienen los coeficientes $n+1$ y $n$ ¿ y así sucesivamente? Debe sumar sobre todos los casos (que son disjuntos) el número de posibilidades de $P$ veces el número de posibilidades de $Q$ . Cuando $n(P)=k$ Hay $n \choose k$ posibilidades de lo que el conjunto $P$ es. Ya hemos calculado que hay $2^{n-k}$ posibilidades de $Q$ dado $P$ . Así que en total hay ${n\choose k}\cdot 2^{n-k}$ posibilidades de $P$ y $Q$ cuando $n(P)=k$ . Así que la respuesta es $$\sum_{k=0}^n{n\choose k}\cdot 2^{n-k}=3^k.$$ (Puedes utilizar el teorema del binomio para calcular esta suma).

Answer 2

Otros han hablado de su método; he aquí una forma diferente de verlo.

Dado un conjunto de tamaño $n$ Hay $2^n$ subconjuntos. Esto se debe a que podemos construir un subconjunto mediante, para cada elemento $x \in A$ , haciendo una elección independiente: o bien $x$ está en el subconjunto, o no lo está.

Así que hay una forma análoga de ver por qué $3^n$ es correcto para este problema -- para cada elemento de $A$ hay tres opciones: o está en $P$ , está en $Q$ o no está en ninguna de las dos.

Answer 3

Una manera fácil de pensar en el problema- Cada uno de los elementos del conjunto A tiene tres opciones: ir al conjunto P, ir al conjunto Q o no ir a ninguno. No puede entrar en ambos, ya que la intersección de P y Q es el conjunto nulo.

Por lo tanto 3^n maneras de formar subconjuntos P y Q

Answer 4

Entonces, cuando $n(P)=1$ tiene un número de subconjuntos $Q = { n-1 \choose {0}} + { n-1 \choose 1} + \dots + {n-1 \choose n-2} + { n-1 \choose n-1}$