Restricted Growth Function and Partition

Question

Can someone explain how do I convert from Partition to Restricted Growth Function to and vice versa? For example: how [1,1,1,2] is the RGF of {{1,2,3},{4}} partition?

I have read the definitions but I do not understand it.

Answer 1

The procedure is this:

First, you sort the parts in the partition by their lowest element. In the case of the partition $\{\{1,2,3\},\{4\}\}$, this is already done: the order is $(\{1,2,3\}, \{4\})$. For a more complicated example, we sort $$ \{ \{3,6\}, \{1,4,8\}, \{2\}, \{5,7\}\} \Longrightarrow (\{1,4,8\}, \{2\}, \{3,6\}, \{5,7\}). $$ Second, you assign the parts labels $1,2,3, \dots$ in that order. In the case of $(\{1,2,3\}, \{4\})$, $\{1,2,3\}$ gets assigned label $1$, and $\{4\}$ gets assigned label $2$. In the case of $(\{1,4,8\}, \{2\}, \{3,6\}, \{5,7\})$, $\{1,4,8\}$ gets assigned label $1$, $\{2\}$ gets assigned label $2$, $\{3,6\}$ gets assigned label $3$, and $\{5,7\}$ gets assigned label $4$.

Some people begin at $0$ instead of $1$.

Finally, you write down the restricted growth string by writing the label of the part containing $1$, then the label of the part containing $2$, then the label of the part containing $3$, and so on. In the case of $(\{1,2,3\},\{4\})$, we write down $(1,1,1,2)$ because $1,2,3$ are all in part $\{1,2,3\}$, which has label $1$, but $4$ is in $\{4\}$, which has label $2$. In the case of $(\{1,4,8\}, \{2\}, \{3,6\}, \{5,7\})$, we write down $$ (1,2,3,1,4,3,4,1) $$ because, for example, $\{1,4,8\}$ is the partition with label $1$, so we write down a $1$ in the $1^{\text{st}}$, $4^{\text{th}}$, and $8^{\text{th}}$ positions.

---

To convert back, you just put all integers whose positions have the same label into the same part.