2

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

Milind Hegde
  • 3,914
user1527227
  • 1,738
  • 7
  • 38
  • 60

3 Answers3

4

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\;.$$

Brian M. Scott
  • 616,228
  • @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 06:30
  • ... $\dfrac{n!}{k!(n-k)!}=\dbinom{n}k$. – Brian M. Scott Apr 18 '13 at 06: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
0

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

Milind Hegde
  • 3,914
0

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?

You want to sum $\binom{n}{k} $ for all values ${k} \to\ {n}$ the binomial equation can be written $\displaystyle\sum\limits_{k=0}^n \binom{n}{k} (x)^k (y)^{n-k} = (x+y)^n$ If you think about your question in terms of finding the sum

$\displaystyle\sum\limits_{k=0}^n \binom{n}{k}$ ~(The number of possible subsets)

you are actually just multiplying the sum by 1, in which case, $(x)^k (y)^{n-k}$ must always evaluate to 1 for each of iteration of the summation. this is true when the values of ${x},{y}$ equal 1 so you get $(1+1)^n=2^n$

mm8511
  • 871