1
$\begingroup$

I was wondering if there is a way to convert from any of the $$\binom{n + k - 1}{n}$$ combinations in a stars and bars setting to a unique number N with $$0 <= N < \binom{n+k-1}{n}$$ and viceversa from a number N to the same combination back.

I am assuming that bins are different, and the information about them must be preserved. I have found the wikipedia article on combinadics but it assumes that the combinations are sorted by size, which would lose the ordering information of the bins.

$\endgroup$
2
$\begingroup$

As explained in the stars and bars article, you are selecting $n$ places to put dividers out of $n+k-1$ so we can let $m=n+k-1$ and find a way to make a correspondence between a particular serial number and a particular selection. Of the $m \choose n$ combinations, ${m-1 \choose n-1}$ include $1$ and ${m-1 \choose n}$ do not. If we list the combinations in lexicographic order, the former will come before the latter, so if $N \lt {m-1 \choose n-1}$ we will include $1$ and if $N \ge {m-1 \choose n-1}$ we will not. In the first case we are looking for the $N^{th}$ combination of $n-1$ items out of $2,3,4,\ldots m$. In the second we are looking for the $N-{m-1 \choose n-1}^{th}$ combination of $n$ items out of $2,3,4,\ldots m$. This gives a nice recursive algorithm as one of the values has been reduced.

$\endgroup$
  • $\begingroup$ I think I've got how to convert a combination to N, I'm counting the number of combinations before my own for each specific element and recursing. I'll now try to understand how exactly to do the opposite. $\endgroup$ – Svalorzen Apr 9 '18 at 15:56

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.