# Lexographic Unranking of Combinations Revisited
## 2 Unranking through Factoradics: A New Strategy
### Combinations Unranking through Factoradics
The bijection between both structures is direct, and thus we provide new information about this sequence in the following. Proof. : The recurrence can be observed by unrolling the first iteration of the while loop. In the first iteration of the loop, a binomial coefficient \(b\) is always computed (regardless the value of \(k\) and \(n\)) which accounts for the term \(\binom{n}{k}\) in the recurrence relation. Then, for all the ranks \(u\) such that \(u<b\), we choose \(f_{n-1}=0\) and increment \(i\), so that the rest of the execution corresponds to unranking a combination of \(k-1\) elements among \(n-1\). This is accounted for by \(u_{n-1,k-1}\). Conversely, for all ranks \(u\) such that \(u\geq b\), the value of \(m\) is incremented and the rest of the execution corresponds to unranking a combination of \(k\) elements among \(n-1\), which is accounted for by \(u_{n-1,k}\). We turn to bivariate generating functions to encode the sequence \((u_{n,k})\) as a power series and express the above recurrence as a simple equation satisfied by this function, which can be solved explicitly. The reader can refer to the two books of [PERSON] and [PERSON] [24; 25] for a global presentation of such method. \begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline \(k\) & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline
1 & 0 & 1 & & & & & & & \\
2 & 0 & 3 & 2 & & & & & & \\
3 & 0 & 6 & 8 & 3 & & & & & \\
4 & 0 & 10 & 20 & 15 & 4 & & & & \\
5 & 0 & 15 & 40 & 45 & 24 & 5 & & & \\
6 & 0 & 21 & 70 & 105 & 84 & 35 & 6 & & \\
7 & 0 & 28 & 112 & 210 & 224 & 140 & 48 & 7 & \\
8 & 0 & 36 & 168 & 378 & 504 & 420 & 216 & 63 & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: First values of \(u_{n,k}\) for \(n=1\ldots 8\) and \(k=0\ldots n\) (Algorithm 2). **Theorem 3**. : _Let \(U(z,y)\) be the generating functions associated with \((u_{n,k})\). Then,_  
\[U(z,y) =\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{1}{1-z}\bigg{)};\text { thus}\] \[u_{n,k} =\binom{n}{k}\frac{k}{k+1}(n+1).\]  
Proof. : The first step of the proof consists in exhibiting the ordinary generating function associated with \(U(z,y)\). To obtain a functional equation satisfied by \(U\), we start from the result presented in Lemma 2. The extreme cases are \(u_{n,0}=0\) and \(u_{n,n+i}=0\) for all \(n\) and \(i>0\). The recursive equation is \(u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}\). We remark the constant \(\binom{n}{k}\) in the equation. We thus need the bivariate generating function of binomial coefficients. Let us denote it by \(B(z,y)\), which is equal to  
\[B(z,y)=\sum_{n\geq 0}\sum_{k=0}^{n}\binom{n}{k}z^{n}\ y^{k}=\frac{1}{1-z-zy}.\]  
To take into account the extreme cases, we must remove the terms corresponding to \(k=0\):  
\[\tilde{B}(z,y)=\frac{1}{1-z-zy}-\frac{1}{1-z}.\]  
By summing both sides of the recursive relation and by taking care of the extreme cases, we get:  
\[\sum_{n\geq 1}\sum_{k=1}^{n}u_{n,k}z^{n}\ y^{k} =\tilde{B}(z,y)+\sum_{n\geq 1}\sum_{k=1}^{n}u_{n-1,k-1}z^{n}\ y^{k}+ \sum_{n\geq 1}\sum_{k=1}^{n}u_{n-1,k}z^{n}\ y^{k}\] \[U(z,y) =\tilde{B}(z,y)+z\ y\ U(z,y)+z\ U(z,y).\]  
We thus deduce  
\[U(z,y)=\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{1}{1-z}\bigg{)}.\]  
The second step in the proof consists in extracting the coefficient \(u_{n,k}\). We rewrite \(U(z,y)\) as:  
\[U(z,y) =\frac{1}{1-z(1+y)}\bigg{(}\frac{1}{1-z(1+y)}-\frac{1}{1-z}\bigg{)}\] \[=\left(\sum_{r\geq 0}z^{r}(1+y)^{r}\right)\cdot\left(\sum_{r\geq 0 }z^{r}(1+y)^{r}-\sum_{r\geq 0}z^{r}\right)\] \[U(z,y) =\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{1}{1-z}\bigg{)};\text { thus}\]0  
By extraction, the coefficient in front of \(z^{n}\) is:  
\[U(z,y) =\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{1}{1-z}\bigg{)};\text { thus}\]1 \[U(z,y) =\frac{1}{1-z-zy}\bigg{(}\frac{1}{1-z-zy}-\frac{1}{1-z}\bigg{)};\text { thus}\]2The latter result corresponds to the distribution of the costs when \(k\) varies from \(0\) to \(n\).