Dénombrement

Dénombrement: permutations, arrangements, combinaisons

Compter sans tout écrire. On choisit des objets : les prend-on tous ou seulement une partie ? L'ordre compte-t-il ? Peut-on reprendre le même ? Trois questions, trois formules — et chaque nombre de cette page est aussi obtenu en énumérant réellement les cas, un par un.

A_n^k = n !(n − k) ! (nk) = C_n^k = n !k ! (n − k) !

L'arrangement retient l'ordre · la combinaison l'oublie, en divisant par les k ! façons de ranger un même paquet.

Une seule règle : multiplier les choix

Au restaurant, on choisit une entrée, puis un plat, puis un dessert. Si la carte propose a entrées, b plats et c desserts, chaque entrée peut s'associer à chacun des plats, et chaque couple à chacun des desserts : il y a a × b × c menus. C'est le principe multiplicatif : quand des choix se font l'un après l'autre, leurs nombres se multiplient. Tout ce cahier en découle.

Arbre des menus : chaque chemin du départ à une feuille du bas est un menu. Le chemin rouge visite les feuilles une à une ; les feuilles déjà atteintes deviennent bleues.

Entrées2

Plats3

Desserts2

Menu affiché

—

Feuilles déjà visitées

—

Feuilles de l'arbre, comptées une à une

—

Principe multiplicatif

—

Les trois familles étudiées ensuite ne sont que trois façons d'appliquer cette règle :

On prend…	L'ordre compte ?	Nom	Nombre	Exemple
les n objets	oui	permutation	n!	ranger 8 livres sur une étagère
k objets parmi n	oui	arrangement	n! ÷ (n − k)!	le tiercé dans l'ordre
k objets parmi n	non	combinaison	n! ÷ (k! (n − k)!)	une grille de loto

Le principe multiplicatif. Si un premier choix offre n₁ possibilités, et que pour chacune d'elles un second en offre n₂, alors les deux choix successifs en offrent n₁ × n₂. C'est tout, et tout le reste en découle.

Avec remise, chaque étage de l'arbre a la même largeur : n × n × … = n^k. Sans remise, l'objet tiré disparaît et chaque étage se rétrécit d'une unité : n(n−1)(n−2)… soit k facteurs décroissants. Ce second produit est l'arrangement, que l'on écrit aussi n ! / (n−k) ! — l'écriture factorielle est plus courte, le produit décroissant est plus honnête sur ce qui se passe.

Permutations : ranger tous les objets

Une permutation de n objets est une façon de les ranger tous, l'un après l'autre. Pour la première place, on a n choix ; pour la deuxième, il n'en reste que n − 1 ; et ainsi de suite jusqu'au dernier objet, qui n'a plus le choix. Le nombre de rangements est donc le produit de tous les entiers de n à 1, que l'on note n! et que l'on lit « factorielle n ».

n! = n × (n − 1) × (n − 2) × … × 2 × 1

Objets

Vitesse

Les jetons prennent tous les ordres possibles, rangés comme dans un dictionnaire (ordre « lexicographique »). Sous chaque case : le nombre de jetons encore disponibles au moment où on la remplit.

Mosaïque : chaque colonne est une permutation déjà énumérée, lue de haut en bas. La première ligne se découpe en n blocs, chacun se recoupe en n − 1 blocs dans la deuxième ligne, puis en n − 2… : le produit n! devient visible. Quand les colonnes sont plus nombreuses que les pixels, les dernières lignes se brouillent : elles changent presque à chaque colonne.

Rangements déjà affichés

—

Liste complète produite par l'algorithme

—

Formule n!

—

Écart liste − formule

—

Stirling

—

Quand certains objets sont identiques — les lettres d'un mot comme ANANAS —, des rangements se confondent. Si une lettre apparaît 3 fois, ses 3! = 6 ordres internes donnent le même mot : on divise n! par la factorielle de chaque répétition. L'algorithme du dictionnaire, lui, ne produit jamais deux fois le même mot : il compte directement les anagrammes distinctes.

