Cardinality of the set $\{(A,B)\in \mathcal{P}(E)^{2} \mid A\cup B=E \}$

Question

let $E$ be a finite set with $|E|=n$ elements.

• what is the cardinality of set $\mathcal{E}=\{(A,B)\in \mathcal{P}(E)^{2} \mid A\cup B=E \}$

My proof:

note that $A\cup B=E \iff A^{c}\subset B $ $$|\mathcal{E}|= | \{ (A,B)\in\mathcal{P}(E)^{2} \ / \ A^{c} \subset B \} |$$

Let for every $(A^{c},B)$ the function $f: E \to \{0,1,2\}$ be defined via : $$f(x)= \begin{cases} 0 & \mbox{ if } \quad x\in A^{c} \\ & \\ 1 & \mbox{ if } \quad x\in B\backslash A^{c} \\ & \\ 2 & \mbox{ if } \quad x\in E\backslash B \end{cases} $$

This construction induces a bijection between $\mathcal{E}$ and $\{0,1,2\}^E$ via : $$\begin{array}{ccccc} \mathcal{T} & : & \mathcal{E} & \to & \{0,1,2\}^E \\ & & (A^{c},B) & \mapsto & f \\ \end{array}$$

and therefore yields $|\mathcal{E}| = |\{0,1,2\}^E| = (2 + 1)^n=3^n$

• Is my proof correct. I'm interested in more ways of prove it

Answer 1

Your proof looks basically correct, but it has some weaknesses.

You use the "complement" notation $A^c$ but never state your universal set. (You seem to imply that it is $E$.) For that and other reasons you should avoid the complement and stick to set difference.

Your notation for the value $f(x)=1$ is unnecessarily complicated. Why not just use $A\cap B$? That would go well with $E\setminus B$ for $0$ and $E\setminus A$ for $2$.

I agree with @BenMillwood's comment that you should show more detail that your construction makes a bijection.

Answer 2

Pick $A$ first. If $A$ has $k$ elements (there are $\binom{n}{k}$ ways to choose these), then we must pick all $n-k$ elements in $B$, so there are $2^k$ many choices of complementary sets (namely all subsets of $A$ can be added to the compulsory elements of $B$). So we have $\sum_{k=0}^n \binom{n}{k} 2^k$ many choices, which amounts to $3^n$ by Newton's binomial formula (expand $(1+x)^n$ with $x=2$).