# Compact, reversible mapping from set partitions of length k to integers

Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\left[0, {n \brace k}\right)$.

Ideally this mapping and its inverse would be easy to compute.

• Use the recurrence formula for the number of partitions. – Yuval Filmus Aug 1 '16 at 6:05

The idea is to use the recurrence $$\newcommand{\stirling}{\genfrac{\{}{\}}{0pt}{}} \stirling{n}{k} = k \stirling{n-1}{k} + \stirling{n-1}{k-1}.$$ This recurrence holds since either element $n$ belongs to one of the $k$ partitions of a partition of $1,\ldots,n-1$ into $k$ parts (say, ordered by minimal element), or it forms a singleton partition, joining a partition of $1,\ldots,n-1$ into $k-1$ parts.
Accordingly, partition the range $[0,\stirling{n}{k})$ into $k$ parts of length $\stirling{n-1}{k}$ and one of length $\stirling{n-1}{k-1}$. Given a partition, determine which of the $k+1$ intervals you belong to, remove $n$, encode the remaining partition of $n-1$ recursively, and locate it inside the chosen interval. The base cases are $\stirling{0}{0} = 1$ and $\stirling{n}{0} = \stirling{0}{n} = 0$ for $n > 0$.
The same algorithm can be reversed and be used to decode a number in $[0,\stirling{n}{k})$ into a partition of $1,\ldots,n$ into $k$ parts.
• I'm stuck on the part where it's determined which of the $k+1$ intervals the partition belongs to. If my original set is $\{1,2,3,4,5\}$, and I have a partition $\{\{1,4,5\},\{2\},\{3\}\}$, that belongs to the interval "defined" by taking the union of $\{1\}$ and one of $\{4,5\}$, $\{2\}$, or $\{3\}$, but how do I determine which $k+1$ that belongs to? I mean clearly it doesn't belong to ${n-1 \brace k-1}$, but past that I can't figure it out. – Jordy Dickinson Aug 1 '16 at 22:24
• Well, my recursion actually removed $5$. After removing $5$, the partitions, ordered by their minimal element, are just as you wrote: $\{1,4\},\{2\},\{3\}$ (you can choose a different order if you want). So it belongs to the first copy of $\genfrac{\{}{\}}{0pt}{}{4}{3}$. – Yuval Filmus Aug 1 '16 at 22:27