Terminale ∼ Spécialité mathématique
Combinatoire et dénombrement Factorielle d'un entier et triangle de Pascal Factorielle d'un entier
Soit $n$ un entier naturel. On appelle factorielle de $n$, le nombre entier noté $n!$ qui est égale au produit de tous les entiers de $1$ jusqu'à $n$, si $n\geq1$, ou qui vaut $1$ si $n=0$. $0!$ $=$ $1$.
$5!$ $=$ $5\times$ $4$ $\times$ $3$ $\times$ $2$ $\times$ $1$ $=$ $120$. Simplifier les expressions suivantes :
  1. $\dfrac{8!}{6!}$

  2. $\dfrac{20!}{17!}$

  3. $\dfrac{n!}{(n-1)!}$, pour $n\in\mathbb{N}^*$.

  4. $\dfrac{(n+2)!}{n!}$, pour $n\in\mathbb{N}$.
  1. $\dfrac{8!}{6!}$ $=$ $\dfrac{8\times7\times6\times5\times4\times3\times2\times1}{6\times5\times4\times3\times2\times1}$ $=$ $\dfrac{8\times7\times6!}{6!}$ $=$ $8\times7$ $=$ $56$.

  2. $\dfrac{20!}{17!}$ $=$ $\dfrac{20\times19\times18\times17!}{17!}$ $=$ $20\times19\times18$ $=$ $6\,840$.

  3. $\dfrac{n!}{(n-1)!}$ $=$ $\dfrac{n\times(n-1)!}{(n-1)!}$ $=$ $n$.

  4. $\dfrac{(n+2)!}{n!}$ $=$ $\dfrac{(n+2)\times(n+1)n!}{n!}$ $=$ $(n+2)(n+1)$ $=$ $n^2+3n+2$.
Les deux algorithmes ci-dessous permettent de calculer la factorielle de n'importe quel nombre entier.
Algorithme n°1
def facto(n): f = 1 if n > 1: for i in range(2,n+1): f = f*i return f print(facto(5))
Algorithme n°2 récursif. Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions à partir de versions plus petites du même problème. Il s'agit d'un concept fondamental en informatique.
def facto(n): f = 1 if n > 1: f = n*facto(n-1) return f print(facto(5))
Triangle de Pascal Compléter le tableau suivant :
11
121
1331
14......1
1...............
11
121
1331
14641
15101051

On complète les cases vides en additionnant le nombre de la case juste au dessus avec celui-ci de celle qui est juste à gauche de cette dernière.
Le 6 est par exemple obtenu en additionnant les deux 3 qui sont juste au-dessus. Ce tableau s'appelle « le triangle de Pascal ».
Extrait du Traité du triangle arithmétique de Blaise Pascal dans lequel se trouve la première preuve par récurrence de l'histoire.
Ce traité a été publié à titre posthume en 1665.
Cardinal d'ensembles
Soit $n$ un entier naturel et $E$ un ensemble possèdant $n$ éléments.
On dit alors que $E$ est un ensemble fini et son nombre d'éléments est appelé cardinal de $E$. On le note $\text{card}(E)$. Soit $C$ l'ensemble des codes à quatre chiffres et $D$ l'ensemble des codes à quatre chiffres sans répétition (tous les chiffres du code sont distincts).
Déterminer $\text{card}(C)$ et $\text{card}(D)$. Lorsqu'on compose un code à quatre chiffres on a dix choix pour chacun des chiffres. Ainsi, $\text{card}(C)$ $=$ $10\times10\times10\times10$ $=$ $10^4$ $=$ $10\,000$.
Lorsque les quatre chiffres sont distincts on a $10$ possibilités pour le premier chiffre, puis $9$ pour le deuxième, $8$ pour le troisième et $7$ pour le quatrième. Ainsi :
$\text{card}(D)$ $=$ $10\times9\times8\times7$ $=$ $5\,040$.
On dit que deux ensembles $A$ et $B$ sont disjoints si $A\cap B$ $=$ $\varnothing$.
Soient $A$ et $B$ deux ensembles disjoints. On a alors : $\text{card}(A\cup B)$ $=$ $\text{card}(A)+\text{card}(B)$. Soit $P$ l'ensemble des nombres premiers inférieurs à $30$ et $Q$ l'ensemble des multiples de $4$ inférieurs à $30$. On a :
$\text{card}(P\cup Q)$ $=$ $\text{card}(P)+\text{card}(Q)$ $=$ $10$ $+$ $7$ $=$ $17$.
Soit $n$ un entier naturel non nul, et $A_1$, $A_2$, $\dots$, $A_n$ des ensembles finis, deux à deux disjoints. On a : $\operatorname{card}\left(A_{1} \cup A_{2} \cup \ldots \cup A_{n}\right)$ $=$ $\operatorname{card}\left(A_{1}\right)+\operatorname{card}\left(A_{2}\right)+\dots+\operatorname{card}\left(A_{n}\right)$. On pourrait démontrer cette propriété par récurrence.

