FR

Combinaisons, arrangements et factorielle

Combien de façons de choisir, de classer ou d'ordonner des éléments ? Le dénombrement répond avec trois outils : la factorielle, les arrangements (l'ordre compte) et les combinaisons (l'ordre est indifférent). Indiquez le nombre total n et le nombre choisi k, avec ou sans répétition.

La question clé : l'ordre compte-t-il ? Un podium (or, argent, bronze) est un arrangement — l'ordre distingue les résultats. Une poignée de cartes ou des numéros de loto sont une combinaison — seul l'ensemble compte, pas l'ordre du tirage.

Données

Type de dénombrement

Changez de mode puis relancez le calcul pour adapter les champs.

Combinaisons C(n, k) — tirage non ordonné

Le stock dans lequel on choisit.

Entre 0 et n (sans répétition).

Résultat

  • C(49, 6) 13 983 816
n (éléments disponibles) 49
k (éléments choisis) 6
Combinaisons sans répétition C(n, k) 13 983 816
Combinaisons avec répétition C(n+k−1, k) 25 827 165

C(n, k) = n! / [ k! · (n − k)! ]

Ordre ou pas d'ordre : tout est là

Le dénombrement repose sur une brique unique, la factorielle. n! compte les façons d'ordonner n éléments distincts : n choix pour la première place, n − 1 pour la deuxième, n − 2 pour la troisième, jusqu'à 1. Trois livres sur une étagère, 3 × 2 × 1 = 6 rangements. Dix livres, 3 628 800. La factorielle n'est pas une curiosité de lycée, c'est le compteur de toutes les files possibles.

A(n, k) = n! / (n − k)!  ·  C(n, k) = A(n, k) / k! = n! / [k! · (n − k)!]

Arrangements et combinaisons en découlent. La seule question qui tranche, c'est : l'ordre compte-t-il ? Un podium, oui. Une main de poker, non. Un code PIN, oui. Une grille de loto, non. Disons-le autrement : si permuter les objets déjà choisis crée un résultat nouveau, nous sommes en arrangement. Si ça reste le même paquet, nous sommes en combinaison. Tout le reste de la page n'est que le développement de cette alternative, avec ou sans remise.

Arrangement : l'ordre compte

Un arrangement A(n, k) compte les façons de tirer k éléments parmi n en tenant compte de l'ordre. Nous ne divisons par rien : la première place n'est pas la deuxième. Un podium de 3 parmi 8 athlètes, c'est A(8, 3) = 8 × 7 × 6 = 336 podiums. Alice-Bob-Chloé n'est pas Bob-Alice-Chloé. Le tiercé dans l'ordre, un classement, un mot de passe sans lettre répétée, une file d'attente nominative : même famille.

Autrement dit, A(n, k) est une factorielle tronquée. Nous n'allons pas jusqu'à 1, nous nous arrêtons après k facteurs. A(n, n) = n!, toutes les permutations. A(n, 1) = n. A(n, 0) = 1, la façon de ne rien ranger : il y en a une, la façon vide.

Le formulaire, mode « arrangements », sans répétition, c'est exactement ça. Huit coureurs, trois marches, 336. Passez à 10 coureurs, A(10, 3) = 720. Le double d'athlètes ne double pas les podiums, il les multiplie par 10 × 9 × 8 / (8 × 7 × 6) = 720/336 ≈ 2,14. Les factorielles ne sont pas linéaires, et c'est tout le sel du dénombrement.

Combinaison : l'ordre est indifférent

Une combinaison C(n, k) compte les façons de tirer k éléments parmi n sans se soucier de l'ordre. Nous prenons l'arrangement, puis nous divisons par k! : le nombre d'ordres possibles des k élus. Alice-Bob-Chloé, Bob-Alice-Chloé et les quatre autres permutations, c'est une équipe de trois, pas six. C(8, 3) = 336 / 6 = 56 équipes.

La main de poker à 5 cartes parmi 52 est le grand classique : C(52, 5) = 2 598 960 mains. L'ordre dans lequel le croupier les pose n'a aucune importance, le jeu les relit ensuite. Parmi ces 2,6 millions, 4 quintes flush royales, 36 autres quintes flush, 624 carrés, 3 744 fulls, 5 108 couleurs (hors quinte flush). Une paire « quelconque » est déjà beaucoup plus fréquente : 1 098 240 mains, soit un peu plus de 42 %. La rareté d'une main, c'est exactement 1 / C(52, 5) multiplié par le nombre de façons de la composer — pas une aura, un rapport.

Pour autant, C(n, k) = C(n, n − k). Choisir 5 cartes à garder, c'est choisir 47 à laisser. Le calculateur s'en sert : il prend min(k, n − k) pour garder les produits petits. Saisir C(52, 47) doit redonner 2 598 960, pas un autre monde.

Avec ou sans répétition, avec ou sans remise

Sans répétition, chaque élément ne sort qu'une fois. C'est le tirage sans remise, celui du loto, du poker, du podium : les A(n, k) et C(n, k) classiques. Avec répétition, un élément peut resservir. Tirage avec remise, ou simples réutilisations (chiffres d'un PIN, lettres d'un mot de passe).

  • Arrangements avec répétition — nk. Un PIN à 4 chiffres, 10 symboles, répétition autorisée : 104 = 10 000. Sans répétition, ce serait A(10, 4) = 10 × 9 × 8 × 7 = 5 040. La case « avec répétition » du formulaire, c'est ce saut-là.
  • Combinaisons avec répétition — C(n + k − 1, k). Trois boules glacées parmi 5 parfums, l'ordre dans le cornet indifférent, le double chocolat autorisé : C(5 + 3 − 1, 3) = C(7, 3) = 35. Formule des « étoiles et barres », moins intuitive, indispensable dès que nous composons un sac, pas une file.

avec répétition : A = nk  ·  C = C(n + k − 1, k)

La remise se voit dans l'expérience. Une urne, nous tirons et nous remettons la boule : le tirage suivant a encore n choix, d'où nk si l'ordre compte. Nous ne remettons pas : n, puis n − 1, puis n − 2. Confondre les deux sur un oral, c'est doubler un PIN ou oublier qu'une grille de loto n'a pas deux fois le 7. Le formulaire a une case pour ça, ce n'est pas un ornement.

Loto 6/49 : 13 983 816 grilles

Au loto « 6 numéros parmi 49 », l'ordre du tirage ne compte pas, et un numéro ne sort qu'une fois. Nous sommes en combinaisons sans répétition. Le nombre de grilles possibles est C(49, 6) = 13 983 816. La probabilité de coller le tirage exact, une grille, une fois, est 1 sur près de 14 millions. Saisissez n = 49, k = 6, mode combinaisons, sans répétition : le calculateur doit afficher ce 13 983 816, pas un cousin.

C(49, 6) = (49 × 48 × 47 × 46 × 45 × 44) / 6! . Le 6! au dénominateur, c'est encore k! : les 720 ordres dans lesquels six boules auraient pu sortir. Les publicités parlent de « combinaison gagnante », et pour une fois le mot est le mot juste. Ce n'est pas un arrangement. Inverser deux numéros sur le bulletin ne crée pas une grille nouvelle.

Le Loto de la FDJ, depuis 2008, n'est plus un 6/49 pur : 5 numéros parmi 49, plus un numéro Chance parmi 10. Ça fait C(49, 5) × 10 = 19 068 840 grilles de rang 1. Plus que 13,98 millions, pas le même jeu. Le 6/49 reste l'exemple des manuels, celui de cette page, celui que nous tapons pour vérifier un coefficient binomial. Les deux chiffres peuvent cohabiter dans une conversation, à condition de nommer la règle.

EuroMillions : deux urnes, un jackpot

L'EuroMillions empile deux combinaisons indépendantes : 5 numéros parmi 50, et 2 étoiles parmi 12. L'ordre, là encore, ne compte pas. Le nombre de grilles de rang 1 vaut donc le produit :

C(50, 5) × C(12, 2) = 2 118 760 × 66 = 139 838 160

Un peu moins de 140 millions. Dix fois le 6/49, à peu de chose près. C(50, 5) se calcule ici avec n = 50, k = 5. C(12, 2) avec n = 12, k = 2. Le produit, la page ne le fait pas toute seule : deux allers-retours, une multiplication. Voilà le geste, dès qu'un jeu a deux urnes (numéros + étoiles, numéros + Chance, boules + couleur).

La probabilité d'un rang 1, une grille, un tirage, est 1/139 838 160. Ce n'est pas une loi normale, pas une cloche, pas un « z-score du jackpot ». C'est une loi uniforme sur un ensemble fini énorme, et le dénombrement en donne le cardinal. Les rangs inférieurs (5 numéros sans étoile, 2 étoiles seules, etc.) se comptent pareil, en changeant k, parfois en soustrayant les cas déjà classés plus haut. Le calculateur fournit les C(n, k) ; le barème du jeu, lui, dit lesquels multiplier.

Mots de passe, codes PIN, et pourquoi la longueur gagne

Un mot de passe est un arrangement avec répétition, sauf politique contraire (certains systèmes interdisent le caractère répété, et tombent alors sur A(n, k)). Alphabet de 26 lettres minuscules, longueur 8 : 268 = 208 827 064 576. Ajoutez majuscules et chiffres, 628 ≈ 2,18 × 1014. Passez à longueur 12, 6212 ≈ 3,23 × 1021. La longueur pèse plus que l'alphabet : un caractère de plus multiplie par 62, alors qu'ajouter les 32 symboles de ponctuation à un mot de 8 signes ne multiplie que par (94/62)8 ≈ 28.

Disons-le sur un PIN, plus petit, plus parlant. 4 chiffres, avec répétition (le cas réel des distributeurs) : 10 000. Sans répétition : 5 040. 6 chiffres avec répétition : 1 000 000. Le « code à 4 chiffres » n'est pas « un peu plus faible » qu'un code à 6, il est cent fois plus petit. Mode arrangements, avec répétition, n = 10, k = 4 ou 6 : le formulaire y va tout droit.

En résumé, trois pièges. Compter comme une combinaison un mot de passe (l'ordre des lettres fait le mot). Oublier la répétition (le e de « motdepasse » revient, 26k pas A(26, k)). Croire qu'un alphabet plus riche rattrape un mot trop court. Le dénombrement, ici, n'est pas un exercice : c'est la taille de l'espace que l'attaquant doit parcourir.

Ank, Cnk, nPk : trois écritures, même objet

Les manuels français de lycée écrivent le plus souvent Ank et Cnk, parfois A(n, k) et C(n, k) comme cette page. Les textes anglo-saxons, les tableurs, les langages, parlent de nPk (ou P(n, k), permutations) et nCk (ou C(n, k), n choose k). Le coefficient binomial se note aussi (n k) en colonne, lu « k parmi n ». Simplement, ce n'est pas un autre calcul. C'est la même formule, d'autres glyphes.

  • Arrangements — Ank = A(n, k) = nPk = P(n, k) = n! / (n − k)!
  • Combinaisons — Cnk = C(n, k) = nCk = (n k) = n! / [k! (n − k)!]
  • Permutations de n objets — n! = Ann = nPn. Tous les rangements.

Un piège de vocabulaire : l'anglais permutation recouvre souvent nos arrangements (k parmi n ordonnés), pas seulement n!. Un autre, français celui-là : certains ouvrages écrivent Anp avec p pour notre k, et parlent de « p-listes » pour np (arrangements avec répétition). Avant de recopier une formule d'un corrigé trouvé en ligne, nous regardons si p est le petit indice ou l'alphabet. Cette page s'en tient à n = taille de l'ensemble, k = taille du tirage.

Excel : PERMUTATION(n ; k) sort A(n, k) sans répétition, PERMUTATIONA sort nk, COMBIN(n ; k) sort C(n, k), COMBINA sort C(n + k − 1, k). Les quatre cases du formulaire ont leur fonction. Un écart entre Excel et cette page, sur les mêmes n et k, signale presque toujours une case répétition mal cochée, pas une divergence de définition.

170! et le plafond des flottants

Les factorielles grandissent vertigineusement. 10! = 3 628 800, encore lisible. 20! ≈ 2,43 × 1018. 70! dépasse déjà le nombre d'atomes estimé dans la galaxie, pour donner une image, pas une mesure. 170! ≈ 7,26 × 10306 frôle la limite des nombres à virgule flottante double précision (environ 1,8 × 10308). 171! bascule : le calculateur signale un dépassement, il ne « calcule pas faux », il sort du format.

D'où le calcul itératif, plutôt que d'écrire n! / (n − k)! en construisant trois factorielles énormes pour les diviser ensuite. A(n, k) se fait en k multiplications. C(n, k) aussi, en réduisant au fur et à mesure par 1, 2, …, k. Les intermédiaires restent plus petits, et C(1000, 2) = 499 500 tombe sans réveiller 1000!. Au-delà d'environ 1015, le résultat s'affiche en notation scientifique : les entiers exacts ne tiennent plus dans la mantisse, les premières décimales restent justes, les dernières non.

Un affichage en 1,234567 × 1020 n'est plus un entier compté un par un. Pour un loto, C(49, 6) = 13 983 816 tient encore dans l'entier. Pour 170!, nous lisons un ordre de grandeur. Au-delà, le message de dépassement est la réponse, pas un bug.

En résumé, le dénombrement exact a un plafond, celui de la machine. Les identités (C(n, k) = C(n, n − k), le produit itératif, le min(k, n − k)) reculent ce plafond, elles ne l'abolissent pas. Si le problème demande 500! pile, il nous faut un outil de grands entiers, pas une page web en virgule flottante. Pour les tirages du quotidien — loto, poker, PIN, équipes, codes — nous sommes très en dessous, et le formulaire suffit.

Voir aussi