2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jordy Dickinson Aug 1 '16 at 22:24
  • $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus Aug 1 '16 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.