3
$\begingroup$

There is a set with $n$ elements. Why is the maximum number of subsets that can be formed out of it $2^n$?

$\endgroup$
2
  • 9
    $\begingroup$ For every element of the set, you have two choices, whether it's in the subset or not. $\endgroup$ Nov 12, 2013 at 13:22
  • $\begingroup$ @BrianM.Scott no, the n refers to the superset. $\endgroup$ Nov 12, 2013 at 13:24

4 Answers 4

9
$\begingroup$

We must show that $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$$ is the number of subsets of an $n$-element set $S$ where $n\geq0$.

Every subset of $S$ is a $k$-subset of $S$ where $k=0,1,2,...,n$. We know that ${n\choose k}$ equals the number of $k$-subsets of S. Thus by the Addition Principle $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}$$ equals the number of subsets to the set $S$. We can count the same thing by observing that each element of the set $S$ has two choices, either they are in a subset or they are not in a subset. Let $S=\{x_1,x_2,x_3,...,x_n\}$. So, $x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,..., $x_n$ is either in a subset or it is not in a subset. Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$. Hence ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$.

Another approach is to consider the Binomial Theorem $$(x+y)^n=\sum_{k=0}^n {n\choose k}x^{n-k}y^k.$$ Letting $x=1$ and $y=1$ we obtain$$2^n=\sum_{k=0}^n{n\choose k}.$$

$\endgroup$
1
  • 2
    $\begingroup$ This (and some other answers) is a very roundabout way to get at the answer. The question does not talk about the size of the subset, so why start counting subsets by size? One doesn't necessarily count the number of permutations of $n$ by their number of cycles either (which would involve Stirling numbers of the first kind, only to find $n!$ in the end); this is similar. $\endgroup$ Nov 12, 2013 at 14:14
9
$\begingroup$

Ross Belgram's method is a classic way to do it. Here's a faster way.

Consider a subset of the set $S=\{a_1,a_2,\cdots,a_n\}$, which has $n$ elements. To create a subset, which may be empty, we can go through each of the elements in the set $S$ and either put it in the subset or not put it in the subset.

That is, we have two choices for a given $a_k$: in the subset or not. So, if we have $2$ choices for each of the $n$ elements, the total number of subsets possible is $$ \underbrace {2 \cdot 2 \cdots 2}_{n \, \text{checks}} = 2^n. $$This is sometimes known as committee-forming since it is analogous to the situation where we want to form a committee of arbitrary size, given $n$ people. And, so for each of the people, you can either put the person in the committee or not put him in the committee, thus giving $2^n$ possible committees.

$ \blacksquare $

$\endgroup$
4
$\begingroup$

Given the number of answer given so far that mention binomial coefficients, I just want to say you don't need them for this problem. Repeating the comment by Daniel Fischer, all you need to know is that is subset $S$ is determined by telling for each of the $n$ elements $x$ whether $x\in S$ or $x\notin S$. That gives $2$ possibilities for $x$, and repetaing this for every $x$ gives $2^n$ possibilities. Once all those choices are fixed, the subset $S$ is completely determined. There are precisely $2^n$ subsets.

$\endgroup$
1
$\begingroup$

If we choose $r$ elements (where $0\le r\le n$) of $n$ elements to form subsets, there can be $\binom nr$ combinations

We know $$\sum_{0\le r\le n}\binom nr=(1+1)^n$$

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged .