[Information Index] [Generation Index] [COS homepage]

Info about Set Partitions

A set partition of the set [n] = {1,2,...,n} is a collection B0,B1,...,Bj of disjoint subsets of [n] whose union is [n]. Each Bi is called a block. Below we show the partitions of [4]. The periods separate the individual sets so that, for example, 1.23.4 is the partition {{1},{2,3},{4}}.

1 blocks: 1234
2 blocks: 123.4,  124.3,  134.2,  1.234,  12.34,  13.24,  14.23
3 blocks: 1.2.34,  1.24.3,  1.23.4,  14.2.3,  13.2.4,  12.3.4
4 blocks: 1.2.3.4

Each partition above has its blocks listed in increasing order of smallest element; thus block 0 contains element 1, block 1 contains the smallest element not in block 0, and so on. A Restricted Growth string (or RG string) is a string a[1..n] where a[i] is the block in which element i occurs. Restricted growth strings are often called restricted growth functions. Here are the RG strings corresponding to the partitions shown above.

1 blocks: 0000
2 blocks: 0001,  0010,  0100,  0111,  0011,  0101,  0110
3 blocks: 0122,  0121,  0112,  0120,  0102,  0012
4 blocks: 0123

The name "restricted growth" comes from the fact that RG strings are characterized by the following growth inequality (for i = 1,2,...,n-1, and with a[1] = 0):

a[i+1]   <   1 + max{a[1],a[2],...,a[i]}.

The number of partitions of an n-set is called a Bell number, bn. For n = 1,2,...,15, the Bell numbers have the values 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322. This is sequence A000110(M1484, N0585) in Neil J. Sloane's database of integer sequences. The Bell numbers have the exponential generating function exp(ex-1) and satisfy the recurrence relation

bn+1   =  
 n 
\
/   
k=0
bk  ( n
k
)

The number of partitions of an n-set into k blocks is called a Stirling number of the second kind and is denoted S(n,k). They satisfy the following recurrence relation, which forms the basis of recursive algorithms for generating them.

S(n,k) = k S(n-1,k) + S(n-1,k-1)

Sometimes ther Stirling numbers of the second kind are written in a manner similar to the binomial coefficients, except that curly braces are used instead of parentheses. Using that notation the recurrence relation is

{ n
k
}   =   k { n-1
  k
} + { n-1
k-1
}

A small table of these numbers may be found at the end of this page.

There is an interesting correspondence between non-taking rooks on a half-chessboard and set partitions. A rook in position i,j corresponds to i and j being in the same block. A partition with k blocks corresponds to the placement of n-k rooks. The placement shown below corresponds to the set partition {1,6,7}, {2,4,8}, {3,5}. (See Knuth vol. 3, Exercise 5.1.3.19 for more on this correspondence.)

1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8

In Gray code order, successive RG functions differ in only one position. Such a change implies that a single element moves from one block to another. (The converse is not necessarily true.) In terms of rooks on a chessboard, a single rook is either removed from the board, added to the board, or moved from one square of the board to another. If Gray code order is chosen, then there is an output option that lists pairs (e,b), where e is the element and b is the block into which it moves.


k =  1 2 3 4  5 6 7 8
n=1   1
2 1 1
3 1 3 1
4 1 7 6 1
5 1 15 25 10 1
6 1 31 90 65 15 1
7 1 63 301 350 140 21 1
8 1 127 966 1701 1050 266 28 1

Relevant Links and References


Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 14760 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.