info prev up next book cdrom email home

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$.


Ruskey, F. ``Info About Set Partitions.''

© 1996-9 Eric W. Weisstein