4
$\begingroup$

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.

$\endgroup$
3

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Great answer. Could you provide the process for going in reverse, i.e. from a number to a combination? $\endgroup$
    – Andrew Mao
    Nov 11, 2014 at 19:45
  • $\begingroup$ @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. $\endgroup$ Nov 16, 2014 at 15:34
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Claudiu
    Jun 29, 2010 at 18:20
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 29, 2010 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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