Some words about Post without words #2

My previous post displayed this picture:

As Yuriy Kashnikov guessed, I made this picture using diagrams, a Haskell library I am developing for creating images like this. (You can see the source code for this picture here.)

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
1 1
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!

About these ads
This entry was posted in counting, pascal's triangle, pattern, pictures and tagged , , , , . Bookmark the permalink.

4 Responses to Some words about Post without words #2

  1. I thought of Boolean logic.

    • Brent says:

      Interesting, can you elaborate?

      • Like xander says below vectors in unit hypercubes have entries that are 0’s and 1’s, so you can think of (0,1,0) as A’BC’ (not-A and B and not-C). Visualising expressions as points on cubes can help you compress expressions in logic. For example the expression ” ABC or AB’C or AB’C’ or A’B’C or A’B’C’ ” can be thought of as the points (1,1,1),(1,0,1),(1,0,0),(0,0,1) and (0,0,0) which lie on the union of the plane y=0 and the line x=z=1, so we must have that the original expression is equivalent to ” B’ or AC “, which it is.

  2. xander says:

    It seems that the graphs pictured have some redundant information. The colors are not really necessary in order to see what is going on (or the ordering of the colors is unecessary—either is an appropriate characterization, though I prefer the former for reasons that shall become clear in a moment).

    If we were to color each node with only two colors—say black and white—then each node could represent an n-dimensional vector where (for instance) black represents a 0 and white a 1. In this case, the edges of the graph are in correspondence with the edges of an n-dimensional box with sides of length 1. Starting at the origin (n black squares, or the point (0,0,…,0)), we can move along an edge. There are n possible points that we could reach, each represented by an n-dimensional vector with n-1 0s, and a single 1 in some position. There are n such points, thus the second row of any such graph will have n nodes.

    Continuing the process, we can sketch out our n-dimensional cube. Huzzah! This may explain the relation both to Boolean logic (each entry of any vector is Boolean in nature, in that it can be only a 1 or 0), and can give us a link to a geometric interpretation.

    xander

Comments are closed.