Restricted Growth String

For a set partition of n elements, the n-character string a_1a_2...a_n in which each character gives the set block (B_0, 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 set blocks are "sorted" so that a_1=0, then the restricted growth string satisfies the inequality


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

Explore with Wolfram|Alpha


Ruskey, F. "Info About Set Partitions."

Referenced on Wolfram|Alpha

Restricted Growth String

Cite this as:

Weisstein, Eric W. "Restricted Growth String." From MathWorld--A Wolfram Web Resource.

Subject classifications