Techniques de dénombrement

Principes fondamentaux

Principe additif

Si $A$ et $B$ sont disjoints : $|A \cup B| = |A| + |B|$

Principe multiplicatif

$|A \times B| = |A| \cdot |B|$

Formules de dénombrement

Arrangements

Nombre de listes ordonnées de $k$ éléments parmi $n$ (sans repetition) :

Permutations

Combinaisons

Nombre de parties a $k$ éléments d'un ensemble a $n$ éléments :

Propriétés :

• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{k} = \binom{n}{n-k}$ (symétrie)
• $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (Pascal)

Formule du binome de Newton