## 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 2010 at 18:09
There was a related question: mathoverflow.net/questions/24481 – Wadim Zudilin Jun 30 2010 at 0:13
You might consult Knuth's TAOCP 4.3 "Generating all Combinations and Partitions" amazon.co.uk/… but perhaps you'll find there more information than you ever wanted to know :-) – Robin Chapman Jun 30 2010 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.

-

Well, yes, in the sense that dividing 26 by 12 choose 2 immediately tells you that 0 is the first digit. Dividing 26 by 11 choose 1 indicates that the second digit is 3. Subtracting 12 + 11 from 26 indicates that you should take the third of the (0, 3, ?) numbers, which is (0, 3, 6). This all looks quite algorithmic: you need to divide and take remainders by certain binomial coefficients or their sums.

-
I can follow that process to go from the number to the combination, but what about reversed? I tried following the approach here en.wikipedia.org/wiki/Combinatorial_number_system , under "Place of a combination in the ordering", but it doesn't seem to work, e.g. (0, 1, 4) should have rank 2, but (0 choose 1 + 1 choose 2 + 4 choose 3) yields 4. – Claudiu Jun 29 2010 at 18:20
The correct order of the subsets is 012, 013, 023, 123, 014, ... (reverse lex order). The first subset 012 is defined to have rank 0. Thus 014 does have rank 4. – Richard Stanley Jun 29 2010 at 19:55