Soit $E=$⟦$0;9$⟧. L'ensemble des couples de $E$ est de cardinal de $100$, car par exemple le couple $(2\,;1)$ est différent du couple $(1\,;2)$.
Soient $A$ et $B$ deux ensembles. Le produit cartésien de $E$ et $F$, noté $E\times F$, est l'ensemble des couples $(e\,;f)$ avec $e$ et $f$ des éléments respectifs de $E$ et $F$.
Soient $E$ et $F$ deux ensembles finis. On a : $\text{card}(E\times F)$ $=$ $\text{card}(E)\times\text{card}(F)$. Soit $E$ un semble de couleurs possibles pour un maillot. $E=\{ \text{R}\,; \text{V}\, ; \text{B} \}$, pour rouge, vert et bleu.
Soit $F$ l'ensemble des numéros possibles que peuvent porter ces maillots. $F=\{1 ; 2 ; 3 ; 4 ;5 \}$.
L'ensemble des maillots possibles (couleurs + numéros) est :
$E\times F$ $=$ $\{ (\text{R}\,;1)$ ; $(\text{R}\,;2)$ ; $(\text{R}\,;3)$ ; $(\text{R}\,;4)$ ; $(\text{R}\,;5)$ ; $(\text{V}\,;1)$ ; $(\text{V}\,;2)$ ; $(\text{V}\,;3)$ ; $(\text{V}\,;4)$ ; $(\text{V}\,;5)$ ; $(\text{B}\,;1)$ ; $(\text{B}\,;2)$ ; $(\text{B}\,;3)$ ; $(\text{B}\,;4)$ ; $(\text{B}\,;5)$ $\}$.
Son cardinal est de $3\times5$ $=$ $15$.
Soit $n$ un entier naturel non nul, et $A_1$, $A_2$, $\dots$, $A_n$ des ensembles finis. On a : $\operatorname{card}\left(A_{1} \times A_{2} \times \ldots \times A_{n}\right)$ $=$ $\operatorname{card}\left(A_{1}\right)\times\operatorname{card}\left(A_{2}\right)\times\dots\times\operatorname{card}\left(A_{n}\right)$. On note $A^2$ l'ensemble $A\times A$, ou encore $A^3$ l'ensemble $A\times A\times A$ etc.
k-uplets ∼ Parties d'un ensemble ∼ Arrangements ∼ Permutations
Soit $A$ un ensemble fini et $k$ un entier naturel non nul. On appelle $k$-uplet de $A$ un élément de $A^k$. Un mot formé de $8$ lettres est un $8$-uplet de l'alphabet. Soit $k\in\mathbb{N}$. Si $A$ est un ensemble fini de cardinal $n$, alors en appliquant la formule du cardinal d'un produit cartésien, il existe $n^k$ $k$-uplet de $A$.
En effet, $\text{card}(E^k)$ $=$ $\text{card}(E\times\dots\times E)$ $=$ $\text{card}(E)\times\dots\times\text{card}(E)$ $=$ $n\times\dots\times n$ $=$ $n^k$.
Une partie d'un ensemble $E$ est un ensemble formé d'éléments de $E$. Pour $E= \{ a\,; b\,; c\}$ les parties de $E$ sont : $\varnothing$, $\{ a \}$, $\{ b \}$, $\{ c \}$, $\{ a\,;b \}$, $\{ a\,;c \}$, $\{ b\, ; c\}$, $\{ a\,; b\,; c\}$.
Le nombre de parties de $E$ est ici de $8$.
Soit $E$ un ensemble fini de cardinal $n\in\mathbb{N}$. Le nombre de parties de $E$ est de $2^n$. Preuve
On note $e_{1}$, $e_{2}$, $\dots$, $e_{n}$ les éléments de $E$.
On associe à chaque partie $P$ de E un unique $n$ -uplet de l'ensemble $\{0 ; 1\}$ de la manière suivante : pour tout entier $i$ entre $1$ et $n$, on note $1$ si $e_{i}$ est dans $P$ et $0$ sinon. Par exemple, on associe à $\left\{e_{1}, e_{5}\right\}$ le $n$-uplet $\{1\, ; 0\, ; 0\, ;0\, ; 1\, ; 0\, ; \ldots ; 0\}$.
Ainsi, le nombre de parties de $E$ est égal au nombre de $n$ -uplets de l'ensemble $\{0\, ; 1\}$, c'est-à-dire $2^{n}$.

