Combinations that include all possible subsets and the null set, and its relation with binomials and binary numbers The regular way we calculate combinations show the number of possible selections that can be made when r items are chosen from a set of n elements, denoted by $C(n, r)$. Therefore, $C(3,2)$ would be $3!/(2!(3-2)!)=6/2=3$. This means for a set of elements, $(A, B, C)$, there are 3 different ways to subset 2 out of it when order does no matter: $AB$, $AC$ and $BC$.
There is another sort of combination which I believe should have also been mathematically defined but am at a loss of formulating it. It involves the null element, which is not having an item at all. In this case, the number of ways we can choose between a set of 2 elements, say $(X, Y)$ would be $4$: $X$, $Y$, $XY$ and none. It can be observed that we are not choosing a fixed number $r$ out of $n$, but rather playing with all possibilities of having or not having $X$ and $Y$, in all possible combination. Choosing between $(A, B, C)$ this way would give: $C(3,1)$: $A$, $B$, $C$ plus $C(3,2)$: $AB$, $AC$, $BC$ plus $C(3,3)$: $ABC$ and $C(3,0)$: none, which gives $3+3+1+1=8$ possibilities. My question would be:

*

*Is there a formal name for this?

*If we define a null element, $O$, the formula for 2 would be $C(3,2)+1$, where the 1 refers to the case where no element is picked. Likewise, the formula for 3 elements can be: $C(4,3)+4$, where 4 is the case in which each element is picked by itself (therefore 2, but not 1 null element is involved), and one which all elements are null. The final addition gets harder to calculate when larger sets are involved (and the number of null elements in a given subset gets larger). It seems likely that the only foolproof way to calculate this is to take $C(n, n)+C(n, n-1)+C(n, n-2)...C(n,0)$, but is there a simpler formula for this?

*What is the best way to approach such problem?

*This problem of choice-possibilities seems to point to the fact that diverse concepts in mathematics, such as the binomial theorem, pascal's triangle, the binary number system and the nature of factorials are all inter-related and connected at a deep level. It would be interesting to ask how such relationship can be understood and the significance of it all. For example, why is $2^n$ such a magic number in these scenarios? (It is the sum of each row on Pascal's triangle, where $n$ gives the row number, starting from 0; which is the same as the sum of all coefficients in a binomial expansion to the $n$, and also the simplified formula for $C(n, n)+C(n, n-1)+C(n, n-2)...C(n,0)$.) What does the base $2$ mean in all these cases?

*The factorial sequence $C(n, n)+C(n, n-1)+C(n, n-2)...C(n,0)$ map exactly to the binomial coefficients: $(1,2,1)$ when n=2, $(1,3,3,1)$ when n=3 etc... This means $n!/(r!(n-r)!)$ is essentially a way to calculate each coefficient by its own terms. How did this formula come about and how can we think of it in terms of its relation to the whole picture?

 A: First of all, please use the standard notation $\binom nr$ for "$n$ choose $r$", the binomial coefficient that counts the number distinct $r$-element subsets that can be chosen from any given $n$-element set, for what you write as $C(n,r)$: given that there is this special notation exclusively reserved for these numbers, why revert to a lowly generic function-of-two-arguments notation? Second, your problem does not seem to be equivalent to adding an "empty set" choice for each of the $r$ elements to choose, because (1) an element and a set of elements are not the same type of thing, so choosing the empty set in place of an element is not really what you are doing, and (2) apparently you allow "choosing the empty set" multiple times, whereas ordinary elements become forbidden once they have already been chosen once. What you seem to be hinting at is what can be expressed as "choosing a subset of at most $r$ elements", and the number is than given as $\binom nr+\binom n{r-1}+\binom n1+\binom n0=\sum_{k=0}^r\binom nk$. There is no easier general formula for this number, but for the case $r=n$ that you seem to be particularly interested in the sum gives$~2^n$, as each element can independently be chosen to be or not to be in the subset.
There you have the deeper significance of the number $2$: it is the number of options in "to be or not to be".
