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.

I'm reading my textbook on binomial theorem and there's an example question with the solution. I don't understand it. Can someone please explain? Thanks in advance.

How many subsets are there of a set consisting of n elements?

Solution: $\displaystyle\sum\limits_{k=0}^n \binom{n}{k} = (1 +1)^n = 2^n$

What does this have to do with the binomial theorem and where is the $x^k y^{n-k}$ terms?

http://en.wikipedia.org/wiki/Subset

share|improve this question

2 Answers 2

up vote 0 down vote accepted

Let $S$ be a set of $n$ objects; then the binomial coefficient $\binom{n}k$ is the number of $k$-element subsets of $S$. Thus, $\sum_{k=0}^n\binom{n}k$ is the number of subsets of $S$ of all possible sizes from $0$ through $n$.

The binomial theorem says that

$$(x+y)^n=\sum_{k=0}^n\binom{n}kx^ky^{n-k}\;;\tag{1}$$

if you substitute $x=y=1$ in $(1)$, you get

$$(1+1)^n=\sum_{k=0}^n\binom{n}k1^k\cdot1^{n-k}=\sum_{k=0}^n\binom{n}k\;.\tag{2}$$

And of course $(1+1)^n=2^n$, so $(2)$ reduces to

$$2^n=\sum_{k=0}^n\binom{n}k=\text{number of subsets of }S\;.$$

share|improve this answer
    
@user1527227: Sorry; that’s usually the first thing that one learns about the binomial coefficients, so I assumed that you already knew it. There are $n$ ways to choose one element from $S$. Once you’ve chosen that, there are $n-1$ ways to choose a second, different element. Keep going, and you’ll see that there are $$n(n-1)(n-2)\dots(n-k+1)=\frac{n!}{(n-k)!}$$ ways to choose a sequence of $k$ elements of $S$. Each set of $k$ elements can be chosen in $k!$ different sequences, so we’ve counted each set $k!$ times. To compensate, we must divide $\dfrac{n!}{(n-k)!}$ by $k!$, getting ... –  Brian M. Scott Apr 18 '13 at 6:30
    
... $\dfrac{n!}{k!(n-k)!}=\dbinom{n}k$. –  Brian M. Scott Apr 18 '13 at 6:30
    
Wow thank you for your response. I really appreciate it. Is this the proper way to think about it then? (n,k) is the number of unique sets by choosing k objects from n objects. So the sum of all (n,k) gives you the total number of unique sets. So since you know the solution must be of the form (n,k), you set x=y=1 and solve the binomial theorem for the formula? Is this the proper thinking? Thanks again Brian!! –  user1527227 Apr 18 '13 at 16:45
    
@user1527227: You’re welcome! Yes, you can always view $\binom{n}k$ as the number of $k$-element subsets of an $n$-element set. And in this problem you can look at the binomial theorem and see that if $x=y=1$, the $x^ky^{n-k}$ part of the summation boils down to $1$, so that you’re just adding binomial coefficients and therefore counting subsets of $S$ according to their sizes. –  Brian M. Scott Apr 18 '13 at 19:04

Also, you can see another way to get the RHS of your equation. Consider a subset. There are $n$ possible members, and each can either be in the subset, or not, i.e. there are 2 possibilities for each member.

Therefore the number of total possible subsets is $2*2*2...$ $n$ times = $2^n$.

share|improve this answer

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.