Soient $A$ un ensemble non vide de cardinal $n$ et $k$ un entier naturel inférieur ou égal à $n$.
Un arrangement de $k$ éléments de $A$ est un $k$-uplet d'éléments distincts de $A$. Si $A=\{ a\,; b\, ; c \, ; d\}$ alors $(a\,;c\,;d)$ et $( d\,; a\,; b)$ sont des arrangements de trois éléments de $A$.
Par contre $(a\,;b\,; b)$ n'est pas un arrangement d'éléments de $A$.
Soient $A$ un ensemble fini non vide à $n$ elements et $k$ un entier naturel tel que $k \leq n$.
Le nombre de $k$-arrangements de $A$ est égal à : $\mathcal{A}_{n}^{k}$ $=$ $n \times(n-1) \times \dots \times(n-k+1)$ $=$ $\dfrac{n !}{(n-k) !}$. Preuve
Pour construire un $k$-uplet de $A$, on a $n$ choix pour le premier élément, puis $n-1$ choix pour le deuxième, etc, jusqu'à $n-k+1$ choix pour le $k$-ième élément.
Ainsi, le nombre d'arrangement de $k$ éléments de $A$ est : $n\times(n-1)\times\dots\times(n-k+1)$ $=$ $\dfrac{n!}{(n-k)!}$.

