1
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by Trevor Wilson, Daniel Fischer, Hagen von Eitzen, Old John, John Gowers Nov 13 '13 at 23:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 9
    $\begingroup$ For every element of the set, you have two choices, whether it's in the subset or not. $\endgroup$ – Daniel Fischer Nov 12 '13 at 13:22
  • $\begingroup$ @BrianM.Scott no, the n refers to the superset. $\endgroup$ – Shaurya Gupta Nov 12 '13 at 13:24
8
$\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$
  • 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$ – Marc van Leeuwen Nov 12 '13 at 14:14
8
$\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$
3
$\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$

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