Rang d'une Combinaison

Le rang d'une combinaison est la position d'une combinaison dans la liste de toutes les combinaisons possibles triées par ordre croissant.

Exemple : Toutes les combinaisons de 2 éléments parmi 4 sont : (1,2),(1,3),(1,4),(2,3),(2,4),(3,4), donc le rang de la combinaison (1,2) est 1, le rang de la combinaison (2,4) est 5

Avec $ c_i $ les éléments par ordre croissant $ c_1, c_2, \cdots, c_k $ d'une combinaison de $ k $ éléments et $ n $ le nombre total d'éléments, la formule pour calculer le rang sans avoir à lister toutes les combinaisons est $$ \binom{n}{k} - \binom{n-c_1}{k} - \binom{n-c_2}{k-1} - \cdots - \binom{n-c_k}{1} $$

Exemple : Calculer le rang de la combinaison (1,3) parmi les combinaisons de 2 parmi 4 $ \binom{4}{2} $, c'est prendre $ n = 4, k = 2, c_1 = 1, c_2 = 3 $ et calculer $$ \binom{4}{2} - \binom{4-1}{2} - \binom{4-3}{2-1} = 6 - 3 - 1 = 2 $$ donc (1,3) est au rang 2.

Cette méthode calcule la combinaison minimale minimisant $ n $ (ie. avec les plus petit nombres) pour une taille donnée $ k $.

Pour calculer une combinaison à partir d'un rang $ r $, déterminer le nombre d'élément $ k $ de la combinaison et répéter l'algorithme suivant :

1 - Calculer le plus grand nombre $ i $, tel que le nombre de combinaisons $ \binom{k}{i} $ soit inférieur ou égal au rang $ r $.

2 - Ajouter $ i $ au début de la combinaison, soustraire la valeur $ \binom{k}{i} $ au $ r $ et décrémenter $ k $ de $ 1 $

3 - Répéter les étapes 1 et 2 tant que $ k > 0 $

Exemple : Pour un rang $ r = 5 $ et une combinaison de $ k = 2 $ éléments
Etape 1 - calculer $ \binom{2}{2} = 1 < r $, $ \binom{3}{2} = 3 < r $ puis $ \binom{4}{2} = 6 > r $
Etape 2 - Combinaison = (4), $ r = 5-3 = 2 $, $ k = 1 $
Etape 1' - calculer $ \binom{1}{2} = 2 <= r $
Etape 2' - Combinaison = (2,4), $ r = 1 $, $ k = 0 $ - Fin
Donc la combinaison minimale de taille 2 et de rang 5 est (2,4)