# Lexographic Unranking of Combinations Revisited
## 3 Classical Unranking Algorithms
### Unranking through the Recursive Method  
We are dealing with a combinatorial structure here, combinations, that is well understood in the combinatorial sense. Thus, when trying to develop an unranking algorithm, the first idea consists in developing one based on the classical recursive generation method presented in [11]. This type of algorithm is based on a recursive decomposition of the structure into smaller parts. Here, this idea is to use the following fact: a combination of \(k\) elements among \(\{0,1,\ldots,n-1\}\) either contains \(n-1\) or does not. In the first case, the rest of the combination can be seen as a combination of \(k-1\) elements among \(n-1\) and in the second case the combination is a combination of \(k\) elements among \(n-1\). From a counting point of view, this translates into the well-known identity \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\) and, from an unranking point of view, this translates into Algorithm 3. ```
1:functionRecGeneration(\(n,k,u\))
2:if\(k=0\)then
3:return\([]\)
4:if\(n=k\)then
5:return\([0,1,2,\ldots,k-1]\)
6:\(b\leftarrow\textsc{binomial}(n-1,k-1)\)
7:if\(u<b\)then
8:\(R\leftarrow\textsc{RecGeneration}(n-1,k-1,u)\)
9:\(\textsc{append}(R,n-1)\)
10:return\(R\)
11:else
12:returnRecGeneration(\(n-1,k,u-b\))
```
**Algorithm 3** Recursive Unranking. **Remark 1**. : _An alternative choice would have been to test whether \(b<(n-1)\) on Line 6. This corresponds to putting first the combinations that do not contain \(n-1\) and then those that contain \(n-1\). In this case, the unranking order is different but the performance is similar._  
**Proposition 3**. : _The function \(\textsc{RecGeneration}(n,k,u)\) computes the \(u\)th combination of \(k\) elements among \(n\) for the reverse co-lexicographic order._  
**Corollary 2**. : _The function \(\textsc{UnrankingRecursive}(n,k,u)\) computes the \(u\)th combinations of \(k\) elements among \(n\) for the lexicographic order._  
Proof. : The proposition is proved by induction and the corollary is a direct observation given in [26] (p. 47). Here, again, we are interested in the average number of calls to the binomial function, when \(u\) describes the whole range of integers from \(0\) to \((n)-1\). [PERSON] justified such a measure by supposing the table of all binomial coefficients pre-computed, thus each call is equivalent. In Section 4, we discuss this measure. We introduce the sequence (to simplify the notations, we use several times the notations \(u_{n,k}\) and \(U(z)\) for distinct sequences and series) \(u_{n,k}\) equal to the cumulative number of calls to binomial for the whole range of possible values for \(u\). **Lemma 3**. : _Let \(u_{n,k}\) be the cumulative number of calls to binomial for the recursive unranking while unranking all possible \(u\) from \(0\) to \((n)-1\). The sequence satisfies: \(u_{n,0}=0\) and \(u_{n,n+i}=0\) for all \(n\) and \(i\geq 0\), and otherwise_  
\[u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}.\]  
Proof. : If \(0<k<n\), calling \(\textsc{RecGeneration}(n,k,u)\) incurs one call to binomial and a recursive call. The cumulative cost of the first call to binomial is \((n)\), the cumulative cost of the recursive calls for \(u<(n-1)\) is \(u_{n-1,k-1}\) and the cumulative costs of the recursive calls for \(u\geq(n-1)\) is \(u_{n-1,k}\). In the following Table 3, we give the first values of \(u_{n,k}\), when \(n\) is less than \(9\). **Theorem 4**. : _Let \(U(z,y)  
The proof of Theorem 4 is very similar to the one of Theorem 3. Proof. : The first step of the proof consists in exhibiting the ordinary generating function associated with \(U(z,y)\). To obtain the equation for \(U\), we start from the result presented in Lemma 3. The extreme cases are \(u_{n,0}=0\) and \(u_{n,n+i}=0\) for all \(n\) and \(i\geq 0\). The recursive equation is \(u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}\). Again, the numbers \(\binom{n}{k}\) appear in the equation, thus we need the bivariate generating function of binomial coefficients. Let us denote it by \(B(z,y)\).