À retenir. n! grandit très vite : 10! dépasse 3,6 millions, 20! vaut environ 2,4·10¹⁸. On ne compte jamais les permutations une à une : on multiplie les choix restants. La formule de Stirling, n! ≈ √(2πn) (n/e)ⁿ, en donne l'ordre de grandeur, avec une erreur relative proche de 1/(12n).

Arrangements : remplir seulement k places

Un arrangement de k objets pris parmi n est une liste ordonnée de k objets différents : on ne remplit que k places. Le produit des choix restants s'arrête donc après k facteurs. Exemple type : le tiercé, où l'on désigne dans l'ordre les trois premiers chevaux d'une course. Si l'on a le droit de reprendre le même objet — les chiffres d'un code de cadenas —, chaque place offre à nouveau n choix : on obtient n^k listes.

A(n, k) = n × (n − 1) × … × (n − k + 1) = n!(n − k)!

n (participants)10

k (places)3

avec répétition (code)

Un arrangement tiré au hasard se construit place par place. Au-dessus de chaque case, en vert, le nombre de choix possibles à cet instant ; en bas, le produit se forme facteur par facteur.

Nombre de listes pour chaque valeur de k, en échelle logarithmique : barre bleue sans répétition, contour orange avec répétition. La valeur choisie est entourée de rouge. Les deux dernières barres bleues sont égales : quand n − 1 objets sont placés, le dernier n'a plus le choix.

A(n, k) = n! ÷ (n − k)!

—

Énumérés un à un

—

Avec répétition : nᵏ

—

Deviner au hasard

—

L'ordre fait la différence. 1-2-3 et 3-2-1 sont deux tiercés différents, mais c'est le même trio de chevaux. Un arrangement est une permutation interrompue : pour k = n, on retrouve A(n, n) = n!, puisque 0! = 1.

La croissance est violente. Ranger 15 livres sur une étagère : 15 ! = 1 307 674 368 000 façons. Battre un jeu de 52 cartes : 52 ! ≈ 8,07 · 10⁶⁷, du même ordre que le nombre estimé d'atomes de notre galaxie. Un mélange correct produit très probablement un ordre que personne n'a jamais obtenu depuis l'invention des cartes à jouer.

À quoi cela sert : le paradoxe des anniversaires. Dans une salle de p personnes, la probabilité que toutes les dates de naissance soient distinctes est un arrangement divisé par un produit : A(365, p) / 365^p. À 23 personnes, la probabilité d'une coïncidence dépasse déjà 50,73 % ; à 57 personnes elle atteint 99,01 %.

Combinaisons : choisir sans ordre

Une combinaison de k objets parmi n est un simple sous-ensemble : on choisit k objets sans se soucier de l'ordre. L'astuce consiste à partir des arrangements et à les regrouper : les arrangements qui contiennent les mêmes objets ne diffèrent que par l'ordre, et ces ordres sont les k! permutations des k objets. Chaque combinaison est donc comptée exactement k! fois parmi les arrangements.

C(n, k) = (nk) = A(n, k)k! = n!k! (n − k)! — on lit « k parmi n »

Chaque bande est un arrangement : ses k carrés colorés sont les objets, dans l'ordre. Au départ, les bandes sont rangées comme dans un dictionnaire ; « Regrouper » envoie chacune dans la case de son ensemble d'objets. Le groupe entouré de rouge change toutes les deux secondes.

Arrangements (bandes)

—

Ensembles différents, comptés

—

Taille de chaque groupe

—

C(n, k) = n! ÷ (k!(n − k)!)

—

C(n, n − k) : ensembles laissés de côté

—

Groupe entouré

—

Symétrie. Choisir les k objets que l'on garde revient à choisir les n − k que l'on laisse : C(n, k) = C(n, n − k). Le dernier compteur le vérifie sans formule, en passant en revue les 2ⁿ sous-ensembles possibles.

Deux chiffres pour situer. Au Loto, choisir 5 numéros parmi 49 sans se soucier de l'ordre : C(49, 5) = 1 906 884, multiplié par les 10 numéros chance, soit 19 068 840 grilles. Une main de poker : C(52, 5) = 2 598 960. Si l'ordre comptait, ce serait 120 fois plus.

Chemins et triangle de Pascal

