Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:- http://books.google.co.in/books?id=cdFYMcmC-tcC&printsec=frontcover&dq=element+of+discrete+mathematics&hl=en&sa=X&ei=KKiiUPPfJoXMrQet-oH4Dw&ved=0CDcQ6AEwAA ( page 70, example 2.6 ).

share|improve this question
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
+1 Nice...and so close to 9K! ;-) –  amWhy Nov 13 '12 at 20:26
    
@amWhy Thanks!! –  EuYu Nov 13 '12 at 20:27
    
@EuYu: Thanks for the nice explanation! –  mag Apr 7 at 18:31
add comment

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.

share|improve this answer
add comment

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!

Regards Joe Tursi tamref@msn.com

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.