Combinatoire et dénombrement

À retenir. Principe multiplicatif : $k$ choix successifs ayant $n_1,\dots,n_k$ possibilités donnent $n_1\times\dots\times n_k$ issues. Nombre de $p$-uplets d’éléments d’un ensemble à $n$ éléments (répétitions possibles, ordre important) : $n^p$.

À retenir. $n!=n(n-1)\cdots1$ ($0!=1$) est le nombre de permutations de $n$ éléments. Nombre de $p$-uplets d’éléments distincts (ordre important) : $\dfrac{n!}{(n-p)!}$. Anagrammes avec lettres répétées : diviser par les factorielles des répétitions.

À retenir. Les sous-ensembles à $p$ éléments d’un ensemble à $n$ éléments (ordre sans importance) sont au nombre de $\binom np=\dfrac{n!}{p!(n-p)!}$. $\binom np=\binom n{n-p}$ ; formule de Pascal : $\binom np+\binom n{p+1}=\binom{n+1}{p+1}$.

À retenir. Se demander : l’ordre compte-t-il ? les répétitions sont-elles permises ? Pour « au moins un », passer par le complémentaire ($\text{total}-\text{aucun}$). Cas disjoints : on additionne ; choix successifs : on multiplie. $\sum_{p=0}^n\binom np=2^n$ (nombre de parties).