Les formules de 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 $$

Récapitulatif des formules de combinatoire et dénombrement

Démonstrations

Soit $E$ un ensemble de $n$ éléments :

$$E = \{e_1, e_2, e_3, \ ..., e_n\}$$

Permutations

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

Pour le premier choix, on a $n$ possibilités. Pour le second, on en a $(n-1)$ puisqu'un premier élément a déjà été choisi. De la même manière, pour le troisième, on en aura $(n-2)$...etc., jusqu'au dernier élément $(n-(n-1))$.

$$ P_n = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(n-2)) \times (n-(n-1))$$

$$ P_n = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times 2 \times 1$$

Soit finalement, pour tout ensemble $E$ de $n$ éléments :

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

$$ P_n = n !$$

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

Soit un alphabet $A$ composée de $n$ lettres :

$$A = \{a, b, c, \ ..., \ \omega \}$$

Et les nombres $k_a, k_b, k_c, \ ..., \ k_{\omega} $ le nombre de répétitions associées à chacune de ces lettres.

Comme plus haut, le nombre de mots de $n$ lettres que l'on peut composer avec les lettres de l'alphabet $A$ sans répétition est : $n !$.

Maintenant, en prenant en compte les répétitions respectives de chaque lettre, on a l'aplhabet suivant:

$$A' = \{ \underbrace{a, a, a, ...} _\text{$k_a$}, \ \underbrace{b, b, b, ...} _\text{$k_b$}, \ \underbrace{c, c, c, ...} _\text{$k_c$}, \ ..., \ \ \underbrace{\omega, \omega, \omega, ...} _\text{$k_{\omega}$} \}$$

Appelons $N$ la somme des différentes répétitions respectives :

$$N = k_a + k_b + k_c + \ ... \ + k_{\omega} $$

De la même manière, on pourra alors composer $N !$ mots de $N$ lettres. Cependant, comme certaines lettres seront répétées, il va falloir retirer les mots qui sont présents plusieurs fois et ainsi ne conserver qu'une seule version de chaque mot.

C'est-à-dire que pour chaque mot $m$ créé, avec une place définie pour chaque lettre :

$$ m_1 = \{ \underbrace{aaa ...} _\text{$k_a$} \ \underbrace{b b b ...} _\text{$k_b$} \ \underbrace{c c c ...} _\text{$k_c$} \ \ \underbrace{\omega \omega \omega ...} _\text{$k_{\omega}$} \}$$

$$ m_2 = \{ a a b ... \ a b b ... \ c c \omega \ ... \ c \omega \omega ... \}$$

$$ ...etc.$$

Il y en a $k_a !$ versions avec la lettre $a$ à ces places précises, puis $k_b !$ versions pour la lettre $b$...etc.

Donc pour chaque mot, il y a $(k_a ! \times k_b ! \times \ k_c ! \times \hspace{0.05em} ... \hspace{0.05em} \times k_{\omega} !) $ versions identiques de ce même mot.

Alors, 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),$$

De manière implicite, pour tout $i$ si l'élément $e_i$ est présent une fois alors $k_i = 1$ par défaut.

Arrangements (avec ordre)

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

Si l'on souhaite classer un nombre de $p$ éléments selon un ordre bien précis, un peu à la manière des permutations on aura $n$ choix pour le premier, $(n-1)$ choix pour le deuxième ... etc., mais sur $p$ éléments seulement, à la différence d'une permutation :

$$A_n^p = \hspace{0.05em} \underbrace{ n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(p-2)) \times (n-(p-1)) } _\text{ $p$ éléments} $$

Or, on remarque que cela correspond presque à une factorielle :

$$n ! = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} 2 \times 1 $$

En effet,

$$n ! = n \times (n-1) \times (n-2) \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} (n-(p-2)) \times (n-(p-1)) \times (n-p) \times (n-(p + 1)) \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} 2 \times 1 $$

$$n ! =A_n^p \times (n-p) ! $$

Alors, 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)

Lorsque que l'on effectue des arrangements dans un ensemble, mais cette fois-ci avec répétition, on aura alors $n$ choix à chaque fois :

$$A_n^p = \hspace{0.05em} \underbrace{ n \times n \hspace{0.02em} \times \hspace{0.02em} ... \hspace{0.02em} \times \hspace{0.02em} n \times n } _\text{ $p$ éléments} $$

Alors, 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)

En calculant le nombre d'arrangements (sans répétition) possibles de $p$ éléments pris dans cet ensemble, on obtient un nombre d'éléments possibles avec une notion de classement, ou d'ordre.

En souhaitant ne conserver qu'une seule version de ce nombre éléments, tous distincts, il faut alors leur retirer leur ordre, c'est-à-dire leur permutations. On notera ce nombre $\binom{n}{p}$, alors :

$$ \binom{n}{p} = \frac{A_n^p}{p !} $$

Alors, 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)

On lit ("$ p $ parmis $ n $").

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

On considère que ces éléments sont en abondance, et que l'on peut, à chaque tour, tirer à nouveau parmis les éléments de cet ensemble.

On souhaite savoir le nombre de façons qu'il y a de prendre un panier de $p$ éléments parmis un total de $n$.

Dans ce cas, considérons un nouvel ensemble final $F$, qui sera l'ensemble de départ, auquel on ajoutera tour à tour les éléments déjà choisis au tour précédent.

