1

There is this theorem in my book in the chapter of permutations and combinations which states: The total number of combinations of n different things taken any number of them at a time is $2^n$.

Its proof is given as: Each thing may be disposed of in two ways-it may or may not be chosen. Therefore, the total number of ways of disposing of all the n things $=2 \times 2\times 2 \times ...\text{n times}=2^n$. Hence, the number of combination (selections)=$2^n$.

I searched the internet for this theorem but could not find it. Can someone please explain the meaning of this theorem to me as well as its proof. What does "disposed" mean here?

MrAP
  • 3,003
  • 1
    As for the name of the theorem, this can be called a special case of the binomial theorem where $x=y=1$. That is to say, $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=2^n$ – JMoravitz Jul 25 '17 at 17:12

2 Answers2

7

Suppose you have some set $S=\{s_1,...,s_n\}$.

You're essentially trying to see how many subsets of $S$ there are (ie. the cardinality of the powerset of $S$).

For each subset $S_i$, assign it the ordered tuple $((x_i)_1,...,(x_i)_n)$ where $(x_i)_k=\begin{cases}0 & s_k\not\in S_i\\1 & s_k\in S_i \end{cases}$

Clearly, the ordered tuples are different for each subset and all possible tuples in $\{0, 1\}^n$ are assigned to some subset. Therefore counting the number of subsets is equivalent to counting the number of possible ordered tuples.

Each ordered tuple is a sequence of $0$s and $1$s and therefore counting the number of possible tuples is equivalent to counting the number of different length $n$ binary strings.

The answer is $2^n$.

What I've laid out here is essentially the idea which your book explains. Each item in the set can be 'on' or 'off' and this is like binary.

Shuri2060
  • 4,353
1

I think this is best illustrated with a simple example.

Suppose you have a set of 4 objects: $\{ A,B,C,D \}$

The question is: how many possible combinations of objects are there? Some possible combinations are: $AB$, $ABD$, $BCD$.

Note that the order does not matter when it comes to combinations so $AB$ would be the same as $BA$. One useful way to think about this then is in terms of sets, for sets have no order. So, $AB$ can be thought of as $\{ A, B \}$.

Also note that taking any of the objects is a possible combination as well, and this would correspond to the empty set $\emptyset$

OK, but how many possible combinations are there (or, in terms of sets: how many subsets of $\{ A,B,C,D \}$ are there?

OK, so the theorem says that this is $2^n$ with $n$ the number of objects in the original set, and in this example we have $n=4$ so there should be $2^4=16$ combinations. Now, you can try to find them all, and presumbaly you can find all $16$. OK, but why does this hold true in general? Well, think about how you could systematically generate all combinations.

First of all, take the first object $A$. We can put $A$ in any combination or not. OK, so lets's consider $\{ A \}$ and $\emptyset$ as temporary results or 'partial combinations'.

Now let's consider the next object $B$. Well, to each of the partial combinations we can either add $B$ or not.

So, the partial combination $\{ A \}$ gives rise to (add $B$) $\{ A ,B \}$ and (don't add $B$) $\{ A \}$.

Likewise, the partial combination $\emptyset$ gives rise to (add $B$) $\{ B \} $ and (don't add $B$) $\emptyset$.

OK, so now we have $4$ partial combinations: $\{ A ,B \}$, $\{ A \}$, $\{ B \} $, and $\emptyset$.

On to the next element $C$.

Again, we can add or not add $C$ to any of the partial combinations, and s0 each partial combination gives rise to two new partial combinations. So, the number of partial combinations doubles once again: $2 \times 4 = 8$.

And finally, with $D$ it doubles once again: $2 \times 8 = 16$

.... and I think you should see the pattern now ....

Bram28
  • 100,612
  • 6
  • 70
  • 118