Dénombrement
Devant une poignée d'objets à choisir, tout le dénombrement tient dans deux questions préalables. L'ordre du tirage change-t-il le résultat ? Un objet peut-il ressortir deux fois ? Selon les réponses, on obtient quatre formules — et quatre seulement. Les cinq planches qui suivent les construisent l'une après l'autre, chacune vérifiée par énumération exhaustive dans votre navigateur.
l'arrangement retient l'ordre · la combinaison l'oublie, en divisant par les k ! façons de ranger un même paquet
Tout part de là : à chaque étape on multiplie. Regardez pousser l'arbre et comptez ses feuilles.
Le principe multiplicatif. Si un premier choix offre n1 possibilités, et que pour chacune d'elles un second en offre n2, alors les deux choix successifs en offrent n1 × n2. C'est tout, et tout le reste en découle.
Avec remise, chaque étage de l'arbre a la même largeur : n × n × … = nk. 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.
Un podium n'est pas un jury : AB et BA sont deux podiums, mais un seul jury. Ici, ce sont deux objets distincts.
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 · 1067, 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) / 365p. À 23 personnes, la probabilité d'une coïncidence dépasse déjà 50,73 % ; à 57 personnes elle atteint 99,01 %. Le panneau du bas remplit des salles au hasard, en continu : la fréquence observée rejoint la courbe.
Tirez le curseur : les arrangements qui contiennent les mêmes objets viennent se replier les uns sur les autres.
Pourquoi exactement k !. Un paquet de k objets distincts peut être écrit dans k ! ordres différents, ni plus ni moins. Chaque combinaison a donc été comptée k ! fois parmi les arrangements — toujours le même nombre de fois, ce qui autorise la division. Les paquets qui se referment sur l'écran ont tous rigoureusement la même taille : c'est la condition de validité de la formule, et elle se voit.
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.
Toutes les combinaisons d'un coup, rangées en triangle. Cliquez une case — ou déplacez les curseurs.
Une seule règle le construit : chaque case est la somme des deux qui la surplombent, C(n,k) = C(n−1, k−1) + C(n−1, k). La démonstration tient en une phrase : parmi les k objets choisis, ou bien le dernier objet disponible y figure — il reste k−1 places à pourvoir — ou bien il n'y figure pas.
Ce que la case compte aussi. En mode « chemins », chaque descente du sommet jusqu'à la case est un itinéraire fait de k pas à droite et n−k pas à gauche : la case vaut donc le nombre de chemins qui y mènent. Le même argument donne le nombre de trajets dans un quadrillage de rues, et le développement de (a + b)n, dont les coefficients sont précisément la ligne n.
Les lignes s'additionnent en 2n — choisir un sous-ensemble quelconque parmi n objets revient à répondre n fois par oui ou par non. Et si l'on ne garde que les cases impaires, il apparaît un triangle de Sierpiński, 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.
Deux questions, quatre réponses. Et la quatrième, la plus surprenante, se démontre en glissant des barres.
Le tableau ferme le sujet. Tirer k objets parmi n : si l'ordre compte et qu'on remet, nk ; si l'ordre compte sans remise, A(n,k) ; sans ordre et sans remise, C(n,k). Reste la case déroutante : sans ordre mais avec répétition, la réponse n'est ni nk/k ! ni rien de simple — c'est C(n + k − 1, k). Chaque case est recomptée en direct par énumération exhaustive : les quatre nombres affichés sont vérifiés, pas récités.
Pourquoi cette formule : les étoiles et les barres. Un tirage sans ordre avec répétition, c'est juste un effectif par catégorie. Écrivez les k objets comme des étoiles, et séparez les n catégories par n − 1 barres. Faites glisser le curseur : les groupes se dissolvent, et il ne reste qu'une file de n + k − 1 cases où il a fallu choisir les k qui portent une étoile. La correspondance est parfaitement réversible — d'où l'égalité exacte des deux comptages.
C'est le mouvement typique du dénombrement : on ne compte presque jamais l'objet demandé. On construit une correspondance parfaite avec un objet dont on sait déjà compter, et on lit la réponse dans l'autre monde.
Les quatre formules ne sont pas seulement affichées : à chaque réglage, le navigateur énumère réellement tous les tirages possibles et compare le décompte obtenu à la formule. Les identités du triangle de Pascal (somme = 2ⁿ, somme alternée nulle, somme des carrés = C(2n, n)) sont recalculées de la même manière.