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

combinationscombinatoricspermutations

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!

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.