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