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

\begin{displaymath}
a_{i+1}\leq 1+\max\{a_1, a_2, \ldots, a_i\}
\end{displaymath}

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


References

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




© 1996-9 Eric W. Weisstein
1999-05-25