Ordered pairs in set-builder notation. I have a problem which is probably quite basic, as I've only just begun studying Set Theory, but I can't wrap my head around it, and need help. The problem is as follows:
$$A = \{1, 2, 3,..., n\}$$
Find the cardinality of the following:
$$\{ (a,S) : a \in S, S \in \mathcal P(A) \}$$
As I understand it, all elements of $\mathcal P(A)$ are sets, including the empty set, and all elements of $S$ will be natural numbers, ranging from $1$ to $n$. So, I (think) I understand that there are $n$ ways to choose $a$; selecting $a$ from any set $S$, there are a maximum of $n$ options. (Please correct if mistaken.)
However, the solution given says there are $2^{n-1}$ ways to select $S$, such that $S \setminus \{a\}$. I don't understand this. I thought this set would give a large set containing subsets of pairs, of the sort (for example) $\{ 1, \{1\} \}$, if $a = 1$ and $S = \{1\}$, or $\{ n, \{1,2,3,4\} \}$, if $a = n$, and $S = \{1,2,3,4\}$, and so on, so no subset will contain duplicates. I don't understand why $S \setminus \{a\}$ is relevant. Please help! The book I'm using gives the cardinality as $n2^{n-1}$, but is not very detailed, and I can't see what's going on. Thank you.
 A: 
"all elements of $\mathcal P(A)$ are sets". 

Yes; but they are the subsets of $A$. If $A$ has $n$ elements, then $\mathcal P(A)$ has $2^n$ elements, "starting" from $\emptyset$ up to $A$ itself.
Consider the simple example with $n=3$, i.e. $A= \{ 1,2,3 \}$.
We have that $\mathcal P(A)$ has $2^3=8$ elements: 

$\mathcal P(A) = \{ \emptyset,\{ 1 \}, \{ 2 \}, \{ 3 \}, \{ 1,2 \}, \{ 1,3 \}, \{ 2,3 \}, \{ 1,2,3 \} \}$.

Thus, for $a=1$ we have that:

$\{ (1,S): S ∈ \mathcal P(A) \} = \{ (1,\emptyset),(1,\{ 1 \}),(1,\{ 2 \}),(1,\{ 3 \}),(1,\{ 1,2 \}),(1,\{ 1,3 \}),(1, \{ 2,3 \}),(1,\{ 1,2,3 \}) \}$ 

i.e. again $8$ elements. 
The same for $a=2$ and $a=3$. Conclusion: $24=3 \times 8= n \times 2^n$.

But the definition is slightly more complicated:

$\{ (a,S) : a∈S, S∈ \mathcal P(A) \}$.

We have to pick-up pairs $(a,S)$ such that $a \in S$: this excludes of course the possibility $S=\emptyset$. But other cases must be excluded as well.
As we can verify in the simplified example, with $a=1$ we have only four pairs with $1 \in S, S \in \mathcal P(A)$.
And we have $4=2^2=2^{n-1}$ for our example with $n=3$.
We have again $3$ possible choices for $a$, and thus - in this case - we have $n \times 2^{n−1}$ pairs. 

Some more calculations ...
Why in general, for fixed $a$, we have $2^{n-1}$ elements $S \in \mathcal P(A)$ such that $a \in S$ ?
With $n$ elements we have that $\mathcal P(A)$ has $2^n$ elements.
If we remove $a$, the set left $A'=A \setminus \{ a \}$ has $n-1$ elements; thus $\mathcal P(A')$ has $2^{n-1}$ elements.
The subsets of $A$ are all the subsets of $A'$ "plus" the subsets obtained from the previous ones "adding" $a$.
This is shown by the fact that: $2^n=2 \times 2^{n-1}=2^{n-1}+2^{n-1}$.
In conclusion, the subsets of $A$, i.e. the elements of $\mathcal P(A)$ are $2^{n-1}$ subsets with $a$ inside plus $2^{n-1}$ subsets without $a$ [see again the simplified example].
This gives us the fact that, for fixed $a$, the number of pairs $(a,S)$ such that $a \in S$ are $2^{n-1}$.
A: For every fixed $a \in S$, there are $2^{n-1}$ subsets of $S$ that contain $a$, namely as much as all subsets of $A\setminus\{a\}$ (we just add $a$ to it, and clearly every $S$ with $a \in S$ can be written as $S = \{a\} \cup (S\setminus\{a\})$ (and $S\setminus\{a\}$ is a subset of $A \setminus \{a\})$ so $S \to S\setminus \{a\}$ is a bijection between $\{S \subseteq A: s \in A\}$ and $\mathcal{P}(A \setminus \{a\})$.
As there are $n$ choices for $a$ we get that this set has $n2^{n-1}$ elements.
A: Another way to get the same result:
First you select $a$. There are $n$ possibilities for that.
Then you have to select an $S\subseteq A$ such that $a\in S$. It is a given that $a$ must be there, but for each of the $n-1$ other elements of $A$, you have a choice of either including it in $S$ or not. So there are $n-1$ choices with $2$ possibilities. By the principle of multiplication, this gives
$$ n \cdot \underbrace{2 \cdot 2 \cdots 2}_{n-1\text{ twos}} = n 2^{n-1} $$
valid $(a,S)$ pairs.
