Number of subsets of a set having r elements

Solution 1:

You are confusing some things here. The argument given is the total number of subsets for a set of $n$ elements. Combinations, on the other hand, count the number of subsets of a given size.

For example, consider the set $\{1,\ 2,\ 3\}$. There are $2^3=8$ total subsets (of all sizes), which are $$\left\{\emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,\ 2\},\ \{1,\ 3\},\ \{2,\ 3\},\ \{1,\ 2,\ 3\}\right\}$$ The subsets are symmetric in inclusion/exclusion (and this is why you only have two boxes: the first box represents inclusion and the second exclusion), for example the set $\{2\}$ has a complement, namely $\{1,\ 3\}$ where the first set is obtained by keeping $2$ while the second set is obtained by throwing away $2$.

Combinations count the subsets of a particular size ($n$ choose $r$ counts the number of $r$-element subsets of an $n$-element set). In our running example consider how many subsets of size $2$ there are: $$\left\{\{1,\ 2\},\ \{1,\ 3\},\ \{2,\ 3\}\right\}$$ for a total of $\binom{3}{2}$. The symmetry noted from before is also reflected in the fact that the binomial coefficients are symmetric $$\binom{n}{r} = \binom{n}{n-r}$$ which represents the fact that for every $r$-element subset that you keep, there's corresponding $n-r$-element subset that you've thrown away.

Of course the two concepts are intimately related. The total number of subsets is the sum of the number of subsets of every size. $$2^n = \sum_{r=0}^n\binom{n}{r}$$ This is in essense what the familiar binomial theorem states.

Solution 2:

You would be double counting. For example, both of these arrangements correspond to the same subset:

• $\{a,b\},\{c,d\},\{\}$
• $\{a,b\},\{c\},\{d\}$

The reasoning in the book requires having a bijection between the set of subsets and the set of placements into 2 boxes.

Solution 3:

I think you would agree this is an elgant proof that the the number of subset in any set in $2^n$. The coefficients of the binomial expansion are precisely the ways of chosing $r$ elements from a set of $n$ elements. Of course $r$ is less than or equal to $n$. But this is precisely the definition of a subset. Write out the binomial expansion and note that the coefficients are independant of $a$ and $b$. They are the same whatever the choices are for $a$ and $b$.

So set $a=1=b$. Bingo! All the products are the same, namely $1$, leaving simply the coefficients of each term multiplied by $1$. On the left of the expansion $$(a+b)^n=(1+1)^n=2^n.$$ Done!