[Math] Why is $2^n$ considered to be all the possible combinations of $n$ items


I've seen in several texts that $2^n$ is the total number of combinations of $n$ items. I don't get how we get that number. I always end up with $2^n – 1$.

For example, if $n = 4$, we have:

  • $\frac{4!}{1!3!} =4$
  • $\frac{4!}{2!2!} =6$
  • $\frac{4!}{3!1!} =4$
  • $\frac{4!}{4!0!} =1$

$4 + 6 + 4 + 1 = 15$.

I get $15$ instead of $16$. Yet in many texts, it says $2^n$. Why do we say it's $2^n$ and doesn't assuming it is $2^n$ when in fact it seems like it's $2^n – 1$ mess up our calculations for other stuff?


Best Answer

Construct any subset $S$ of $n$ items as follows: We put $n$ items in a row and go through them one by one. For each item we either say yes or no to indicate whether it belongs to $S$.

Since there are $2$ choices per item, by the rule of product, $S$ can be constructed in $2^n$ ways.