Counting certain partitions

Question

Consider the partition of an integer into the sum of some integers:

n = n₁ + n₂ + ... + n_r, with each n_i ≥ 1. How many such partitions are there? An equivalent question: how many integer solutions (n_1, n_2, ..., n_r) to the equation n = n₁ + n₂ + ... + n_r, with each n_i ≥ 1, are there?

Answer 1

Huaizhong's solution is only correct if the order of the n_i counts, so that 7 = 4+3 and 7 = 3+4 are different solutions. The asker of the question did not appear to specify whether order counted or not.

If order does not matter, then the problem is very different and much harder, so hard that it was not solved completely until the 1930's. Some extreme values of r lend themselves to easy solutions: if r = 2, for example, then the number of partitions is (n-1)/2 or n/2, whichever is a whole number, while if r = n-1, there will only be one possible partition regardless of the value of n.

Answer 2

The number of solutions to n = n₁ + ... + n_r, n_i ≥ 1 is the same as the number of ways to distribute n balls into r containers, with at least one ball in each container. To ensure n_i ≥ 1, we use the substitution n_i = u_i + 1, i = 1, 2, ..., r. Then

n = u₁ + 1 + ... + u_r +1 = u₁ + ... + u_r + r, or u₁ + ... + u_r = n − r, u_i ≥ 0.

This means we put one ball in each container, and distribute the remaining n − r balls. This can be viewed as arranging n − r balls and r − 1 "dividers" when they are lined up in a row. The total number of objects is n − r + r − 1 = n − 1. Therefore it is the number of ways to choose r − 1 positions among n − 1 positions which is

_{n − 1}C_{r − 1} = (n − 1)!/(r − 1)!(n − r)!

= (n − 1)(n − 2)...(n − r + 1)/(r − 1)!.