Pour aller du coin A au coin B d'un quadrillage en ne faisant que des pas vers la droite (D) ou vers le haut (H), il faut a pas à droite et b pas vers le haut, soit a + b pas en tout. Un chemin est entièrement décrit par la place de ses a pas « D » parmi les a + b : il y a C(a + b, a) chemins. Autre façon de compter : on n'arrive à un carrefour que par sa gauche ou par le dessous, donc le nombre de chemins qui l'atteignent est la somme des deux nombres voisins. C'est exactement la règle du triangle de Pascal.

C(n, k) = C(n − 1, k − 1) + C(n − 1, k)

a (pas à droite)4

b (pas vers le haut)3

nombres aux carrefours

Le chemin bleu foncé parcourt tous les chemins possibles ; ceux déjà vus restent en bleu clair. En vert, le nombre de chemins qui atteignent chaque carrefour, obtenu par additions.

Triangle de Pascal : la case bleue est C(a + b, a) ; ses deux « parents », entourés de rouge, s'additionnent pour la former. Toucher une case charge le quadrillage correspondant.

Lignes du triangle12

colorier les nombres impairs

Chemins énumérés

—

C(a + b, a) par la formule

—

Additions jusqu'au point B

—

Parents dans le triangle

—

Somme de la ligne a + b

—

Chemin courant (D = droite, H = haut)

—

Une ligne entière vaut 2ⁿ. Choisir un sous-ensemble de n objets, c'est décider pour chacun « dedans ou dehors » : 2 × 2 × … × 2. En coloriant les nombres impairs sur 32 lignes, on voit surgir le triangle de Sierpiński : la parité des C(n, k) se répète par blocs de taille 2, 4, 8, 16…. Le triangle de Sierpiński a été découvert deux siècles et demi après Pascal. Le triangle lui-même est bien plus vieux que lui : Pingala en Inde, Al-Karaji à Bagdad vers l'an mille, Yang Hui en Chine en 1261 ; le traité de Pascal date de 1654.

Quelle formule ? Deux questions suffisent

Devant un problème de dénombrement, il suffit de se demander : l'ordre compte-t-il ? et peut-on répéter ? Les quatre réponses donnent quatre formules. Les trois onglets les mettent à l'épreuve : une énumération brute qui retrouve les quatre nombres d'un seul coup, le loto, puis le célèbre paradoxe des anniversaires.

La page écrit toutes les listes de k valeurs prises parmi n (il y en a n^k), puis les trie. Celles sans valeur répétée sont les arrangements. Parmi elles, celles écrites en ordre strictement croissant représentent chacune une combinaison, une seule par ensemble. Enfin, les listes en ordre croissant au sens large représentent les combinaisons avec répétition : un cornet de k boules de glace choisies parmi n parfums, où seul compte combien de boules de chaque parfum.

n (valeurs, parfums)4

k (longueur, boules)3

	Sans répétition	Avec répétition
L'ordre compte
L'ordre ne compte pas

Étoiles et barres : k étoiles pour les boules, n − 1 barres pour séparer les parfums. Les étoiles placées avant la première barre sont du parfum 1, entre la première et la deuxième du parfum 2, etc. Un cornet revient à choisir la place des k étoiles parmi n + k − 1 cases.

Cornet affiché

—

Listes écrites au total

—

Au loto à 6 numéros sur 49 (la formule française jusqu'en 2008), une grille est une combinaison : l'ordre de sortie des boules n'a aucune importance. La probabilité d'avoir exactement j bons numéros se compte en choisissant j numéros parmi les 6 gagnants, puis les 6 − j autres parmi les 43 perdants, et en divisant par le nombre total de grilles.

P(j bons) = C(k, j) × C(N − k, k − j)C(N, k)

N (boules)49

k (numéros cochés)6

Tirages par image

À gauche, en échelle logarithmique : probabilité exacte de chaque nombre de bons numéros (barres bleues) et fréquence observée sur les tirages simulés (losanges rouges). À droite : la grille du joueur (contour vert) et le dernier tirage (boules rouges).

Grilles possibles C(N, k)

—

Gagner le gros lot

—

Attente moyenne, un tirage par semaine

—

Vandermonde : Σ C(k, j) C(N − k, k − j) − C(N, k)

—

Tirages simulés

—

3 bons : simulé / exact

—

Dans un groupe de k personnes, quelle est la probabilité que deux d'entre elles fêtent leur anniversaire le même jour ? Les listes de k dates toutes différentes sont des arrangements : il y en a A(365, k) parmi les 365^k listes possibles (on ignore le 29 février et l'on suppose les naissances également réparties). Le complément donne la probabilité d'au moins une coïncidence.

