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
3  
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

2 Answers 2

up vote 4 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.

UPDATE. In fact, there is a simpler way to enumerate combinations, using combinatorial number system of degree $k$. A $k$-combination $0\leq a_1 < a_2 < \dots < a_k < n$ here gets the order number: $$\binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}.$$

The properties of combinatorial number system ensure that this representation is a bijective mapping between $k$-combinations of $n$ and the integers in the interval $[0,\tbinom{n}{k}-1]$. In particular, given an integer $m$ in this interval, its representation in the combinatorial number system of degree $k$: $$m = \binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}$$ uniquely defines numbers $0\leq a_1 < a_2 < \dots < a_k < n$ (the last inequality follows from $m<\tbinom{n}{k}$), i.e., a $k$-combination of $n$.

share|improve this answer
    
Great answer. Could you provide the process for going in reverse, i.e. from a number to a combination? –  Andrew Mao Nov 11 at 19:45
    
@AndrewMao: It is easy to reverse the described recursive process to obtain the combination from a given number. But there is even a simpler way, which I described in the UPDATE. –  Max Alekseyev Nov 16 at 15:34

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

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.