# Order of a combination when mapping them to whole numbers

You can map whole numbers to combinations when taking them in order. For example, 13 choose 3 would look like:

0 --> (0, 1, 2)
1 --> (0, 1, 3)
2 --> (0, 1, 4)
etc...


Given a particular combination, such as (0, 3, 9), is there a way to determine which whole number maps to it (26, in this case), short of writing out all the combinations in order until I hit upon the proper one? Furthermore, is there a way of doing this when counting combinations with repetitions?

If anyone is wondering, this isn't homework, but for a personal programming project.

-
this is usually called ranking and unranking. Searching the web with "combinations, ranking, unranking" should give you some hints. Possibly you find 1stworks.com/ref/RuskeyCombGen.pdf helpful. –  Martin Rubey Jun 29 '10 at 18:09
There was a related question: mathoverflow.net/questions/24481 –  Wadim Zudilin Jun 30 '10 at 0:13
You might consult Knuth's TAOCP 4.3 "Generating all Combinations and Partitions" amazon.co.uk/Art-Computer-Programming-Fascicle-Combinations/dp/… but perhaps you'll find there more information than you ever wanted to know :-) –  Robin Chapman Jun 30 '10 at 17:58

Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).

Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:

if $a_1 = 0$, then $$N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$

if $a_1 > 0$, then $$N(n;a_1,\dots,a_k) = \binom{n-1}{k-1} + N(n-1;a_1-1,a_2-1,\dots,a_k-1).$$

with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.

For example, $$N(13;0,1,4) = N(12;0,3) = N(11;2) = \binom{10}{0} + N(10;1)$$ $$= \binom{10}{0} + N(10;1) = \binom{10}{0} + \binom{9}{0} + N(9;0)$$ $$=\binom{10}{0} + \binom{9}{0} + N(8;) = 1 + 1 + 0 = 2$$ as required.

-