Finding the Cardinality of a Cartesian Product 
Problem: $$A=\{ 1,2,3, \dots, n \}$$ $$\text{ Find the Cardinality of ... } $$$$\{(a,S) | a \in S, S \in P(A)\}$$

So the way I've approached this problem thus far was to find the cardinality of $S$ and then multiply it by the cardinality of $a$. If I'm not mistaken the cardinality of $S$ should be $2^n-1$ as $S$ cannot be an element of itself and the cardinality of $P(A)$ is $2^n$. However, I'm having difficulty finding the cardinality of $a$. Is it just n? And if so, why is that? 
 A: As $S$ is a subset of $A$, $a\in S$ is an element of $A$, and consequently talking about its cardinality doesn't make much sense. I'll provide some hints only since this might be a homework question. Let $T$ be the set about whose cardinality you inquire.

Example: Let's fix $n:=3$ for now. Then
$$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},A\}.$$
In this case we have
$$T=\{(1,\{1\}),(2,\{2\}),(3,\{3\}),(1,\{1,2\}),(2,\{1,2\}),(1,\{1,3\}),(3,\{1,3\}),(2,\{2,3\}),(3,\{2,3\}),(1,A),(2,A),(3,A)\}$$
and consequently $\operatorname{card}(T)={3\choose 1}+2{3\choose 2}+3{3\choose 3}=12$.

Hint: Observe that in the example above I listed the elements of $T$ using a somewhat natural ordering of its elements. First I ordered the nonempty subsets of $A$ (which are the nontrivial elements of the power set of $A$) according to their cardinality, and then I used the natural ordering of the natural numbers to order the pairs $(a,S)$ (for fixed $S$). In terms of cardinalities, then, computing the cardinality of $T$ is nothing but counting the cardinality of the power set of $A$, except one should use the cardinality of each subset as a weight, so that a subset of $A$ with $k$ elements should contribute not $1$ but $k$ to the total count.

Hint 2: Continuing from the previous hint, there are (at least) two ways to give an answer. Either you can generalize the formula for $n=3$ and show that it is correct for arbitrary $n$ using induction, or you can try to write $T$ as a disjoint union of sets whose cardinalities are much easier to compute. Following the ordering used above, a nonzero subset of $A$ can have at least $1$ element and at most $n$ elements. But how many subsets of $A$ are there containing $k$ elements, for $1\leq k\leq n$?

As a further exercise, it might be instructive also to think about what happens when $A:=\Bbb{N}$.
