🔢 Combinatoire et dénombrement

La croissance factorielle est hyper-exponentielle : 10! = 3 628 800 ; 20! ≈ 2,4 × 10¹⁸ ; 52! ≈ 8 × 10⁶⁷ (le nombre de façons de battre un jeu de cartes). L'approximation de Stirling donne n! ≈ √(2πn)·(n/e)^n, ce qui montre que la croissance factorielle dépasse toute exponentielle fixe 2^n pour n grand. C'est pourquoi une recherche exhaustive sur toutes les permutations devient infaisable même pour un n modeste.

Le théorème du binôme énonce que (x+y)^n = Σ_{k=0}^{n} C(n,k) x^(n−k) y^k. Le coefficient C(n,k) de chaque terme compte le nombre de façons de choisir k facteurs de y parmi n facteurs de (x+y). En posant x = y = 1, on obtient 2^n = Σ C(n,k), montrant que le nombre total de sous-ensembles d'un ensemble à n éléments est 2^n. En posant x = 1, y = −1, on obtient la somme alternée Σ (−1)^k C(n,k) = 0.

Un dérangement est une permutation où aucun élément ne reste à sa position d'origine — par exemple, réarranger {1,2,3} de sorte que 1 ne soit pas en position 1, 2 pas en position 2, et 3 pas en position 3. Le nombre de dérangements D(n) = n! × Σ_{k=0}^{n} (−1)^k / k!, qui par inclusion-exclusion est égal à l'entier le plus proche de n!/e. Pour n grand, environ 1/e ≈ 36,8 % de toutes les permutations sont des dérangements.

La méthode des étoiles et des barres dénombre le nombre de façons de répartir n objets identiques dans k compartiments distincts (en autorisant des compartiments vides) : C(n+k−1, k−1). Par exemple, répartir 7 bonbons indiscernables entre 3 enfants = C(9,2) = 36 façons. Si les compartiments vides ne sont pas autorisés (chaque enfant doit recevoir au moins un bonbon), la réponse est C(n−1, k−1) = C(6,2) = 15. Cette technique est à la base des fonctions génératrices et de l'extraction de coefficients polynomiaux.

La probabilité classique définit la probabilité d'un événement comme (issues favorables) / (issues totales également probables). Le numérateur comme le dénominateur sont généralement calculés à l'aide de permutations et de combinaisons. Par exemple, la probabilité qu'une main de poker à 5 cartes soit une couleur est C(13,5) × 4 / C(52,5) ≈ 0,00198, car on choisit 5 rangs parmi 13 dans l'une des 4 couleurs, parmi toutes les mains possibles de 5 cartes.

Colorier les entrées du triangle de Pascal selon C(n,k) mod p (pour p premier) produit la fractale du triangle de Sierpiński lorsque p = 2. Cela découle du théorème de Lucas : C(n,k) mod p ≡ le produit des C(nᵢ, kᵢ) mod p pour chaque chiffre des représentations en base p de n et k. Les entrées sont nulles modulo p dès qu'un chiffre de k dépasse le chiffre correspondant de n en base p, créant des « trous » triangulaires autosimilaires à toutes les échelles.

En génétique, C(n,k) compte le nombre de façons dont k mutations peuvent survenir dans un génome de n paires de bases — un facteur crucial pour estimer la probabilité de mutations cancérigènes spécifiques. L'équilibre de Hardy-Weinberg utilise les coefficients binomiaux pour prédire les fréquences génotypiques dans une population, et le dénombrement combinatoire sous-tend le calcul du nombre de structures d'anticorps possibles que le système immunitaire peut produire (estimé à plus de 10¹⁸ configurations distinctes).