ABSTRACT
This chapter discusses partitions of integers and develops algorithms for generating set partitions in lexicographic order, as well as ranking and unranking algorithms. The Catalan numbers are a sequence of numbers which arise naturally in many different combinatorial enumeration problems. The chapter provides ranking and unranking algorithms for the lexicographic ordering of the Catalan families. The first few Catalan numbers turns out that there is a very simple formula for the Catalan numbers, which is stated in the theorem presented in this chapter. There are many other families which have the same cardinality, and which therefore could equally well be taken as a definition of Catalan families. These include triangulations of polygons, rooted plane binary trees, rooted plane bushes, and non-crossing handshakes, to name a few examples.
