Puzzle III.2: Combinations

Just a little bit [!! or a lot!] more preparation in addition to last time, and we can get back on track solving the puzzle at hand (if you’re jumping in midstream, you should go back to the beginning!)

Let’s count some quantities which are significant to our form of puzzles:

  1. How many edges does KN have?
  2. How many triangles (K3) does KN have?
  3. How many KM does KN have?
  4. How many colorings does KN have?
  5. How long would it take to exhaustively check all colorings of KN for a coloring with no monochromatic KM?

Understand here that for our particular puzzles, I am interested in N=5, N=6, and N=100,M=10, but the counting techniques will be universally applicable.

Q1: What is an edge, but a pair of vertices (since we are dealing with complete graphs)? So if we count the number of ways that we can choose a pair of vertices that define an edge, we have N choices for the first vertex, and (since one vertex is already chosen) N-1 choices for the second vertex. Thus we multiply to get N*(N-1). K_5Does this formula work? For K5 that gives us 5*(5-1) = 5*4 = 20. It is pretty easy to tell with a quick count that KN actually has only 10 edges, so what went wrong? Why is our count twice as big as it should be? It’s because we counted every edge twice. For instance the edge {2,5} was counted once when vertex 2 was the first choice, and 5 the second, and then it was counted again with 5 as the first choice and 2 as the second. Accounting for this double-counting, the correct formula is thus N*(N-1)/2.

Let’s test it against some other complete graphs: K3 by definition has three vertices. The formula predicts that it would have 3*(3-1)/2 = 3*2/2 = 3 edges, which is exactly how many edges a triangle has. Even smaller, K2 is simply two vertices connected by all possible edges — which is one edge. And the formula predicts 2*(2-1)/2 = 2*1/2 = 1, which is correct. It is not valid to apply the formula to K1 or K0, because the derivation of the formula assumed there are at least a first and a second vertex to pick from, but the formula does serendipitously predict 0 edges in both cases. I’ll let you verify the correctness of the formula for K4 and K6 (and higher if you want), so that you can just believe it to compute the number of edges in K100.

Q2: We will proceed in the same fashion to determine how many triangles KN has. We can choose 3 vertices in N*(N-1)*(N-2) ways, but we know we will need to account for overcounting. How many times is every triangle counted? More specifically, how many times is triangle 123 counted? Well, here are all the equivalent triangles that get counted separately, which we want to count only once: 123, 132, 213, 231, 312, 321. That’s 6. Does that ring any bells? Those are all the possible permutations of 123, so it’s not surprising that the amount of overcounting is 3! = 3*2*1 = 6. Every triangle gets overcounted 6 times, so we need to correct our formula by dividing by 6: N*(N-1)*(N-2)/3!

Now let’s verify. K5 should have 5*4*3/3! = 60/6 = 10 triangles. Go up yonder and count the triangles, and if you count carefully, you’ll see that it’s correct. I’ll let you in on a secret: here’s a gratuitously clever way to count triangles in K5: every edge is defined by 2 vertices. 5-2=3. Thus for every choice of two vertices there are three other vertices that didn’t get chosen, and which form a triangle. So there are just as many triangles (10) as edges (10). For K5, anyways. How many triangles in K3? Since K3 is a triangle, it is self-evident that the correct answer is 1. And the formula predicts 3*2*1/3! = 3!/3! = 1. Again, I’ll let the reader verify that the formula is also correct for K4 and K6, and then compute a believeable answer for K100 (which is not actually a quantity we need to know).

Q3: Looking back at question one, we see that the overcounting of the number of edges is not simply 2, but 2!, the number of ways to order two objects. And when selecting 3 objects, we overcount by a factor of 3!. That pattern holds true generally; when selecting M objects, we start with N choices, then N-1 choices, then N-2 choices…, we are following the process for selecting a permutation — an ordered subset of objects. So the amount of overcounting is the number of ways to order that many objects, which is M!.

So that’s half the problem solved: we know our formula will need to divide by M!. The top of the fraction is also analogous. In order to get ordered subsets of M, we choose from N, then from N-1, then from N-2, … until we have made M choices. It turns out that at our last step we will have (N-M+1) choices, so our general formula is:

C(N,M) = N*(N-1)*(N-2)*…*(N-M+1) / M!

“C(N,M)” reads “the number of combinations of M objects out of N”, or “N choose M”. Combinations are just like permutations, but unordered (hence the division by M!). This general formula answers the previous two questions as well; notice that when M=2, there are two terms (N*(N-1)) on top, and 2! on the bottom (Q1), and when M=3, there are three terms on the top, and 3! on the bottom. So the reader exercise is then to apply the general formula and compute C(100,10). As a hint, if you write out the fraction with 10 terms on the top and 10! on the bottom, you will be able to reduce the fraction by cancelling out all of the factors on the bottom. You still might want to resort to a calculator, or to a spreadsheet (the Excel formula is COMBIN(N,M)).

Q4: Counting the colorings works somewhat differently than all the other counting we have done, because for the first time we are not counting subsets of vertices. But by now we already have the principle down. To count the number of colorings, we will count the number of ways to choose a coloring, one edge at a time. How many choices for the first edge? 2 (red, blue). How many choices for the second edge? Still 2 — unlike before, our later choices are not contingent on our earlier choices, but rather they are independent. It’s going to be two choices every time, so the only question is how many times? Well, we answered that back in Q1: N*(N-1)/2. So we multiply that many 2’s all together, and that’s how many colorings. Another name for that is exponentiation: 2^(N*(N-1)/2), pronounced “two to the (N*(N-1)/2)”.

Let’s verify first on the small scale. How many colorings of K3? There are 3 edges, thus 2^3 = 2*2*2 = 8 colorings. Call the edges abc, and I’ll show them to you: abc abc abc abc abc abc abc abc.

How many colorings of K4, which has 6 edges? 2^6 = 2*2*2*2*2*2 = 64. If you’re careful, you can write them all out. Reader exercises: how many colorings of K5, K6, and K100?

Q5: This post is way overlong by now, so fortunately this will be quick. I choose to measure “how long to exhaustively search all colorings” by counting the number of edges that have to be checked for whether they are red or blue. To search exhaustively, you need to:

  • Search every coloring (all 2^(N*(N-1)/2) of them)
  • For each coloring, check every one of the KM (all N*(N-1)*…*(N-M+1)/M! of them) to see if it is monochromatic
  • For each KM, you have to inspect all of its edges (for a K3, all three edges, for a KM, all M*(M-1)/2 of them)

So you multiply those three numbers (#colorings, #subsets, #edges per subset) together, and that’s how long a brute force, exhaustive search will take. For Puzzle I, searching all colorings of K5 for monochromatic K3 would require checking the colors of this many edges:

[2^(5*4/2)] * [5*4*3/3!] * [3*2/2] = [2^10] * [10] * [3] = 1024*10*3 = 30720

You can compute (or try to compute) the number of edge-color-checks required for an exhaustive search of all colorings of K6 for K3 as in Puzzle II, or Puzzle III with K100 and K10 (warning: the numbers get kinda big)!

Next time, I promise, I will finally reveal the supercool answer, so stay tuned!

Advertisements

2 Responses

  1. […] Puzzle III.2: Combinations […]

  2. […] Next time, we’ll ask (and answer) questions of the form: If we were to search all the colorings of K5 (or K6 (or K100)) for one that had no monochromatic K3 (or K10), how long would it take? […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: