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.



Order of a combination when mapping them to whole numbers
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](https://en.wikipedia.org/wiki/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$.