P(au moins deux le même jour) = 1 − A(365, k)365^k = 1 − 365365 × 364365 × … × 365 − k + 1365

k (personnes)23

À gauche : probabilité exacte d'une coïncidence en fonction de k (bleu) et approximation 1 − e^{−k(k−1)/730} (orange pointillé). À droite : l'année en cercle, avec les anniversaires d'un groupe tiré au hasard ; les jours partagés sont en rouge.

Probabilité exacte (produit)

—

Contrôle en entiers exacts

—

Approximation exponentielle

—

Groupes simulés avec coïncidence

—

Plus petit groupe dépassant 50 %

—

Pourquoi 23 suffit. On ne cherche pas quelqu'un né le même jour que soi, mais un couple quelconque : 23 personnes forment C(23, 2) = 253 couples, chacun ayant une chance sur 365 de coïncider. Le même nombre C(n, k) compte des grilles de loto, des chemins sur un quadrillage, des couples, des sous-ensembles : dénombrer, c'est souvent reconnaître un problème ancien sous un déguisement nouveau.

Repères historiques

vers −200En Inde, le traité de métrique de Pingala dénombre les vers formés de syllabes longues et brèves : on y trouve en germe le triangle des C(n, k).
vers 1140Abraham ibn Ezra compte les conjonctions possibles des sept « planètes » de l'astrologie : C(7, 2) + C(7, 3) + … + C(7, 7) = 120.
1303Zhu Shijie publie en Chine le triangle des coefficients, déjà connu de Jia Xian au XIᵉ siècle.
1321Levi ben Gershon (Gersonide) démontre les formules des permutations, arrangements et combinaisons, par un raisonnement proche de la récurrence.
1654Blaise Pascal rédige le Traité du triangle arithmétique (publié en 1665) et l'applique, avec Fermat, au problème des partis : la naissance du calcul des probabilités.
1666Leibniz consacre sa Dissertation sur l'art combinatoire à ces dénombrements, qu'il voit comme une logique de l'invention.
1713L'Ars conjectandi de Jacques Bernoulli, posthume, réunit la théorie des permutations et des combinaisons au service des probabilités.
1939Richard von Mises pose le problème des anniversaires, dont la réponse — 23 personnes — surprend encore.

En résumé

Permutations

On range tous les objets ; l'ordre compte. Avec des objets identiques, on divise par la factorielle de chaque répétition.

Arrangements

n!(n − k)!

On remplit k places ; l'ordre compte. Avec répétition autorisée : n^k.

Combinaisons

n!k! (n − k)!

On choisit k objets ; l'ordre ne compte pas : chaque ensemble regroupe k! arrangements. Avec répétition : C(n + k − 1, k).

Pour aller plus loin

Formule du binôme. En développant (x + y)ⁿ = (x + y)(x + y)…(x + y), on choisit dans chaque parenthèse x ou y ; le terme x^ky^n−k apparaît autant de fois qu'il y a de façons de choisir les k parenthèses qui donnent x, soit C(n, k). D'où le nom de « coefficients binomiaux ».

Coefficients multinomiaux. Le nombre d'anagrammes d'un mot de n lettres où les lettres se répètent m₁, m₂, … fois vaut n! ÷ (m₁! m₂! …). Pour MISSISSIPPI : 11! ÷ (4! 4! 2! 1!) = 34 650.

Dérangements. Le nombre de permutations où aucun objet ne reste à sa place est l'entier le plus proche de n!/e : la probabilité qu'aucune lettre ne revienne à son destinataire tend vers 1/e ≈ 36,8 %.

Stirling. Le rapport n! ÷ (√(2πn)(n/e)ⁿ) vaut 1 + 1/(12n) + 1/(288n²) + … ; la planche 1 l'affiche pour chaque n.