Outil pour calculer le rang d'une combinaison mathématique (ou inversement, calculer une combinaison à partir d'un rang), c'est-à-dire la position d'une combinaison dans la liste croissante des combinaisons possibles générées.
Rang d'une Combinaison - dCode
Catégorie(s) : Combinatoire
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Rang d'une Combinaison
Calcul du Rang à partir d'une Combinaison
Calcul d'une Combinaison à partir d'un Rang
Réponses aux Questions (FAQ)
Comment calculer le 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.
Comment calculer une combinaison à partir de son rang ?
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)
Code source
dCode se réserve la propriété du code source pour "Rang d'une Combinaison". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Rang d'une Combinaison", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Rang d'une Combinaison" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Rang d'une Combinaison" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Citation
Le copier-coller de la page "Rang d'une Combinaison" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous citez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Rang d'une Combinaison sur dCode.fr [site web en ligne], consulté le 05/05/2024,
