Determining the cardinality from set builder notation

Question

I am currently struggling with the following question :

Let S be defined as the following:
    S = {(A,B)| A ⊆ {1,2,....,n}, B ⊆ {1,2,....,n}, |A ∩ B| >= 1}
What is the cardinality of S? Justify your answer.

I am by no means looking for someone to give me the answer, rather I am looking for hints on how to even begin dissecting this question. For starters a translation of the definition of S in terms of english. I believe it says S is defined as a tuple of set A and B s.t A is a subset of positive integers 1 to n and the same with set B? Any hints would be greatly appreciated.

Answer 1

• How many choices are there for $A$ (if we ignore the other conditions)?
• How many for $B$?
• So how many choices for $(A,B)$ if we ignore the intersection condition?

Now the tricky idea:

• How many $(A,B)$ with $A,B\subseteq \{1,2,\ldots,n\}$ with $|A\cap B|=\emptyset$ are there?

Use these results to deduce the cardinality of $S$.

Hint for the "trick" part: consider maps $\{1,2,\ldots,n\}\to \{1,2,3\}$.

Answer 2

Assume that you have chosen a set $A\subset[n]$. This $A$ will have $r\in[0..n]$ elements. How many allowed choices are there for $B$?

Write $B$ in the form $B=B'\cup B''$ with $B':=B\cap A$ and $B'':=B\cap\complement A$. Then $B'$ and $B''$ can be chosen independently, and the number of choices only depends on $r$ and $n$.