Number of subsets of a set having r elements

Question

We have studied the standard way of ascertaining the total number of subsets of a set by using the concept of combinations ( or binomial coeffecients ). I came across an alternate derivation for this fact. The derivation goes as follows:-

Consider the problem of placing the $r$ elements of $A$ in two boxes. Corresponding to each placement, we can define a subset of $A$ by taking the elements placed in box 1 and discarding the elements placed in box 2. Since there are $2^r$ ways to place the $r$ elements, there are $2^r$ subsets of $A$.

My doubt is that, although I understand the line of logic behind this reasoning, but I think that this reason can also be given with 3,4,5 ( and so on ) number of boxes. All we have to do is to observe only one box and discard all the other. Where am I wrong?

Reference:- Elements of Discrete Mathematics, Liu ( page 70, example 2.6 ).

Answer 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.

Answer 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.

Answer 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!