Soit $A$ un ensemble fini non vide de cardinal $n$.
Une permutation de $A$ est un $n$-uplet d'éléments distincts de $A$. Si $ A=\{1\, ; 2\, ; 3\},$ les permutations de $A$ sont $(1\, ; 2\, ; 3 )$, $(1\, ; 3\, ; 2)$, $(2\, ; 1\, ; 3)$, $(2\, ; 3\, ; 1)$, $(3\, ; 1\, ; 2)$ et $(3\, ; 2\, ; 1)$.
Le nombre de permutations sur un ensemble de cardinal est de $n!$. Preuve
D'après la propriété précédente, une permutation étant un arrangement de $n$ éléments sur un ensemble de $n$ éléments, leur nombre est de : $\mathcal{A}_n^n$ $=$ $\dfrac{n!}{(n-n)!}$ $=$ $\dfrac{n!}{0!}$ $=$ $n!$.
Combinaisons d'un ensemble fini
Soit $A$ un ensemble fini de cardinal $n$ et $k$ un entier naturel tel que $k\leq n$.
Une combinaison de $k$ éléments de $A$ est une partie de $A$ de cardinal $k$.
Le nombre de combinaisons de $k$ éléments parmi $n$ est noté ${n \choose k}$. Dans une combinaison il n'y a pas de notion d'ordre.
Par exemple les combinaisons de deux éléments de $E=\{a\, ; b\, ; c\}$ sont :
$\{a\, ; b \}$, $\{a\, ; c \}$ et $\{ b\, ; c\}$.
On remarque donc que ${3 \choose 2}$ $=$ $3$.
On peut d'ailleurs voir que ${3 \choose 0}$ $=$ $1$, l'ensemble vide étant la seule partie d'un ensemble ne possédant aucun élément.
Soient $n$ et $k$ deux entiers naturels tels que $k \leq n$. Le nombre de combinaisons de $k$ éléments d'un ensemble de cardinal $n$ vérifie :
$\displaystyle{ {n \choose k} }$ $=$ $\dfrac{n!}{k!(n-k)!}$. Preuve
Dans un ensemble de $n$ éléments il y a $\dfrac{n!}{(n-k)!}$ arrangements de $k$ éléments (ou $k$-uplets sans répétition).
Or, dans un $k$-uplet l'ordre compte. Cependant il y a $k!$ façons de permuter $k$ éléments. Donc on peut regrouper les $k$-uplet par paquets de $k!$ pour ne les compter qu'une seule fois pour correspondre à une combinaison (puisque pour une combinaison l'ordre ne compte pas).
Ainsi, le nombre de combinaison de $k$ éléments parmi $n$ vérifie :
$\displaystyle{ n \choose k }$ $=$ $\dfrac{\mathcal{A}_n^k}{k!}$ $=$ $\dfrac{n!}{(n-k)!}\times\dfrac{1}{k!}$ $=$ $\dfrac{n!}{k!(n-k)!}$. Déterminer :
  1. ${2 \choose 0}$, ${2 \choose 1}$ et ${2 \choose 2}$.

  2. ${3 \choose 0}$, ${3 \choose 1}$, ${3 \choose 2}$ et ${3 \choose 3}$.
  1. ${2 \choose 0}$ $=$ $\dfrac{2!}{0!(2-0)!}$ $=$ $\dfrac{2}{1\times2}$ $=$ $1$.
    ${2 \choose 1}$ $=$ $\dfrac{2!}{1!(2-1)!}$ $=$ $2$.
    ${2 \choose 2}$ $=$ $\dfrac{2!}{2!(2-2)!}$ $=$ $1$.

  2. ${3 \choose 0}$ $=$ $\dfrac{3!}{0!3!}$ $=$ $1$.
    ${3 \choose 1}$ $=$ $\dfrac{3!}{1!(3-1)!}$ $=$ $3$.
    ${3 \choose 2}$ $=$ $\dfrac{3!}{2!(3-2)!}$ $=$ $1$.

    ${3 \choose 3}$ $=$ $\dfrac{3!}{3!0!}$ $=$ $1$.

Soit $n\in\mathbb{N}$. Preuve
Soient $n$ et $k$ deux entiers naturels tels que $k \leq n$. On a alors :
$\displaystyle{ n \choose k }$ $=$ $\displaystyle{ n \choose n-k }$. Preuve

$\displaystyle{ n \choose n-k }$ $=$ $\dfrac{n!}{(n-k)!(n-(n-k))!}$ $=$ $\dfrac{n!}{(n-k)!k!}$ $=$ $\displaystyle{ n \choose k }$.
Soient $n$ et $k$ deux entiers naturels tels que $1\leq k \leq n-1$. On a alors :
$\displaystyle{ n \choose k }$ $=$ $\displaystyle{ n-1 \choose k-1 }+\displaystyle{ n-1 \choose k }$. Preuve n°1
$\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$ $=$ $\dfrac{(n-1)!}{(k-1)!(n-1-(k-1))!}+\dfrac{(n-1)!}{k!(n-1-k)!}$
$=$ $\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}$.
On remarque alors que : Le dénominateur commun dans $\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}$ est donc $k!(n-k)!$.
Il faut donc : On a alors :

$\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$ $=$ $\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}$
$=$ $\dfrac{k(n-1)!}{k(k-1)!(n-k)!}+\dfrac{(n-k)(n-1)!}{k!(n-1-k)!(n-k)}$
$=$ $\dfrac{k(n-1)!}{k!(n-k)!}+\dfrac{(n-k)(n-1)!}{k!(n-k)!}$
$=$ $\dfrac{k(n-1)!+(n-k)(n-1)!}{k!(n-k)!}$
$=$ $\dfrac{k(n-1)!+n(n-1)!-k(n-1)!}{k!(n-k)!}$
$=$ $\dfrac{n(n-1)!}{k!(n-k)!}$
$=$ $\dfrac{n!}{k!(n-k)!}$
$=$ $\displaystyle{n \choose k}$.
Preuve n°2
Soit $E$ un ensemble de cardinal $n$ et soit $a$ un élément de $E$. On définit les ensembles suivants : Le cardinal de $A$ est $n \choose k$.
L'ensemble $B$ contenant $a$ pour le construire il faut donc choisir $k-1$ éléments (puisqu'on $a$ est déjà choisi) parmi les $n-1$ restants (tous les éléments de $E$ sauf $a$). Le cardinal de $B$ est donc ${n-1 \choose k-1}$.
De même, pour construire $C$ il nous faut choisir $k$ éléments parmi $n-1$ (tous les éléments de $E$ sauf $a$). Son cardinal est donc $n-1 \choose k$.

