Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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 '10 at 18:20
1  
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 '10 at 19:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.