Combinatoire et dénombrement

Toutes les formules qui vont suivre auront toujours deux cas :

sans répétition
avec répétition : dans ce cas, il y aura une barre au-dessus pour signifier "avec répétition"

Par exemple, si on note les arrangements sans répétition $A_n$, on notera $\overline{A_n}$ ceux avec répétition possible.

Permutations

Le nombre de permutations des éléments d'un ensemble (sans répétition)

Pour tout ensemble $E$ de $n$ éléments, le nombre de permutations possibles sans répétition vaut :

$$ \forall n \in \mathbb{N}, $$

$$ P_n = n !$$

Le nombre de permutations des éléments d'un ensemble (avec répétition)

Pour tout ensemble $E = \{e_1, e_2, e_3, \ ..., \ e_n \}$ avec $k_1, k_2, k_3, ...,k_{n}$ le nombre d'occurrences de chaque élément, le nombre de permutations possibles vaut :

$$ \forall n \in \mathbb{N}, \ \forall (k_1, k_2, k_3, ...,k_n),$$

$$ \overline{P_n} = \frac{ \left( \sum\limits_{i=1}^{n} k_i \right) ! }{\prod\limits_{i=1}^{n} k_i ! } = \frac{\bigl(k_1 + k_2 \hspace{0.05em} + \hspace{0.05em} ... \hspace{0.05em} + k_n \hspace{0.05em}\bigr) !}{k_1 ! \times k_2 ! \hspace{0.05em} \times \hspace{0.05em} ... \hspace{0.05em} \times k_n ! } $$

Arrangements (avec ordre)

Le nombre d'arrangements des éléments d'un ensemble (sans répétition)

Le nombre d'arrangements sans répétition de $p$ éléments pris dans un ensemble de $n$ éléments vaut :

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ A_n^p = \frac{n !}{(n-p) !}$$

Le nombre d'arrangements des éléments d'un ensemble (avec répétition)

Le nombre d'arrangements avec répétition de $p$ éléments pris dans un ensemble de $n$ éléments vaut :

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \overline{A_n^p} = n^p$$

Combinaisons (sans ordre)

Le nombre de façons de prendre des éléments distincts d'un ensemble (sans répétition)

Le nombre de façons de prendre $p$ éléments (distincts et sans répétition) dans un ensemble de $n$ éléments vaut :

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$

$$ \binom{n}{p} = \frac{n !}{p ! (n-p) !}$$

($\Longrightarrow$ voir les propriétés du binôme)

Le nombre de façons de prendre des éléments distincts d'un ensemble (avec répétition)

Le nombre de façons de prendre $p$ éléments (distincts et avec répétition) dans un ensemble de $n$ éléments vaut :

$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \ n \geqslant 1, $$

$$ \left(\binom{n}{p}\right) = \binom{n + p - 1}{p} = \frac{(n + p -1) !}{p ! (n-1) !}$$

Le nombre de parties possibles d'un ensemble

Le nombre de parties possibles d'un ensemble $E = \{e_1, e_2, e_3, \ ..., e_n\}$, c'est-à-dire :

$$ \Bigl \{ \{ \emptyset \}, \{e_1\}, \{e_2\}, \{e_3\}, \ ..., \ \{e_1, e_2\}, \ \{e_1, e_3\}, \ \{e_2, e_3\}, \ ..., \ \{e_1, e_2, e_3\}, \ \{e_1, e_3, e_4\}, \ \{e_1, e_2, e_4\}, \ ..., \ \{e_1, e_2, e_3, \ ..., e_n\} \Bigr \}$$

vaut :

$$ \forall n \in \mathbb{N}, $$

$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$