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 : Le rang de combinaison (1,3) parmi les combinaisons \( \binom{4}{2} \) se calcule \( \binom{4}{2} - \binom{3}{2} - \binom{1}{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 \), il faut connaitre 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)