0
$\begingroup$

$A = \{{1, ... , n\}}$
How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$ ?
I got to the conclusion that it must be $\sum\limits_{k=0}^{n}2^k$ because for each size of $C$ I'm looking for the size of all its subsets because each subset will be suitable to be $B$.
Is it correct and is there another way to calculate it without a sigma?

$\endgroup$
  • $\begingroup$ If you are the same Lisa who has posting other combinatorics problems on this site, you should merge your accounts since you will earn more reputation on this site and the privileges that accrue with your reputation. $\endgroup$ – N. F. Taussig Feb 1 '16 at 21:40
1
$\begingroup$

Your conclusion that $B$ is a subset of set $C$ is correct. For each subset $C$ of size $k$, there are $2^k$ subsets. However, you forgot to take into account that there are $\binom{n}{k}$ subsets of size $k$ in set $A$. Hence, the number of order pairs $(B, C) \in \mathcal{P}(A) \times \mathcal{P}(A)$ such that $B \cap \overline{C} = \emptyset$ is $$\sum_{k = 0}^{n} \binom{n}{k}2^k = \sum_{k = 0}^{n} \binom{n}{k}2^k1^{n - k} = (2 + 1)^n = 3^n$$ by the Binomial Theorem.

Alternate Solution: Observe that each of the $n$ elements in $A$ is in $B$, $C \backslash B$, or $\overline{C}$. Thus, there are $3^n$ ordered pairs $(B, C) \in \mathcal{P}(A) \times \mathcal{P}(A)$ such that $B \cap \overline{C} = \emptyset$.

$\endgroup$
  • $\begingroup$ Thanks (: That's amazing! By $C - B$ you mean $C$ \ $B$ ? $\endgroup$ – Lisa Feb 1 '16 at 21:38
  • $\begingroup$ That is what I meant by $C - B$, but I changed the notation to conform to the form you prefer. $\endgroup$ – N. F. Taussig Feb 1 '16 at 21:43
0
$\begingroup$

The condition $B \cap \overline{C} = \emptyset$ tells you that $B$ must be a subset of $C$. So consider all possible sets $C$, and for each $C$ consider all of its possible subsets.

You'll get a more complicated sum as follows: $\Sigma_{k=0}^{n} \binom{n}{k} 2^k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.