TOPICS
Search

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

 a_(i+1)<=1+max{a_1,a_2,...,a_i}

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


Explore with Wolfram|Alpha

References

Ruskey, F. "Info About Set Partitions." http://www.theory.csc.uvic.ca/~cos/inf/setp/SetPartitions.html.

Referenced on Wolfram|Alpha

Restricted Growth String

Cite this as:

Weisstein, Eric W. "Restricted Growth String." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RestrictedGrowthString.html

Subject classifications