# Lexographic Unranking of Combinations Revisited
## 3 Classical Unranking Algorithms
### Unranking through Combinatics
First note that, the values \(n\) and \(k\) being given, the worst cases are obtained when \(v\) gets as small as possible at the end of the loop, thus for all \(u\) whose combinadic satisfies \(c_{1}=0\). Hence, the worst case complexity is \(n-1\). Again, we complete this analysis, by computing the average complexity of the algorithm. To reach this goal, we again introduce the sequence \(u_{n,k}\) computing the cumulative number of calls to binomial when \(u\) ranges from \(0\) to \(\binom{n}{k}-1\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Rank, \(u\)** & **Reversed Rank, \(u^{\prime}=\binom{6}{2}-1-u\)** & **Combinadic of \(u^{\prime}\)** & **Combination of Rank \(u\)** \\ \hline
0 & 14 & (4, 5) & (0, 1) \\
1 & 13 & (3, 5) & (0, 2) \\
2 & 12 & (2, 5) & (0, 3) \\
3 & 11 & (1, 5) & (0, 4) \\
4 & 10 & (0, 5) & (0, 5) \\
5 & 9 & (3, 4) & (1, 2) \\
6 & 8 & (2, 4) & (1, 3) \\
7 & 7 & (1, 4) & (1, 4) \\
8 & 6 & (0, 4) & (1, 5) \\
9 & 5 & (2, 3) & (2, 3) \\
10 & 4 & (1, 3) & (2, 4) \\
11 & 3 & (0, 3) & (2, 5) \\
12 & 2 & (1, 2) & (3, 4) \\
13 & 1 & (0, 2) & (3, 5) \\
14 & 0 & (0, 1) & (4, 5) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Combinidics and their combinations for \(n=6\) and \(k=2\). **Lemma 4**. : _Let \(u_{n,k}\) be the cumulative numbers of calls to binomial while unranking all possible \(u\) from \(0\) to \(( \begin{subarray}{c}n\\ k\end{subarray} )-1\). The sequence satisfies: \(u_{n,0}=1\) and \(u_{n,n+i}=0\) for all \(n\) and \(i>0\), and otherwise_  
\[u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}.\]  
Table 5 presents the sequence given in Lemma 4. The difference with the two sequences studied before lies in the extreme cases. This sequence is a shifted version of the sequence OEIS A264751. Both combinatorial objects can be put in bijection, and thus some conjectures stated there are solved in the following. Proof. : Note that \(n-c_{k}\) calls to binomial are necessary to determine \(c_{k}\), then \(c_{k}-c_{k-1}\) calls to determine \(c_{k-1}\),..., and finally \(c_{2}-c_{1}\) to determine \(c_{1}\). Hence, the total number of binomial coefficients evaluations necessary to compute the combinadic of \(u\) is \(n-c_{1}\) (and thus only depends on \(c_{1}\)). Besides, for a given \(j\geq 0\), the number of finite sequences \(c_{1}=j<c_{2}<c_{3}<\cdots<c_{k}<n\) is equal to the number of sequences \(0\leq c_{2}^{\prime}<c_{3}^{\prime}<\cdots<c_{k}<n-j-1\) by the change of variable \(c_{i}^{\prime}\gets c_{i}-j-1\). Hence, this number is equal to \(\binom{n-1-j}{k-1}\). In addition, there is a first call to binomial at the beginning of the algorithm to reverse the rank, regardless of the value of \(u\). We thus obtain:  
\[u_{n,k}=\binom{n}{k}+\sum_{j=0}^{n-k}(n-j)\cdot\binom{n-j-1}{k-1}.\]  
Using the latter equation, the recursive equation is directly proved by induction. Note that in this case the cumulative numbers are not symmetrical \(u_{n,k}\
eq u_{n,n-k}\). In fact, the computation of the combinadics is not symmetrical. **Theorem 6**. : _Let \(U(z,y)\) be the generating function associated with \((u_{n,k})\). Then,_  
\[U(z,y) =\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{z}{1-z}\bigg{)};\; thus\] \[u_{n,k} =\binom{n}{k}\bigg{(}n+1-\frac{n-k}{k+1}\bigg{)}.\]  
The proof is the same as for Theorem 3. The values for \(u_{n,k}\) are a bit different due to the extreme cases \(u_{n,0}\). \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \(n\) & \(k\) & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline
2 & 1 & 5 & 3 & & & & & & \\
3 & 1 & 9 & 11 & 4 & & & & & \\
4 & 1 & 14 & 26 & 19 & 5 & & & & \\
5 & 1 & 20 & 50 & 55 & 29 & 6 & & & \\
6 & 1 & 27 & 85 & 125 & 99 & 41 & 7 & & \\
7 & 1 & 35 & 133 & 245 & 259 & 161 & 55 & 8 & \\
8 & 1 & 44 & 196 & 434 & 574 & 476 & 244 & 71 & 9 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: First values of \(u_{n,k}\) for \(n=1\ldots 8\) and \(k=0\ldots n\) (Algorithm 4). **Corollary 4**.