Remarquons que $B$ et $C$ sont disjoints (c'est-à-dire $B\cap C=\varnothing$).
Par ailleurs une partie à $k$ éléments de $E$, contient $a$ ou ne le contient pas. Ainsi : $A=B\cup C$ et :
$\text{card}(A)$ $=$ $\text{card}(B)+\text{card}(C)$
$\displaystyle{{n \choose k}}$ $=$ $\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$.
Cette formule justifie la construction du triangle de Pascal.
Pour tout entier $n$ : $\displaystyle{\sum_{k=0}^n{n \choose k}}$ $=$ $2^n.$ Preuve.
Soit $E$ un ensemble de cardinal $n$.
Pour tout entier $k$ inférieur à $n$, le nombre $\displaystyle{{n \choose k}}$ correspond au nombre de parties de $E$ possédant $k$ éléments.
Ainsi, la somme $\displaystyle{\sum_{k=0}^n{n \choose k}}$ correspond au nombre de parties de $E$ possédant aucun élément plus le nombre de parties de $E$ possédant un élément, plus le nombre de parties à deux éléments, etc. jusqu'au nombre de parties à $n$ éléments. Cette somme vaut donc le nombre total de parties de $E$, soit $2^n$.

Illustration dans le cas où $n=3$.
On note $E=\{ e_1 ; e_2 ; e_3 \}$ un ensemble à trois éléments.
Pour déterminer l'ensemble des parties de $E$ on peut parcourir l'arbre ci-dessous, la notation $\overline{e_1}$ voulant dire que l'on ne choisit pas l'élément $e_1$ :
$e_1$ $\overline{e_1}$ $e_2$ $\overline{e_2}$ $e_2$ $\overline{e_2}$ $e_3$ $\overline{e_3}$ $e_3$ $\overline{e_3}$ $e_3$ $\overline{e_3}$ $e_3$ $\overline{e_3}$
Il y a $2^3=8$ chemins possibles dans cet arbre qui sont respectivement :
$\{ e_1 ; e_2 ; e_3 \}$
$\{ e_1 ; e_2 ; \overline{e_3} \}$ $=$ $\{ e_1;e_2 \}$
$\{ e_1 ; \overline{e_2} ; e_3 \}$ $=$ $\{ e_1;e_3 \}$
$\{ e_1 ; \overline{e_2} ; \overline{e_3} \}$ $=$ $\{ e_1 \}$
$\{ \overline{e_1} ; e_2 ; e_3 \}$ $=$ $\{ e_2;e_3 \}$
$\{ \overline{e_1} ; e_2 ; \overline{e_3} \}$ $=$ $\{ e_2 \}$
$\{ \overline{e_1} ; \overline{e_2} ; e_3 \}$ $=$ $\{e_3 \}$
$\{ \overline{e_1} ; \overline{e_2} ; \overline{e_3} \}$ $=$ $\varnothing$

Il y a ${3 \choose 0} =1$ partie à $0$ élément qui est : $\varnothing$.

Il y a ${3 \choose 1} =3$ parties à $1$ élément qui sont : $\{ e_1 \}$, $\{ e_2 \}$ et $\{ e_3 \}$.

Il y a ${3 \choose 2} =3$ parties à $2$ éléments qui sont : $\{ e_1;e_2 \}$, $\{ e_1;e_3 \}$ et $\{ e_2;e_3 \}$.

Il y a ${3 \choose 3} =1$ parties à $3$ éléments qui est : $\{ e_1 ; e_2 ; e_3 \}$.

Dans cette illustration nous avons bien : ${3 \choose 0}+{3 \choose 1}+{3 \choose 2}+{3 \choose 3}$ $=$ $2^3$.

Dans la démonstration on a généralisé cet exemple à un arbre contenant $2^n$ chemins possibles en rassemblant les chemins par nombres d'éléments.