# Lexographic Unranking of Combinations Revisited
## 5 Extensions of the Algorithmic Context  
### Objects Counted by Multinomial Coefficients  
Let \(n\) and \(m\) be two positive integers and let \(K=(k_{1},k_{2},\ldots,k_{m})\) be a finite sequence of non-negative integers whose sum equals \(n\). The multinomial coefficient \(\binom{n}{k_{1},\ldots,k_{m}}\) counts the number of ways of depositing \(n\) distinct objects into \(m\) distinct buckets such that there are \(k_{i}\) objects in the \(i\)th bucket. It can also be interpreted as combination with repetitions as follows. Consider we have a (large enough) pool of \(m\) kinds of different objects and we must pick a finite sequence of \(n\) objects from this pool such that \(k_{1}\) of them are of the first kind, \(k_{2}\) of the second kind, and so on. Figure 4: Merge of Algorithm 2 and its theoretical complexity. Note that, when \(m=2\), the multinomial coefficient corresponds to a binomial coefficient. Informally, Proposition 1 (related to combinations) states that combinations are in one-to-one correspondence with permutations containing two increasing runs. We have an analogous interpretation here. The ranks from \(0\) to \(\binom{n}{k_{1},\ldots,k_{m}}-1\) are in one-to-one correspondence with size-\(n\) permutations composed of \(m\) increasing runs. We now exhibit this link more formally. Proposition 4: _Let \(n\) and \(m\) be two positive integers and let \(K=(k_{1},k_{2},\ldots,k_{m})\) be a sequence of non-negative integers such that \(\sum_{i}k_{i}=n\). Each object enumerated by \(\binom{n}{k_{1},\ldots,k_{m}}\) is represented by a finite sequence \((\ell_{1},\ell_{2},\ell_{k_{m}})\) where for all \(1\leq i\leq m\), \(\ell_{i}\) is an increasing finite sequence of length \(k_{i}\). Furthermore, the union over \(i\) of all elements of \(\ell_{i}\) is exactly \(\{0,1,\ldots,n-1\}\)._  
Our unranking algorithm relies on the classical formula expressing the multinomial coefficient as a product of binomial coefficients. \[\binom{n}{k_{1},\ldots,k_{m}}=\binom{k_{m}}{k_{m}}\cdot\binom{k_{m}+k_{m-1}}{ k_{m-1}}\ldots\binom{k_{m}+\cdots+k_{2}}{k_{2}}\cdot\binom{k_{m}+\cdots+k_{1}}{k_ {1}}.\]
```
1:functionUnrankingCombinationWithRepetitions(\(n,K=(k_{1},\ldots,k_{m}),u\))
2:\(F\leftarrow[0,\ldots,0]\)\(\triangleright\)\(n\) components in \(M\)
3:\(u^{\prime}\gets u\)
4:\(n^{\prime}\gets k_{m}\)
5:for\(i\)from\(m-1\)downto\(1\)do
6:\(n^{\prime}\gets n^{\prime}+k_{i}\)
7:\(b\leftarrow\texttt{binomial}(n^{\prime},k_{i})\)
8:\((u^{\prime},u^{\prime\prime})\leftarrow\texttt{division}(u^{\prime},b)\)
9:\(F^{\prime}\leftarrow\texttt{factoradic}(\texttt{RankConversion}(n^{\prime},k_{ i},u^{\prime\prime}))\)
10:for\(j\)from\(0\) to \(k_{i}-1\)do
11:\(F[n^{\prime}-k_{i}+j]\gets F^{\prime}[n^{\prime}-k_{i}+j]\)
12:\(r\leftarrow\texttt{composition}(F)\)
13:returnUnrankingPermutation(\(n,r\))
```  
**Algorithm 8** Unranking a combination with repetitions. **Proposition 5**. : _The function UnrankingCombinationWithRepetitions(\(n,(k_{1},\ldots,k_{m}),u\)) computes the \(u\)th object counted by \(\binom{n}{k_{1},\ldots,k_{m}}\) in lexicographic order._  
The core of the algorithm consists in computing the rank of the permutation, written in factoradics, associated with the combination with repetitions we are interested in. It remains then to unrank a permutation. Proof. : Based on Proposition 4, the core of the algorithm computes the rank of a permutation containing \(m\) increasing runs respectively of lengths \(k_{1},k_{2},\ldots,k_{m}\). Determining the contribution of each run in the factoradic decomposition of the permutation rank is done in the external loop starting in Line 5, from \(k_{m}\) down to \(k_{1}\). The correctness of our algorithm relies on the following loop invariant:  
* The values of \(f_{j}\) for all \(0\leq j<k_{m}+\cdots+k_{i+1}\) have been computed and stored in \(F\).