# Combinations formula shorthand with $2$ as the base.

Hope you are doing great. I hope you will help me to understand one thing related to combinations.

I have grasped general ideas behind permutation and combination, but I can not understand how the specified combinations have been compressed just to $$2^{100}-1$$ in the following extraction from an online presentation.

$$\binom{100}{1} + \binom{100}{2} + \binom{100}{3} + \cdots + \binom{100}{100} = 2^{100} - 1$$

I had checked whether this formula would work with another case, more simple and it has worked.
I took the case with A,B,C and calculated all possible combinations(A,B,C,AB,AC,ABC,BC) with general combination formula. Below screenshot is represented.

$$\frac{3!}{(3 - 1)!1!} + \frac{3!}{(3 - 2)!2!} + \frac{3!}{(3 - 3)!3!} = 7$$

So the answer is $$7$$. However, if I use the formula mentioned above and plug numbers $$2^3-1$$ the answer is also $$7$$.

I can not understand how this formula was derived and why $$2$$ is the base? I would appreciate if you help me to figure it out.

Thank you all in advance and sorry if the format is not so straightforward.
Asking questions here is new to me.

• – John
Feb 4, 2019 at 22:13
• Also, maybe check this out: math.stackexchange.com/q/2628135/403337
– user403337
Feb 5, 2019 at 9:10
• Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. Feb 5, 2019 at 10:56
• Thank you for your help and useful links Feb 6, 2019 at 15:36

Assume that you have a set $$S$$ with $$n$$ elements. Your combinations correspond to the (non-empty) subsets of $$S$$. To construct such a subset, for each of the $$n$$ elements you must decide whether it is to be contained in your subset or not. So, for each of the $$n$$ elements, you have $$2$$ possibilities, which makes a total number of $$2^n$$ possibilities. If your subset must not be the empty set, you have to subtract $$1$$ from that number.
A set of $$n$$ elements has $$2^n$$ subsets. You can see this by considering the set of all functions from the set to the two element set $$\{0,1\}$$. Each such function specifies a subset $$S$$ by defining $$S=\{x\mid f(x)=1\}$$.
The set of such functions, denoted $$Y^X$$, where $$X$$ is the $$n$$-element set and $$Y$$ the two-element set, indeed has order $$\mid Y^X\mid=\mid Y\mid^{\mid X\mid}=2^n$$.
The $$-1$$ comes because the empty set is not included.
Note, the binomial theorem also gives the result, quite beautifully, by considering $$(1+1)^n=\sum_{k=0}^n {n\choose k}$$.