This will be, I think, a relatively gentle treatment of what could be a rather complicated matter.
The problem came up in problem seminar this week, the matter of integer partitioning. Specifically, given an integer n, how many different ways can you write it as the sum of smaller integers? More specifically, and a notably easier problem, how many different ways can you write it as the sum of three smaller integers?
For example, 6 can be written as 1 + 4 + 1, 3 + 2 + 1, and 2 + 2 + 2. Notice that we’re counting 1 + 4 + 1 as the same as 4 + 1 + 1. 5 can be written as 1 + 1 + 3, 1 + 2 + 2. So the number of 3-partitions for 6 is 3, and the number of 3-partitions for 5 is 2. Clearly 0, 1, and 2 all have no 3-partitions, and 3 has one, 1 + 1 + 1. But for a general n, how many are there?
The basic approach is going to be to come up with a method of constructing all 3-partitions of a given number, and then the formula for the total number falls out almost automatically. What follows then is a reduction from the initially simple to understand but difficult to compute formula to a relatively difficult to understand but surprisingly simple formula. It’s interesting.
(more…)
