# 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.

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.