Partitions Into Distinct Parts 

For any positive integers n and k, let p_{k}(n) denote the number of ways in which the integer n can be expressed as a sum of exactly k distinct positive integers, without regard to order. For example, the integer n = 12 can be expressed as a sum of three distinct positive integers in the following seven ways: 

_{} 

Therefore we have p_{3}(12) = 7. Obviously p_{1}(n) = 1 for all n, so the generating function for p_{1}(n) is just the geometric series 

_{} 

The values of p_{2}(n) for n = 1, 2, 3, … are easily seen to be 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, … and so on. In other words, p_{2}(1+2j) = p_{2}(2+2j) = j. Factoring x^{3} and 1+x from the power series with these coefficients, we get 

_{} 

The infinite series on the right is just the derivative of the previous geometric series, except with x^{2} in place of x, so we can differentiate the closed form of the geometric series and insert into this expression to give the generating function for p_{2}(n) 

_{} 

The first several values of p_{3}(n) are listed (by rows) below. 

_{} 

Just as every second term of the p_{2}(n) series gives an arithmetic sequence, we expect that the values of p_{3}(n) should give sequences of degree 2, and this is indeed the case, as can be seen by taking every sixth term. The values in the columns are given by seconddegree polynomials, i.e., we have 

_{} 

The generating functions for these individual subsequences are 

_{} 

The sum of these subsequences gives the generating function for the entire p_{3}(n) sequence. The numerator of the sum is a (shifted) palindromic polynomial 

_{} 

Dividing this by the denominator and simplifying, we get the complete generating function for the number of partitions of n into 3 distinct parts 

_{} 

Notice that if x^{6} is replaced with 1 in the numerator the resulting expression would be the generating function for the number of partitions of n into positive integers (not necessarily distinct) no greater than 3. We can see this immediately because each of the factors in the denominator contributes a geometric series in x^{k} where k is 1, 2, and 3 respectively, and hence the coefficient of x^{n} for n greater than 0 is the number of ways in which n is the sum of those three elements. Therefore, letting P_{j}(n) denote the partitions of n into positive integers no greater than j (and defining P_{3}(0) = 1), we have shown that P_{3}(n) = p_{3}(n+6) for all n. This correspondence can be represented pictorially as shown below for the case n = 5. 


Each partition of 11 into distinct positive integers must have a smallest part of at least 1, a second smallest part of at least 2, and a third smallest part of at least 3, so we can begin with this triad of 6 dots, and then to each column we add zero or more dots, with the requirement that the number of added dots can never decrease as we go from the leftmost to the rightmost column. The total number of additional dots to be added is 5, and with the stated restriction these rows can be interpreted as the partitions of 5 into positive integers no greater than 3. By the same reasoning it follows that, for any positive integer k, we have P_{k}(n) = p_{k}(n + k(k+1)/2). In other words, the number of partitions of n into positive integers no greater than k is equal to the number of partitions of n + k(k+1)/2 into k distinct positive integers. Thus the generating function for the latter is 

_{} 

