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?
Thanks!
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.