Discrete Mathematics An Open Introduction, 3rd edition

Subsets should be familiar, otherwise read over Section 0.3 again. Suppose we look at the set $A=\{1,2,3,4,5\}\text{.}$ How many subsets of $A$ contain exactly 3 elements?

First, a simpler question: How many subsets of $A$ are there total? In other words, what is $|\mathcal{P}(A)|$ (the cardinality of the power set of $A$)? Think about how we would build a subset. We need to decide, for each of the elements of $A\text{,}$ whether or not to include the element in our subset. So we need to decide “yes” or “no” for the element 1. And for each choice we make, we need to decide “yes” or “no” for the element 2. And so on. For each of the 5 elements, we have 2 choices. Therefore the number of subsets is simply $2\cdot 2\cdot 2\cdot 2\cdot 2=2^5$ (by the multiplicative principle).

Of those 32 subsets, how many have 3 elements? This is not obvious. Note that we cannot just use the multiplicative principle. Maybe we want to say we have 2 choices (yes/no) for the first element, 2 choices for the second, 2 choices for the third, and then only 1 choice for the other two. But what if we said “no” to one of the first three elements? Then we would have two choices for the 4th element. What a mess!

Another (bad) idea: we need to pick three elements to be in our subset. There are 5 elements to choose from. So there are 5 choices for the first element, and for each of those 4 choices for the second, and then 3 for the third (last) element. The multiplicative principle would say then that there are a total of $5\cdot 4\cdot 3=60$ ways to select the 3-element subset. But this cannot be correct ($60>32$ for one thing). One of the outcomes we would get from these choices would be the set $\{3,2,5\}\text{,}$ by choosing the element 3 first, then the element 2, then the element 5. Another outcome would be $\{5,2,3\}$ by choosing the element 5 first, then the element 2, then the element 3. But these are the same set! We can correct this by dividing: for each set of three elements, there are 6 outcomes counted among our 60 (since there are 3 choices for which element we list first, 2 for which we list second, and 1 for which we list last). So we expect there to be 10 3-element subsets of $A\text{.}$

Is this right? Well, we could list out all 10 of them, being very systematic in doing so, to make sure we don’t miss any or list any twice. Or we could try to count how many subsets of $A$ don’t have 3 elements in them. How many have no elements? Just 1 (the empty set). How many have 5? Again, just 1. These are the cases in which we say “no” to all elements, or “yes” to all elements. Okay, what about the subsets which contain a single element? There are 5 of these. We must say “yes” to exactly one element, and there are 5 to choose from. This is also the number of subsets containing 4 elements. Those are the ones for which we must say “no” to exactly one element.

So far we have counted 12 of the 32 subsets. We have not yet counted the subsets with cardinality 2 and with cardinality 3. There are a total of 20 subsets left to split up between these two groups. But the number of each must be the same! If we say “yes” to exactly two elements, that can be accomplished in exactly the same number of ways as the number of ways we can say “no” to exactly two elements. So the number of 2-element subsets is equal to the number of 3-element subsets. Together there are 20 of these subsets, so 10 each.

The number of bits (0’s or 1’s) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1’s. The number of 1’s in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.

For example, the elements of the set ${\mathbf{B}}_2^3$ are the bit strings 011, 101, and 110. Those are the only strings containing three bits exactly two of which are 1’s.

The counting questions: How many bit strings have length 5? How many of those have weight 3? In other words, we are asking for the cardinalities $|{\mathbf{B}}^5|$ and $|{\mathbf{B}}_3^5|\text{.}$

To find the number of 5-bit strings is straight forward. We have 5 bits, and each can either be a 0 or a 1. So there are 2 choices for the first bit, 2 choices for the second, and so on. By the multiplicative principle, there are $2\cdot 2\cdot 2\cdot 2\cdot 2=2^5=32$ such strings.

We can keep going down, but this should be good enough. Both ${\mathbf{B}}_1^3$ and ${\mathbf{B}}_2^3$ contain 3 bit strings: we must pick one of the three bits to be a 1 (three ways to do that) or one of the three bits to be a 0 (three ways to do that). Also, ${\mathbf{B}}_3^3$ contains just one string: 111. Thus $|{\mathbf{B}}_2^4|=6$ and $|{\mathbf{B}}_3^4|=4\text{,}$ which puts ${\mathbf{B}}_3^5$ at a total of 10 strings.

But wait —32 and 10 were the answers to the counting questions about subsets. Coincidence? Not at all. Each bit string can be thought of as a code for a subset. To represent the subsets of $A=\{1,2,3,4,5\}\text{,}$ we can use 5-bit strings, one bit for each element of $A\text{.}$ Each bit in the string is a 0 if its corresponding element of $A$ is not in the subset, and a 1 if the element of $A$ is in the subset. Remember, deciding the subset amounted to a sequence of five yes/no votes for the elements of $A\text{.}$ Instead of yes, we put a 1; instead of no, we put a 0.

For example, the bit string $11001$ represents the subset $\{1,2,5\}$ since the first, second and fifth bits are 1’s. The subset $\{3,5\}$ would be coded by the string $00101\text{.}$ What we really have here is a bijection from $\mathcal{P}(A)$ to ${\mathbf{B}}^5\text{.}$

Now for a subset to contain exactly three elements, the corresponding bit string must contain exactly three 1’s. In other words, the weight must be 3. Thus counting the number of 3-element subsets of $A$ is the same as counting the number 5-bit strings of weight 3.

The integer lattice is the set of all points in the Cartesian plane for which both the $x$ and $y$ coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines.

A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the point $(0,0)$ to $(3,2)\text{:}$

Notice to ensure the path is the shortest possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be 5 steps. Thus each path has length 5.

The counting question: how many lattice paths are there between $(0,0)$ and $(3,2)\text{?}$ We could try to draw all of these, or instead of drawing them, maybe just list which direction we travel on each of the 5 steps. One path might be RRUUR, or maybe UURRR, or perhaps RURRU (those correspond to the three paths drawn above). So how many such strings of R’s and U’s are there?

Notice that each of these strings must contain 5 symbols. Exactly 3 of them must be R’s (since our destination is 3 units to the right). This seems awfully familiar. In fact, what if we used $1$’s instead of R’s and 0’s instead of U’s? Then we would just have 5-bit strings of weight 3. There are 10 of those, so there are 10 lattice paths from (0,0) to (3,2).

The correspondence between bit strings and lattice paths does not stop there. Here is another way to count lattice paths. Consider the lattice shown below:

Any lattice path from (0,0) to (3,2) must pass through exactly one of $A$ and $B\text{.}$ The point $A$ is 4 steps away from (0,0) and two of them are towards the right. The number of lattice paths to $A$ is the same as the number of 4-bit strings of weight 2, namely 6. The point $B$ is 4 steps away from (0,0), but now 3 of them are towards the right. So the number of paths to point $B$ is the same as the number of 4-bit strings of weight 3, namely 4. So the total number of paths to (3,2) is just $6+4\text{.}$ This is the same way we calculated the number of 5-bit strings of weight 3. The point: the exact same recurrence relation exists for bit strings and for lattice paths.

If that looks daunting, go back to the case of $(x+y{)}^3=(x+y)(x+y)(x+y)\text{.}$ Why do we only have one $x^3$ and $y^3$ but three $x^{2}y$ and $x{y}^2$ terms? Every time we distribute over an $(x+y)$ we create two copies of what is left, one multiplied by $x\text{,}$ the other multiplied by $y\text{.}$ To get $x^3\text{,}$ we need to pick the “multiplied by $x$” side every time (we don’t have any $y$’s in the term). This will only happen once. On the other hand, to get $x^{2}y$ we need to select the $x$ side twice and the $y$ side once. In other words, we need to pick one of the three $(x+y)$ terms to “contribute” their $y\text{.}$

These numbers we keep seeing over and over again. They are the number of subsets of a particular size, the number of bit strings of a particular weight, the number of lattice paths, and the coefficients of these binomial products. We will call them binomial coefficients. We even have a special symbol for them: $(\genfrac{}{}{0ex}{}{n}{k})\text{.}$

Remember, this is because we can start the bit string with either a 1 or a 0. In both cases, we have $n-1$ more bits to pick. The strings starting with 1 must contain $k-1$ more 1’s, while the strings starting with 0 still need $k$ more 1’s.

Since $|{\mathbf{B}}_k^n|=(\genfrac{}{}{0ex}{}{n}{k})\text{,}$ the same recurrence relation holds for binomial coefficients:

Let’s arrange the binomial coefficients $(\genfrac{}{}{0ex}{}{n}{k})$ into a triangle like follows:

This can continue as far down as we like. The recurrence relation for $(\genfrac{}{}{0ex}{}{n}{k})$ tells us that each entry in the triangle is the sum of the two entries above it. The entries on the sides of the triangle are always 1. This is because $(\genfrac{}{}{0ex}{}{n}{0})=1$ for all $n$ since there is only one way to pick 0 of $n$ objects and $(\genfrac{}{}{0ex}{}{n}{n})=1$ since there is one way to select all $n$ out of $n$ objects. Using the recurrence relation, and the fact that the sides of the triangle are 1’s, we can easily replace all the entries above with the correct values of $(\genfrac{}{}{0ex}{}{n}{k})\text{.}$ Doing so gives us Pascal’s triangle.

We can use Pascal’s triangle to calculate binomial coefficients. For example, using the triangle below, we can find $(\genfrac{}{}{0ex}{}{12}{6})=924\text{.}$