Finding the cardinality of $\{(a, S) \mid a ∈ S, S ∈ P(A)\}$ for $A =\{1, 2, 3, \cdots , n\}$.

Question

This is exercise 1.6a in Introductory Mathematics: Algebra And Analysis by G.C. Smith.

Let $A =\{1, 2, 3, \cdots , n\}$. What is the cardinality of $\{(a, S) \mid a ∈ S, S ∈ P(A)\}$?

The answer given is $n \cdot 2^{n - 1}$ since there are $n$ choices for $a$, and $2^{n-1}$ choices for $S$, since we can choose the set $S \setminus \{a\}$ in $2^{n - 1}$ ways.

I understand that the cardinality of $P(A)$ is $2^n$ and that there are that many possible $S$ sets, $2^n - 1$ if we exclude the empty set. The number of elements in each $S$ set ranges from $1$ to $n$, every set yields $k$ pairs which is the number of elements it contains. The number of sets containing $k$ elements is $\binom n k$. So I think the answer should be $$ 1 \cdot \binom n 1 + 2 \cdot \binom n 2 + \cdots + n \cdot \binom n n $$ which I think is correct. I just don't see how that is equal to $n \cdot 2^{n - 1}$.

If you could explain the reasoning behind the author's answer it would be appreciated as well.

Answer 1

So, to look at your summation, $$ \sum_{k=1}^n k \binom n k \stackrel ? = n \cdot 2^{n-1} $$ we can instead look at the more general equality $$ \sum_{k=0}^n \binom n k x^k = (1+x)^n $$ where this equality holds by the binomial theorem. If we differentiate both sides, we get $$ \sum_{k=1}^n k \binom n k x^{k-1} = n(1+x)^{n-1} $$ and then we let $x=1$ to get $$ \sum_{k=1}^n k \binom n k = n \cdot 2^{n-1} $$

---

The author's reasoning is quite simple. We need to find pairs $(a,S)$ such that $a \in S \subseteq A$.

If we fix a particular $a \in A$ (of which there are $n$ possible choices), we still need to figure out the sets $S$ we can associate with $a$. We know that $a$ must lie in $S$ (so we already know that $S \ne \varnothing$), but otherwise have no further restrictions. So, how many additional sets $S$ can we build from the $n-1$ remaining elements of $A \setminus \{a\}$? Well, that's just the cardinality of $P(A \setminus \{a\})$, i.e. $2^{n-1}$.

Hence, $n \cdot 2^{n-1}$ possible pairs.

Answer 2

Another way to see the cardinality $N$ is $n2^{n-1}$ from calculating that $N = \sum_{k=0}^n k\binom{n}{k}$ is to note that, if $k\geq 1$, then $$ k\binom{n}{k} = \frac{k.n!}{k!(n-k)!} = n.\frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}. $$

It follows that $$ N= \sum_{k=0}^n k\binom{n}{k} = \sum_{k=1}^n k\binom{n}{k} = \sum_{k-1=0}^{n-1} n\binom{n-1}{k-1} = n\sum_{l=0}^{n-1} \binom{n-1}{l} = n2^{n-1}. $$

It might be useful to note that the identity $n\binom{n-1}{k-1} = k\binom{n}{k}$ has a combinatorial proof which comes from the two different counting methods used by the OP and the text: Let us write $[n]$ for $\{1,2,\ldots,n\}$ and for any $k$, $1\leq k\leq n$, let $S_k = \{(a,S): a\in S\subseteq [n], |S|=k\}$, and $N_k = |S_k|$.

The two ways to count the set of pairs in $S_k$ are $$ N_k = \sum_{a\in [n]}\left(\sum_{S\subseteq [n], a\in S} 1\right) = \sum_{S \subseteq [n]} \left(\sum_{a\in S} 1\right) $$ that is, we can count how many pairs $(a,S)$ with $a=j$ for some $j \in [n]$ and then we obtain the total number of pairs by summing over all possible $j$, or we can count how many pairs $(a,S)$ have $S=S_0$, a given $k$-element set, and then sum over all possible $S_0$. The first approach gives $\binom{n-1}{k-1}$ $k$-element subsets contain a given element $j$, and hence $N_k = n\binom{n-1}{k-1}$, while for the second, clearly for a given $k$-element set there are $k$ choices for $a$, and hence one obtain $N_k = k\binom{n}{k}$.