# Convert stars-and-bars combination to number N and back

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.

## 1 Answer

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.

• 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. – Svalorzen Apr 9 '18 at 15:56