The Technique of Partitions

After an extended break for Lent, we continue with the series on counting principles. I had ended the last post in the series with a promise that we will look into the technique of partitioning. And I had left you with a problem to solve: Given that x, y, and z are natural numbers, how many solutions exist to the equation x + y + z = 100? Let us begin to address this with a simpler problem.

Suppose we are given that x + y = 10 and that x and y are natural numbers, how many solutions are there? Here, we can write y = 10 – x. Now, we can simply increase x from the smallest value 1 to the largest value 9. We can obtain the following ordered pairs as solutions: (1, 9), (2, 8), (3, 7), (4, 6), (5, 5), (6, 4), (7, 3), (8, 2), and (9, 1). We can visualize this as follows

Since all the ‘1’s are identical, there is no sense in thinking of ordering them. However, we can see the partition in red. Including the partition, there are 10 + 1 = 11 items, the 10 identical ‘1’s and the partition, that need to be placed in a row. However, only the position of the partition matters. If the partition is in position 2, then we have x = 1 and y = 9. However, the partition cannot be placed in positions 1 and 11 because then either x or y would be zero. Hence, what we have is a choice of 9 positions for the partition, from position 2 to position 10, giving us 9 solutions to the original equation.

What we can say is that, we had 11 items to place. However, we were first constrained to fill each of the variables x and y with a 1, thereby ensuring that we have only positive values for each of them. This left nine items, including eight ‘1’s and the partition. And since we had one partition, the problem boiled down to choosing one position out of nine, which is ⁹C₁ = 9.

Now, let us consider the original problem. We want to find the number of natural number solutions to the equation x + y + z = 100. We recognize that, since there are three variables, we will need two partitions, leaving us with 102 items. However, we will first have to distribute one ‘1’ to each of the variables to ensure that we have only natural number solutions. This leaves us with 99 items. Now, the two items have to be placed in the 99 positions that remain, which can be done in ⁹⁹C₂ = 4851 ways. This means that there are 4851 solutions to the equation x + y + z = 100 such that x, y, and z are natural numbers.

We can generalize this process. Suppose we have n identical items that need to be divided into r groups such that no group is empty. Now, for r groups we will need r – 1 partitions, leading to a total of n + r – 1 items. Now, we need to fill each of the groups with one item to ensure that no group is empty. This leaves us with n – 1 items. And we have to place r – 1 partitions, which can be done in ^{n – 1}C_{r – 1}.

We can now relax the restriction on the numbers and say that they need not be natural numbers (i.e. greater than zero), but whole numbers (i.e. greater than or equal to zero). In this case, we are permitting empty groups. Now the problem reduces to placing r – 1 partitions in n + r – 1 positions, which can be done in ^{n + r – 1}C_{r – 1} ways. Hence, if we return to the original problem, the number of solutions to x + y + z = 100 such that x, y, and z are whole numbers is ¹⁰²C₂ = 5151.

In this post, we looked at the technique of partitions. In the next post, we will consider the exponent of a prime number p in the number n! Look out for that!