Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes combinatoires
1. Formule des coefficients binomiaux
Définition 1.
Soient $n$ et $k$ deux entiers naturels, $0\leqslant k\leqslant n$ et $E$ un ensemble non vide, à $n$ éléments.
Le nombre de parties ou de combinaison de $k$ éléments de $E$, noté $\dbinom{n}{k}$, est donné par la formule :
$$\dbinom{n}{k}=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ facteurs}}}{k!}\quad(1)$$
Explication de la formule
Une $k$-liste d’éléments distincts deux à deux s’obtient en choisissant successivement ses éléments $x_i$ distincts deux à deux, de la manière suivante :
On choisit $x_1$ parmi les $n$ éléments de $E$ ;
$x_1$ étant choisi, on choisit $x_2$ parmi les $(n-1)$ éléments restant dans $E$ ;
$x_1$ et $x_2$ étant choisis, on choisit $x_3$ parmi les $(n-2)$ éléments restant dans $E$ ;
et ainsi de suite…
$x_1$, $x_2$,$\ldots$, $x_{k-1}$ étant choisis, il reste : $n-(k-1)=\color{brown}{n-k+1}$ choix pour $x_k$.
Ce qui donne :
$$\begin{array}{|c|c|c|c|}\hline
x_1&x_2&x_3&\ldots&x_k\\ \hline
n\text{ choix}&(n-1)\text{ choix}&(n-2)\text{ choix}&\ldots&(n-(k-1))\text{ choix}\\ \hline
\end{array}$$
Par conséquent, d’après le principe multiplicatif, le nombre de $k$-listes $L_k$ ou $k$-uplets d’éléments distincts deux à deux de $E$ est égal à : $$\underbrace{n\times(n-1)\times(n-2)\times\ldots\times (n-k+1)}_{k\text{ facteurs}}$$
Or, à chaque partie $A_k$ ayant $k$ éléments (distincts) de $E$, correspondent $k!$ ($k$ factorielle) permutations donnant $k!$ possibilités de construire des $k$-listes avec les mêmes éléments deux à deux distincts de $A_k$. Ce qui donne la correspondance :
$$\color{brown}{\text{1 partie }A_k \longleftrightarrow k!\text{ listes différentes à } k \text{ éléments}}$$
Par conséquent, le nombre de parties $\dbinom{n}{k}$ de $k$ éléments dans un ensemble à $n$ éléments est égal au nombre de $k$-listes d’éléments distincts deux à deux, divisé par $k!$.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{k}=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ facteurs}}}{k!}\;}}\;(1)$
Cette formule ainsi écrite donne une manière très pratique pour les calculs numériques.
2. Propriétés des coefficients binomiaux
Propriété 1.
Pour tout entier naturel $n$ et tout entier $k$ tel que $0\leqslant k \leqslant n$, on a :
$$\boxed{\;\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\;}\quad(2)$$
Démonstration
$$\begin{array}{rl}
\dbinom{n}{k}&=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ facteurs}}}{k!}\\
&=\dfrac{n(n-1)(n-2)\cdots(n-(k-1))\color{brown}{\times(n-k)!}}{k!\color{brown}{\times(n-k)!}}\\
&=\dfrac{n!}{k!(n-k)!}\\
\end{array}$$
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\;}}$
Propriétés 2.
1°) Pour tout entier naturel $n$ :
a) $\dbinom{n}{0}=1$ ; b) $\dbinom{n}{n}=1$ ;
c) $\dbinom{n}{1}=n$ ; d) $\dbinom{n}{n-1}=n$.
2°) Pour tout entier $k$, $0\leqslant k\leqslant n$ :
e) $\dbinom{n}{n-k}=\dbinom{n}{k}$.
3°) Pour tout entier $k$, $0\leqslant k\leqslant n$ :
f) $\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}$
Ces dernières formules s’appellent les Relations de Pascal.
Démonstrations
Méthodes combinatoires
1°a) Pour tout entier naturel $n$ : $\dbinom{n}{0}=1$.
En effet, dans un ensemble à $n$ élément, il existe une seule partie à $0$ éléments et c’est l’ensemble vide $\emptyset$. D’où le résultat.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{0}=1\;}}$
1°b) Pour tout entier naturel $n$ : $\dbinom{n}{n}=1$.
En effet, dans un ensemble à $n$ élément, il existe une seule partie à $n$ éléments et c’est l’ensemble $E$ lui-même. D’où le résultat.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{n}=1\;}}$
1°c) Pour tout entier naturel $n$ : $\dbinom{n}{1}=n$.
En effet, dans un ensemble à $n$ élément, il existe $n$ parties à $1$ éléments. Ce sont tous les singletons de la forme $\{a\}$, $a\in E$ lui-même. D’où le résultat.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{1}=n\;}}$
1°d) Pour tout entier naturel $n$ : $\dbinom{n}{n-1}=n$.
En effet, dans un ensemble à $n$ élément, à toute partie $A$ à $(n-1)$ éléments correspond une seule partie à un seule élément $\overline{A}$, son complémentaire. Or, il existe $n$ parties à $1$ éléments dans $E$.
Par conséquent, il existe $n$ parties à $1$ éléments dans $E$. D’où le résultat.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{n-1}=n\;}}$
2°) Pour tous entiers $n$ et $k$, $0\leqslant k\leqslant n$ : $\dbinom{n}{n-k}=\dbinom{n}{k}$.
En effet, dans un ensemble à $n$ élément, à toute partie $A$ à $k$ éléments correspond une seule partie à $(n-k)$ élément $\overline{A}$, son complémentaire.
Par conséquent, le nombre de parties à $(n-k)$ éléments dans un ensemble à $n$ éléments est égal au nombre de parties à $k$ éléments dans un ensemble à $n$ éléments. D’où le résultat.
Conclusion. $\color{brown}{\boxed{\;\binom{n}{n-k}=\binom{n}{k}\;}}$
Relations de Pascal.
3°) Pour tous entiers $n$ et $k$, $0\leqslant k\leqslant n-1$ :
$\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}$.
Soit $a$ un élément étranger à $E$. Donc $a\not\in E$.
L’ensemble $E’=E\cup \{a\}$ contient exactement $n+1$ éléments.
Le nombre de parties à $(k+1)$ de l’ensemble $E’$ à $(n+1)$ éléments est donc égal à $\dbinom{n+1}{k+1}$.
Mais alors, cet ensemble des parties à $(k+1)$ éléments dans $E’$ se compose de deux types de parties.
$\bullet$ Les parties de $E’$ à $(k+1)$ éléments et qui contiennent $a$.
Elles sont formées de $a$ et de $k$ éléments de $E$.
Leur nombre est égal aux nombre de parties de $k$ éléments dans un ensemble à $n$ élément, à savoir $\dbinom{n}{k}$.
$\bullet$ Et les parties de $E’$ à $(k+1)$ éléments et qui ne contiennent pas $a$. Cela revient à choisir les $(k+1)$ éléments dans $E$.
Leur nombre est égal à $\dbinom{n}{k+1}$.
Il s’agit donc de cardinaux de deux parties disjointes. Donc d’après le principe additif, le nombre de parties à $k+1$ éléments dans un ensemble à $n+1$ est égal à $\dbinom{n}{k}+\dbinom{n}{k+1}$
Conclusion. $\color{brown}{\boxed{\;\dbinom{n+1}{k+1}=\dbinom{n}{k}+\dbinom{n}{k+1}\;}}$
2. Exercices résolus
Exercice résolu n°1.
Vues : 1004