2

Assume that $R$ is a set with $n$ elements. We know that the number of subsets of $R = 2^n$.

What does this statement have to do with the binomial coefficient?

David G. Stork
  • 29,774
Lama
  • 43

2 Answers2

3

There are $n$ subsets containing a single element. There are ${n \choose 2}$ subsets that contain two elements, ... and ${n \choose i}$ subsets that contain $i$ elements, where ${n \choose i} = {n! \over i!(n-i)!}$ is the binomial coefficient.

Add those up to find the total number of subsets:

$$\sum_{i=0}^n {n \choose i} = 2^n.$$

David G. Stork
  • 29,774
0

$(a+x)^n = \sum_{r=0}^{n}{C(n, r)a^rx^{n-r}}$

If $x = a$, then

=>$(a+a)^n = 2^na^n = \sum_{r=0}^{n}{C(n, r)a^n}$

=>$2^n = \sum_{r=0}^{n}{C(n, r)}$

ukh
  • 378
  • All true, but how does this relate to subsets of a finite-cardinality set, which is what the OP wanted to know? – amd Dec 20 '15 at 07:19
  • The OP asked to know relation between $2^n$ and binomial coefficient which is what I have shown above. – ukh Dec 20 '15 at 08:45
  • Not quite. He asked about the relationship between the number of subsets of a set, which happens to be $2^n$, and binomial coefficients. – amd Dec 20 '15 at 09:06
  • 1
    If he didn't understand the meaning of binomial coefficient in the first place then , C(n,k) gives the total number of ways of selecting k items from n elements which is the same as total ways to form a set of k elements. – ukh Dec 20 '15 at 09:08