Restricted Growth String

For a Set Partition of $n$ elements, the $n$-character string $a_1a_2\ldots a_n$ in which each character gives the Block (${\bf B}_0$, ${\bf B}_1$, ...) in which the corresponding element belongs is called the restricted growth string (or sometimes the Restricted Growth Function). For example, for the Set Partition $\{\{1\}, \{2\}, \{3,4\}\}$, the restricted growth string would be 0122. If the Blocks are ``sorted'' so that $a_1=0$, then the restricted growth string satisfies the Inequality

$$a_{i+1}\leq 1+\max\{a_1, a_2, \ldots, a_i\}$$

for $i=1$, 2, ..., $n-1$.

References

Ruskey, F. ``Info About Set Partitions.'' http://sue.csc.uvic.ca/~cos/inf/setp/SetPartitions.html.