Enumerating Partitions

As part of my research into Data Clustering, I've been considering how to enumerate a set of partitions. Now this is pretty esoteric stuff, but I'm writing this entry to help me clarify my thoughts and define the problem.

A partition of a set is defined as a division of a group of identical objects into a collection of (unordered) subsets of various sizes. According to Tuckers "Applied Combinatorics" (page 257), partitions are normally written as a sum and list of integers in increasing order. For example, the seven partitions of the integer 5 are:

1 + 1 + 1 + 1 + 1          1 + 1 + 1 + 2          1 + 1 + 3
1 + 2 + 2          1 + 4          2 + 3          5

The problem enumeration involves labeling each of these partition with a number such that the partition can (that is which elements are in which subset), can be recoved from the numeric label. A nice feature for a particular enumeration to have would be if it were compact, that is if there were just as many consecutive labels as there were partitions.

As I write this, I realize that the particular application I have in mind really requires that the objects being partitioned not be identical. But more about this later.