Most positive integers can be written as the sum of  positive integers in several ways. The elements or "parts" of such a sum for an integer n are called a partition of N.   Partitions of N can contain as few as a single part  {N}, or as many as N parts {1,1,1,.....1}.  The normal representation of a partition is as a set of integers which sum to N, without the "+" signs.

For example 5 may be partitioned in 7 ways.  {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,,1,1,1}, {1,1,1,1,1}.    Note that the order on the elements of a partition are not significant - they are typically written in colexicographical  (reverse dictionary) order, also called standard form (SF).   There are two common forms of the function which returns the number of partitions for a given integer:  P(N) represents the total number of partitions of N.   The other, P(N,k) or P_k(N),  represents the number of partitions of N that contain K elements.  Clearly P(N)=sum(P_k(N),  k=1 to N).

The program available here can generate all partitions or those of a specified size for numbers from 1 to 100.   Actually, for P(N) grows quite rapidly, P(100)= exceeds 190 million, so it is not feasible to list partitions for large numbers.   The program will stop computing after a specified number up to 1,000 are displayed.   

I would like to be able to display the partition of a particular rank, say the one millionth partition of 100, but haven't quite figured out how to do it yet. 

This page was motivated to help solve  problem #103 in the Project Euler set of programming challenges:  

"Find the set, A,  of 7 positive integers with the following characteristics:

1. No  two different subsets of A have the same sum of elements.

2. For any two subsets, B & C,  if B has more elements than C then the sum of the elements of B is greater than the sum of the elements of C.

3. A is set which meets the above conditions and has the smallest total sum of elements. "  

A challenge indeed! 

Download source code

Download executable program