Partitions

In this post, I will outline my approach to this partition problem:

How many ways can you write a positive integer n as a sum of three or fewer positive integers?

Partitions are a standard topic in number theory, but I will limit myself to this specific question. I started trying to figure it out after a conversation about a different (but intimately related) problem, which Marilyn Burns e-mailed me about. Read about the original problem on her blog.

Like Marilyn, I will start by listing some takeaways:

1. For most people, time pressure is not helpful when trying to work on a challenging problem. I was unable to think about any of this when I felt I should answer Marilyn’s questions right away.
2. Knowing “the answer” does not prevent one from thinking about a problem. It is often a good idea to tell students the answer to a problem, and have them think about why it may be true.
3. Sometimes, a change of representations is the key to solving a problem. Therefore we are undermining our students’ mathematical power if we only teach what we deem to be “the best” way to think about a certain topic.
4. Proof is not just to establish the validity of a conjecture. It is also a way to get at why it is valid.

In any case, according to Wikipedia, the answer to the partition problem is

Try to apply the Wikipedia formula to the numbers you found. Sure enough, it does work. But why?

Let’s break this down into smaller problems. We have sums of one, two, or three terms, so we will tackle these one at a time. I will use n = 12 as an example, to make this easier to follow.

One term: There is always exactly one way to write n as a “sum” of one term. For example, 12 = 12.

Two terms: Once you choose the first term, the other is forced. For 12: 1+11, 2+10, etc. If the first term is t, the second term is 12-t. However I must stop after 6+6, since the next one would be 7+5, which we already saw as 5+7. So the stopping point is at the half-way mark, when the first term is half of n. There are n/2 possibilities for two terms.

What if n is odd? Look at your calculations for 9. You’ll see that there were four possibilities, from 1+8 to 4+5. The next one, 5+4, has already appeared. More generally, in n is odd, there are floor(n/2) possibilities. (Where “floor” means the greatest integer less than or equal to n/2.) In fact, this same formula works for the even case, so that is our answer for two terms.

Three terms: That is what makes the problem difficult, and therefore what makes finding the solution so satisfying. This time, once you choose the first two terms, the third term is forced. Here is a systematic search for 12. The sums are all written with the three terms ranked from least to greatest. Each row stops right before it repeats.

1+1+10, 1+2+9, …, 1+5+6     5 sums

2+2+8, 2+3+7, …, 2+5+5   4 sums

3+3+6, 3+4+5   2 sums

4+4+4    1 sum

Note that the last row has a single sum, with all the terms equal to one-third of 12. Making one of those terms greater than one-third would make another less, and therefore would yield a sum we have already listed.

So a total of 12 sums. But how to generalize? Looking at the numbers did not suggest anything to me.

The answer came while I was lying in bed in a bout of insomnia, about ten days after first seeing the problem. Since the third term is forced once the first two have been chosen, we can represent each sum on a Cartesian grid, using the first term as the x-coordinate, and the second as the y. For 12, we get this figure:

 

 

Draw a triangle with one side on the y-axis, from (0,0) to (0,6), and the opposite vertex at (4,4):

Note that we could include the one-term and two-term sums on the y-axis, by thinking of those sums as three-term sums, and including 0 terms. But we won’t do that: we will stick with the display of the three-term sums.

Shade each unit square that lies “north-west” of one of our dots:

Note that the area of the shaded region is equal to the area of the triangle. This gives us a way to generalize: the base of the triangle is n/2, and its height is n/3. This is not a coincidence, as you will see if you look back at the partitions above, and the accompanying reasoning. So the area of the triangle is n²/12. (Here is our exponent 2, and the 12 in the denominator!) The area of the triangle equals the shaded area, which in turn is equal to the number of three-term partitions.

This does not constitute a full proof, as it relies on the particular case where n is both even and a multiple of 3, but you can see that at least, it gets us close to the final answer. The Wikipedia formula is now much less mysterious.

Indeed, the above argument gives us the following approximate formula by adding our answers for three-, two-, and one-term sums:

…very close to the Wikipedia formula. Accounting for all the cases, (as we did for the two-term sums) should wrap this up. I will leave that project to you.

–Henri