My previous post displayed this picture:
If you haven’t had a chance to ponder the image and look for patterns, maybe you want to do that now! I want to say a few things about it. First, as JM observed, one way to look at this is a “tree with each branch asking, `Which color should I eliminate?'”
Here’s another way to think about it (which really amounts to the same thing). Each graph is a picture of all the subsets of a certain set, arranged so that the empty subset is at the bottom, the complete set is at the top, and all the sets in between are arranged so that there is an upwards-pointing edge (or path of several upwards-pointing edges) connecting each set to the other sets of which it is a subset. So if we start at the bottom and travel upwards following the edges, more and more colors will be added, but once we have seen a certain color, it will remain in all the sets we encounter from then on (as long as we keep traveling only upwards). These sorts of diagrams are actually called Hasse diagrams. (Hasse diagrams are a bit more general; they can actually be used to visualize any partially ordered set.)
Now, xander counted the number of sets in each row. He correctly pointed out that I should have included another diagram at the top, namely, an empty dotted box. If we include that, counting the number of sets in the rows of each diagram gives an interesting pattern:
1 2 1
1 3 3 1
1 4 6 4 1
Do you recognize this pattern? That’s right, it’s Pascal’s triangle! We would expect the next row to be 1 5 10 10 5 1. Let’s see:
Sure enough! This is not too surprising, actually: each row of one of these diagrams shows all the size-k subsets of a size-n set, that is, the number of ways to choose k colors out of n. This is also called a binomial coefficient, and the binomial coefficients are exactly the numbers that make up Pascal’s triangle.
Now, someone else also mentioned hypercubes. Certainly the first diagram I showed looks like a line (a “one-dimensional cube”), the second looks like a square (a two-dimensional cube), and it’s not too hard to imagine the next one as a drawing of a three-dimensional cube. But how do we know whether the next one looks like a four-dimensional cube? And what the heck is a four-dimensional cube, anyway? I’ll talk about that in my next post!