How many ordered pairs (with limitations)?

Question

having hard time with the following question: $$A = \{1,2,.....,n\}$$ How many ordered pairs $(B,C)$ which are members of $P(A) \times P(A)$ are there where $B\cap \overline{C}$ is the empty set?

Answer 1

The condition says that $B$ is a subset of $C$. So the number of ordered pairs is the number of ways to express the set $A$ as the union of three pairwise disjoint sets, namely $B$, $C\setminus B$, and $A\setminus C$.

The number of ways to do this is the number of functions from $A$ to a three-element set $\{x,y,z\}$. There are $3^n$ such functions, so there are $3^n$ ordered pairs $(B,C)$ satisfying the condition.

Answer 2

Consider $(B,C) \in P(A) \times P(A)$ such that $B \cap \bar{C} = \emptyset$. $B$ can have up to $n$ elements, so let us consider the case where $|B| = k$ for some $k \in [n].$ There are $\binom{n}{k}$ ways to construct $B$. $\bar{C}$ must have all of its elements not in $B$, so $C$ must contain $B$. Hence, $C$ can contain any amount of elements $b \geq k$. Given that $B$ is now fixed, we must select $b-k$ elements from the $n-k$ left. This can be done $\binom{n-k}{b-k}$ ways. Hence, the solution is

$$\sum_{k=0}^n \sum_{b=k}^n \binom{n}{k}\binom{n-k}{b-k}.$$