Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes algébriques


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.

Fig. 1. Relations de Pascal

Démonstrations

Méthodes algébriques

1°a) Pour tout entier naturel $n$ : $\dbinom{n}{0}=1$.
$\dbinom{n}{0}=\dfrac{n!}{0!\times (n-0)!}=\dfrac{n!}{1\times n!}=1$.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{0}=1\;}}$

1°b) Pour tout entier naturel $n$ : $\dbinom{n}{n}=1$.
$\dbinom{n}{n}=\dfrac{n!}{n!\times (n-n)!}=\dfrac{n!}{n!\times 0!}=1$.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{n}=1\;}}$

1°c) Pour tout entier naturel $n$ : $\dbinom{n}{1}=n$.
$\dbinom{n}{1}=\dfrac{n!}{1!\times (n-1)!}=\dfrac{n\times(n-1)!}{1!\times (n-1)!}=n$.
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{1}=n\;}}$

1°d) Pour tout entier naturel $n$ : $\dbinom{n}{n-1}=n$.
$\dbinom{n}{n-1}=\dfrac{n!}{(n-1)!\times (n-(n-1))!}=\dfrac{n\times(n-1)!}{(n-1)!\times 1!}=n$.
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}$.
$\dbinom{n}{n-k}=\dfrac{n!}{(n-k)!\times (n-(n-k))!}=\dfrac{n!}{(n-k)!\times k!}=\dbinom{n}{k}$.
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}$.
Par définition de chaque terme, on a :
$\begin{array}{rcl}
& &\dbinom{n}{k}+\dbinom{n}{k+1}\\
&=& \dfrac{n!}{k!\times (n-k)!}+\dfrac{n!}{(k+1)!\times (n-(k+1))!}\\
&=& \dfrac{n!\color{brown}{\times(k+1)}}{{\color{brown}{(k+1)\times}}k!\times (n-k)!}+\dfrac{{\color{brown}{(n-k)}}\times n!}{(k+1)!\times (n-k-1)!\color{brown}{\times(n-k)}}\\
&=&\dfrac{n!+kn!}{(k+1)!\times (n-k)!}+\dfrac{n\times n! -k\times n!}{(k+1)!\times (n-k)!}\\
&=&\dfrac{n!+\not kn!+nn!-\not kn!}{(k+1)!\times (n-k)!}\\
&=&\dfrac{(n+1)n!}{(k+1)!\times \left((n+1)-(k+1)\right)!}\\
&=&\dfrac{(n+1)!}{(k+1)!\times \left((n+1)-(k+1)\right)!}\\
&=&\dbinom{n+1}{k+1}\\
\end{array}$
Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}\;}}$


2. Exercices résolus

Exercice résolu n°1.