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):
The number of partitions of an n-set is called a Bell number, b_{n}. 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(e^{x}-1) and satisfy the recurrence relation
b_{n+1} | = |
| b_{k} | ( |
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.
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 |