Combinatoire et dénombrement

La combinatoire permet de compter le nombre de façons de choisir ou d'ordonner des éléments d'un ensemble. Le nombre de permutations de n éléments est n! (factorielle n). Le nombre d'arrangements de p éléments parmi n est n!/(n−p)!, ce qui correspond au nombre de listes ordonnées. Le nombre de combinaisons de p éléments parmi n, noté C(n,p) ou (n p), est n!/[p!(n−p)!] : il compte les sous-ensembles sans tenir compte de l'ordre. Par exemple, le nombre de mains de 5 cartes dans un jeu de 32 est C(32,5) = 201 376. La formule du binôme de Newton permet de développer (a+b)ⁿ = Σ C(n,k) aⁿ⁻ᵏ bᵏ pour k de 0 à n. Le triangle de Pascal organise les coefficients binomiaux avec la relation C(n,k) = C(n−1,k−1) + C(n−1,k).