Atelier de combinatoire

La difficulté en combinatoire est rarement le calcul en lui-même — c'est de classer correctement l'énoncé du problème. Deux questions oui/non font presque tout le travail : l'ordre compte-t-il (arranger ou choisir), et le même élément peut-il être choisi plus d'une fois (avec ou sans répétition) ? Ces deux réponses classent à elles seules chaque problème dans l'un des quatre modèles de base — permutations, combinaisons, permutations avec répétition et combinaisons avec répétition (« étoiles et barres ») — ce qui explique pourquoi un comité, une composition d'équipe, un code PIN et un ticket de loterie nécessitent chacun une formule différente malgré une apparence superficiellement similaire. L'inclusion-exclusion et les dérangements existent précisément parce que les problèmes réels enfreignent souvent les hypothèses propres de ces quatre modèles, avec des ensembles qui se chevauchent ou des correspondances exactes interdites, d'une manière que les formules de base ne peuvent pas gérer seules.

Le but de la combinatoire est de trouver combien d'arrangements existent sans tous les écrire. Un code PIN à 4 chiffres n'a que 10⁴ = 10,000 possibilités que l'on pourrait encore imaginer comme une liste, mais un ticket de loto 6 parmi 49 en compte C(49,6) = 13,983,816 — personne ne les liste à la main. Les formules proposées ici donnent le total exact en une seule étape, transformant une énumération sans espoir en un court calcul. C'est pourquoi l'outil affiche toujours le décompte, son nombre de chiffres et une notation scientifique pour les valeurs vraiment gigantesques.

Le modèle de dérangement compte les arrangements où rien n'occupe sa propre place — le cas du Père Noël secret où personne ne tire son propre nom. Étonnamment, la proportion de toutes les permutations qui sont des dérangements converge presque aussitôt vers 1/e ≈ 0.3679 : dès 6 personnes, elle est déjà exacte à trois décimales. Ainsi, la probabilité qu'un tirage aléatoire ne donne à personne son propre nom est d'environ 37%, et elle bouge à peine que le groupe compte 6 ou 600 membres. La constante e, née de l'analyse et des intérêts composés, sort directement d'un problème de pur dénombrement.