Au premier tour, on choisit un élément, que l'on ajoute à la fin :

$$F = \{ \cancel{e_1}, e_2, e_3, e_4, \ ..., e_p, \ ..., e_n, e_1\}$$
Au second tour, on choisit un deuxième élément, que l'on ajoute à la fin :

$$F = \{ \cancel{e_1}, \cancel{e_2}, e_3, e_4, \ ..., e_p, \ ..., e_n, e_1, e_2\}$$
..etc.
Au $(p-1)$-ième tour, on a remis $(p-1)$ fois les éléments choisis à chaque tour :

$$F = \{ \cancel{e_1}, \cancel{e_2}, \cancel{e_3}, \cancel{e_4}, \ ..., \cancel{e_{p-1}}, e_{p} \ ... , e_n , \ e_1, e_2, e_3, e_4, \ ... , e_{p-1} \}$$
Au $p$-ième tour, on en choisit un dernier sans le remettre dans l'ensemble final, car on a atteint le nombre de $p$ éléments souhaités.

$$F = \{ \underbrace{ \cancel{e_1}, \cancel{e_2}, \cancel{e_3}, \cancel{e_4}, \ ..., \cancel{e_{p-1}}, \cancel{e_{p}}, \ ... , e_n } _\text{$n$ éléments de départ }, \ \underbrace{ e_1, e_2, e_3, e_4, \ ... , e_{p-1} } _\text{$(p-1)$ éléments ajoutés} \}$$

Finalement, cela revient à prendre $p$ éléments distincts dans un ensemble de $(n + p - 1)$ éléments.

On notera ce nombre $\bigl(\binom{n}{p}\bigr)$ par opposition au éléments pris sans répétition $\binom{n}{p}$.

Alors, 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) !}$$

À noter qu'à la différence des éléments pris sans répétition $\binom{n}{p}$, dans ce cas-ci il est possible d'avoir $(p > n)$.

Le nombre de parties possibles d'un ensemble

Si l'on souhaite obtenir le nombre de parties possibles de cet ensemble, c'est-à-dire :

Pour tout $p $ allant de $0$ à $n$, on doit additionner les $ p $ éléments pris parmis $ n $ $\binom{n}{p}$ :

$$ \sum_{p = 0}^n \binom{n}{p} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} \hspace{0.05em} + \hspace{0.05em} ... \hspace{0.05em} + \hspace{0.05em} \binom{n}{n-1} + \binom{n}{n} $$

Et cette somme vaut :

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

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

($\Longrightarrow$ voir la démonstration)

Récapitulatif des formules de combinatoire et dénombrement

Exemples

Les permutations

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

Si l'on dispose d'un alphabet avec $3$ lettres différentes :

$$A = \bigl \{a, b, c \}$$

Si l'on souhaite savoir le nombre de mots possibles, sans répétition de lettres, on a $3!$ mots possibles.

$$ P_{abc} = 3 !$$

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

À présent, avec cet alphabet de $3$ lettres :

$$A = \bigl \{m, a, n \}$$

Si l'on souhaite savoir le nombre d'anagrammes du mot $"maman"$, on a :

$$ \overline{P_{maman}} = \frac{(2 + 2 + 1) !}{2 ! \times 2 ! } $$

$$ \overline{P_{maman}} =30$$

Les arrangements

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

On dispose d'une urne avec $8$ boules numérotées de $1$ à $8$. On souhaite calculer le nombre de possibilités de tirer $3$ boules.

$$ A_8^3 = \frac{8 !}{(8-3) !}$$

$$ A_8^3 = \frac{8 !}{5 !}$$

$$ A_8^3 = 8 \times 7 \times 6$$

$$ A_8^3 = 336$$

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

On souhaite maintenant tirer toujours $3$ boules, mais avec remise dans l'urne à chaque fois. On aura donc pour les trois fois, $8$ possibilités de tirages.

$$ \overline{A_8^3} = 8^3$$

$$ \overline{A_8^3} = 512$$

Les combinaisons

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

Si on souhaite savoir combien de matchs vont avoir dans un championnat d'échecs entre $10$ compétiteurs, qui vont tous jouer entre eux une fois.

On doit alors prendre $2$ joueurs parmis les $10$ compétiteurs.

$$ \binom{10}{2} = \frac{10 !}{2 ! (10-2) !} $$

$$ \binom{10}{2} = \frac{9 \times 10}{2} $$

$$ \binom{10}{2} = 45 $$

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

On souhaite constituer un panier de $(p = 4)$ fruits parmis un choix possible de $(n = 6)$ fruits, sachant que les fruits disponibles sont en abondance. On a alors :

$$ \left(\binom{6}{4}\right) = \binom{6 + 4 - 1}{4} $$

$$ \left(\binom{6}{4}\right) = \binom{9}{4} $$

$$ \left(\binom{6}{4}\right) = \frac{9 !}{4 ! (9-4) !} $$

$$ \left(\binom{6}{4}\right) = \frac{9 \times 8 \times 7 \times 6 }{4 \times 3 \times 2} $$

$$ \left(\binom{6}{4}\right) = 126 $$

Les formules de combinatoire et dénombrement

Démonstrations

Exemples

Les permutations

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

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

Les arrangements

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

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

Les combinaisons

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

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