# Math Help - Cardinality

1. ## Cardinality

I'm stuck on this question:
Let A={1,2,3....,n}. What is the cardinality of the set:
{(a,S) : a $\in$S, S $\in$P(A)}.

I feel like its going to be related to 2^n, but i'm not sure. Could someone point me in the right direction?

2. Let $D = \left\{ {(a,S):a \in S \in \mathcal{P}(A)} \right\}$, then we are counting the number of ordered pairs in $D$.
There are $2^{n-1}$ subsets of $A$ that contain the number $1$.
So there are $2^{n-1}$ pairs in $D$ having $1$ as the first term.
Therefore, how many pairs are there in $D~?$

3. Why $2^{n-1}$? Surely it would be $2^n$?

4. No wait I see it now. So the answer should be $n{2^{n-1}}$?

5. You have it.

6. Awesome, thanks for the help!