Subscribe to Macosxnerd101's Blog

## Counting Subsets and the Binomial Theorem

The Power Set on a finite set S, denoted P(S), has 2|S| elements. Similarly enough, Sum_{i}^{n} C(n, i) = 2n, where C(n, i) represents the choose function. So what is the relationship between the Power Set and Binomial Coefficients?

First, let's look at more closely at the Power Set. The Power Set is defined to contain all possible subsets of S, including the null set. So if |S| = n, then there are subsets with all possible combinations of i elements. Looking at this in binary might help a little more. Consider subset contents represented by binary strings of length n, where a 1 denotes that the ith element is present in the subset, and a 0 denotes that the ith element is absent from the set. So if there are 5 elements, then the string 10111 denotes that elements 1-3 and 5 in S are present in the subset. So for each element in S, there are two possibilities- it either exists in the subset or it doesn't. Thus, two possibilities per element with n elements can be counted as 2 * 2 * 2 * 2 ... * 2 = 2n. This is the justification for why |P(S)| = 2|S|.

Now let's examine what we know about the power set in terms of the choose function. The choose function does exactly as it reads; it "chooses" i elements from n elements (n >= i). Here, order does not matter. So quite literally, C(n, i) counts the number of subsets of i elements from a superset of n elements. So since the power set has all the possible subsets, the count of each possible subset of i elements should add up to 2n.

Finally, let's take a look at how this can be applied to the Binomial Theorem, which states that a polynomial (x + y)n can be written as a sum of terms of the form C(n, i)xiyn-i. There is an inductive proof for the Binomial Theorem, which is rather unsatisfying and relies on algebraic manipulations. Instead, the combinatorial proof provides a lot more insight and is much more intuitive.

Consider (x + y)n as a product of n of the terms (x + y). So (x + y)n = (x + y)(x + y)(x + y) ... (x + y).

When foiling the elements, each individual term is a sequence of x's and y's. Since multiplication is associative, order does not matter. Thus, for each (x + y) term, either x or y is selected, but not both. Thus, for a term with xi, there are C(n, i) ways to accomplish this. The remaining n-i terms are chosen from the y's. This is in fact, essentially the same problem as when handling power sets and finding subsets.

S M T W T F S
1
2345678
9101112131415
16171819 20 2122
23242526272829