Les propriétés du binôme \(: \binom{n}{p}\)
Soient \((p,n) \in \hspace{0.05em}\mathbb{N}^2 \) deux entiers naturels avec \( p \leqslant n \).
On appelle \(\binom{n}{p} \) ("\( p \) parmis \( n \)") le nombre de façons de prendre \( p \) éléments parmis \( n \) éléments d'un ensemble.
On l'appelle aussi le binôme, il répond à la formule suivante :
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$
$$ \binom{n}{p} = \frac{n!}{p \hspace{0.1em} ! \hspace{0.1em} (n-p) \hspace{0.1em} !} $$
"0 parmis n" / "n parmis n"
$$ \forall n \in \mathbb{N}, $$
$$ \binom{n}{0} = \binom{n}{n} = 1$$
"1 parmis n"
$$ \forall n \in \mathbb{N}, $$
$$ \binom{n}{1} = n$$
Symétrie
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$
$$ \binom{n}{p} = \binom{n}{n-p} $$
Formule du pion
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$
$$ \binom{n}{p} = \frac{n}{p} \binom{n -1}{p-1} $$
Formule de Pascal
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n - 1, $$
$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$
Somme horizontale de 0 à n
$$\forall n \in \mathbb{N}, $$
$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$
Somme verticale de r à n
$$\forall (r, n) \in \hspace{0.05em}\mathbb{N}^2, \enspace r \leqslant n, $$
$$ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r +1} $$
Récapitulatif des propriétés du binôme
Démonstrations
Soient \((p,n) \in \hspace{0.05em}\mathbb{N}^2 \) deux entiers naturels avec \( p \leqslant n \).
Il n'existe qu'une seule manière de prendre aucun ou tous les éléments d'un ensemble composé de \( n \) éléments.
Autrement, par la formule du binôme, on a :
$$ \binom{n}{0} = \frac{n!}{0 \hspace{0.1em} ! \ n!} =1 $$
Idem avec \(n\), on a :
$$ \binom{n}{n} = \frac{n!}{ n! \ 0 \hspace{0.1em} ! } =1 $$
Soit finalement,
$$ \forall n \in \mathbb{N}, $$
$$ \binom{n}{0} = \binom{n}{n} = 1$$
Par la formule du binôme, on a :
$$ \binom{n}{1} = \frac{n!}{1! \ (n-1)!} =1 $$
$$ \binom{n}{1} = \frac{n (n-1)!}{1! \ (n-1)!} = n $$
Soit finalement,
$$ \forall n \in \mathbb{N}, $$
$$ \binom{n}{1} = n$$
Le triangle de Pascal illustre bien la symétrie qu'il y a entre les \( p\) et \( (n-p) \) éléments pris parmis \(n\).
Par ailleurs, on peut voir par le calcul que :
$$ \binom{n}{p} = \frac{n!}{p \hspace{0.1em} ! \hspace{0.1em} (n-p) \hspace{0.1em} !} $$
$$ \binom{n}{n-p} = \frac{n!}{ (n-p) \hspace{0.1em} ! (n - (n-p))!} = \frac{n!}{p \hspace{0.1em} ! \hspace{0.1em} (n-p) \hspace{0.1em} !}$$
Soit,
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$
$$ \binom{n}{p} = \binom{n}{n-p} $$
Par la formule du binôme, on a :
$$ \binom{n}{p} = \frac{n!}{p \hspace{0.1em} ! \hspace{0.1em} (n-p) \hspace{0.1em} !} $$
$$ \binom{n}{p} = \frac{n(n-1)!}{p(p-1)! \hspace{0.1em} (n-p) \hspace{0.1em} !} $$
$$ \binom{n}{p} = \frac{n}{p} \frac{(n-1)!}{(p-1)! \hspace{0.1em} (n-p) \hspace{0.1em} !} $$
Or, on remarque qu'au dénominateur :
$$ n-p = (n-1) - (p-1) $$
Alors,
$$ \binom{n}{p} = \frac{n}{p} \frac{(n-1)!}{(p-1)!((n-1) - (p-1))!} $$
$$ \binom{n}{p} = \frac{n}{p} \binom{n -1}{p-1} $$
Soit,
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n, $$
$$ \binom{n}{p} = \frac{n}{p} \binom{n -1}{p-1} $$
-
Visualisation par le triangle de Pascal
Pour retrouver le triangle de Pascal, on additionne une case avec son voisin de gauche pour trouver le voisin du dessous.
Par ailleurs, si l'on considère les rangs \( (n-1)\) et \(n\) du Le triangle de Pascal, la formule apparaît clairement.
Par visualisation il est évident que,
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$
-
Par raisonnement
Considérons un ensemble \( E \) comprenant \(n\) éléments.
$$ E = \Bigl \{ e_1, e_2 , \hspace{0.2em} ... \hspace{0.2em}, e_{n} \Bigr\} $$
Dans cet ensemble, le nombre de parties possibles contenant \( p \) éléments est \( \binom{n}{p} \).
Séparons cet ensemble en deux ensembles distincts : \( E_1 \) et \( E_2 \).
-
\( E_1\) : un ensemble qui contient toutes les parties possibles de \( E \) contenant \( e_n \)
$$
E_1 =
\begin{Bmatrix}
\Bigl \{ e_1 , e_2, e_3, \ ... \ , e_n \Bigr \} \\
\Bigl\{ e_1 , e_3, e_4, \ ... \ , e_n \Bigr \} \\
\Bigl\{ e_1 , e_2, e_4, \ ... \ , e_n \Bigr \} \\
\Bigl\{................ \Bigr \} \\
\Bigl \{ \underbrace { e_1 , e_2, e_4, \ ... \ , e_n} _\text{ \(p\) éléments } \Bigr \}
\\
\end{Bmatrix}
$$
Étant donné que toutes ces parties contiennent \( e_n \), cela simplifie l'ensemble \( E_1 \) :
$$
E_1 =
\begin{Bmatrix}
\Bigl \{ e_1 , e_2, e_3, \ ... \ , e_n \Bigr \} \\
\Bigl\{ e_1 , e_3, e_4, \ ... \ , e_n \Bigr \} \\
\Bigl\{ e_1 , e_2, e_4, \ ... \ , e_n \Bigr \} \\
\Bigl\{................ \Bigr \} \\
\Bigl \{ \underbrace { e_1 , e_2, e_4, \ ... \ , e_n} _\text{ \(p\) éléments } \Bigr \}
\\
\end{Bmatrix}
\enspace
\Longrightarrow
\enspace
\begin{Bmatrix}
\Bigl \{ e_1 , e_2, e_3, \ ... \ \Bigr \} \\
\Bigl\{ e_1 , e_3, e_4, \ ... \ \Bigr \} \\
\Bigl\{ e_1 , e_2, e_4, \ ... \ \Bigr \} \\
\Bigl\{............. \Bigr \} \\
\Bigl \{ \underbrace { e_1 , e_2, e_4, \ .... } _\text{ \((p -1)\) éléments } \Bigr \}
\\
\end{Bmatrix}
$$
Alors le nombre d'éléments de \( E_1 \) se réduira au nombre de façons de prendre \( (p -1) \) éléments parmis \( (n-1) \) éléments dans \( E\), c'est-à-dire \( \binom{n -1}{p -1} \).
-
\( E_2 \) : un ensemble qui contient toutes les parties possibles de \( E \) ne contenant pas \( e_n \)
$$
E_2 = \underbrace {
\begin{Bmatrix}
{ e_1 , e_2, e_3, \ ... } \\
{ e_1 , e_3, e_4, \ ... } \\
{ e_1 , e_2, e_4, \ ... } \\
{............. } \\
{ e_1 , e_2, e_4, \ ... } \\
\end{Bmatrix} }
_\text{ \(p\) éléments }
$$
Comme \( E_2 \) ne contient pas \(e_n\), alors il restera un choix de \( (n-1) \) éléments pour en prendre \( p \). C'est-à-dire \( \binom{n -1}{p} \).
On a alors montré que :
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$
-
Par le calcul
Calculons \( \binom{n -1}{p -1} + \binom{n -1}{p} \) :
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) !}{ p \hspace{0.1em} ! \ (n-1-p)!} + \frac{(n-1) !}{ (p-1)! \ (n-1-(p-1))!} $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) !}{ p \hspace{0.1em} ! \ (n-1-p)!} + \frac{(n-1) !}{ (p-1)! \ (n-p) \hspace{0.1em} !} $$
On met ces deux termes au même dénominateur :
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ \textcolor{#8E5B5B}{(n-p)}}{ p \hspace{0.1em} ! \ (n-1-p)! \ \textcolor{#8E5B5B}{(n-p)}} + \frac{(n-1) ! \ \textcolor{#8E5B5B}{p}}{ (p-1)! \ (n-p) \hspace{0.1em} ! \ \textcolor{#8E5B5B}{p}} $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ (n-p)}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } + \frac{(n-1) ! \ p }{ p \hspace{0.1em} ! \ (n-p) \hspace{0.1em} !} $$
Et on factorise :
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{(n-1) ! \ (n-p + p)}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \frac{n!}{ p \hspace{0.1em} ! (n-p) \hspace{0.1em} ! } $$
$$ \binom{n -1}{p -1} + \binom{n -1}{p} = \binom{n}{p} $$
On a alors montré que,
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
$$ \binom{n}{p} = \binom{n -1}{p -1 } + \binom{n - 1}{p} \qquad (Pascal) $$
Soit \( n \in \mathbb{N}\) un entier naturel.
On souhaite calculer la somme horizontale des \( \binom{n}{k} \), de \( 0\) jusqu'à \( n\).
-
Avec le binôme de Newton
Le binôme de Newton nous dit que :
$$\forall n \in \mathbb{N}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{R}^2,$$
$$ (a + b)^n = \sum_{p = 0}^n \binom{n}{p} a^{n-p}b^p $$
En prenant \( \{ a = 1, \enspace b = 1 \}\), on a :
$$ \sum_{p = 0}^n \binom{n}{p} = (1 + 1)^n $$
Et finalement,
$$\forall n \in \mathbb{N}, $$
$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$
Soit :
$$ \binom{n}{0} + \binom{n}{1} \enspace + ... + \enspace \binom{n}{n-1} + \binom{n}{n} = \hspace{0.02em} 2^n $$
-
Par récurrence
Essayons de montrer que la proposition suivante \((P_n)\) est vraie :
$$\forall n \in \mathbb{N}, $$
$$ \binom{n}{0} + \binom{n}{1} \enspace + ... + \enspace \binom{n}{n-1} + \binom{n}{n} = \hspace{0.02em} 2^n \qquad (P_n) $$
-
Calcul du premier terme
Vérifions que c'est bien vrai pour le premier terme, c'est-à-dire lorsque \( n = 0 \).
$$ \sum_{p = 0}^0 \binom{0}{p} = \binom{0}{0} = 1 $$
Or,
$$ 2^0 = 1 $$
On a donc bien :
$$ \sum_{p = 0}^0 \binom{0}{p} = \hspace{0.2em} 2^0 $$
\((P_0)\) est vraie.
-
Vérification de l'hérédité
Soit \( k \in \mathbb{N} \) un entier naturel.
On suppose que la proposition \((P_k)\) est vraie pour tout \( k \).
$$ \binom{k}{0} + \binom{k}{1} \enspace + ... + \enspace \binom{k}{k} + \binom{k}{k} = \hspace{0.2em} 2^{k} \qquad (P_{k}) $$
Vérifions que c'est bien le cas pour \((P_{k + 1})\).
$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2^{k + 1} \qquad (P_{k + 1}) $$
Calculons le membre de droite de \(( P_{k + 1} ) \):
$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} $$
Mais on sait grâce à la formule de Pascal, que :
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
$$ \binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p} \qquad (Pascal) $$
Soit aussi que :
$$ \binom{n + 1}{p + 1} = \binom{n}{p} + \binom{n}{p + 1} \qquad (Pascal^*) $$
$$ \textcolor{#606B9E}{\binom{k + 1}{0}} + \textcolor{#446e4f}{\binom{k + 1}{1}} + \textcolor{#8E5B5B}{ \binom{k + 1}{2}} \enspace + ... + \enspace \textcolor{#7C578A}{\binom{k + 1}{k}} + \textcolor{#606B9E}{\binom{k + 1}{k + 1}} $$
Alors grâce à \( (Pascal^*)\), on a :
$$ \textcolor{#606B9E}{\binom{k + 1}{0}} + \textcolor{#446e4f}{\binom{k}{0} + \binom{k}{1}} + \textcolor{#8E5B5B}{\binom{k}{1} + \binom{k}{2}} \enspace + ... + \enspace \textcolor{#7C578A}{\binom{k}{k - 1} + \binom{k}{k}} + \textcolor{#606B9E}{\binom{k + 1}{k + 1}} $$
Or, le premier terme est égal au second.
$$ \binom{k + 1}{0} = \binom{k}{0} $$
De même, le dernier est égal à l'avant-dernier.
$$ \binom{k + 1}{k + 1} = \binom{k}{k} $$
Ce qui nous amène à :
$$ \binom{k}{0} + \binom{k}{0} + \binom{k}{1} + \binom{k}{1} + \binom{k}{2} \enspace + ... + \enspace \binom{k}{k - 1} + \binom{k}{k} +\binom{k}{k} $$
Puis finalement :
$$ 2 \left[ \binom{k}{0} + \binom{k}{1} + \binom{k}{2} \enspace + ... + \enspace \binom{k}{k - 1} + \binom{k}{k} \right] $$
Or, notre hypothèse était que :
$$ \binom{k}{0} + \binom{k}{1} \enspace + ... + \enspace \binom{k}{k-1} + \binom{k}{k} = \hspace{0.2em} 2^k \qquad (P_k) $$
On en déduit que :
$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2 \times 2^{k} $$
Soit :
$$ \binom{k + 1}{0} + \binom{k + 1}{1} \enspace + ... + \enspace \binom{k + 1}{k} + \binom{k + 1}{k + 1} = \hspace{0.2em} 2^{k + 1} \qquad (P_{k+1}) $$
\((P_{k + 1})\) est vraie.
-
Conclusion
La proposition \((P_n)\) est vraie pour son premier terme \(n_0 = 0\) et est héréditaire de proche en proche pour tout \(k \in \mathbb{N}\).
Par le principe de récurrence, elle ainsi est vraie pour tout \(n \in \mathbb{N}\).
Nous venons de prouver par une récurrence que :
$$\forall n \in \mathbb{N}, $$
$$ \sum_{p = 0}^n \binom{n}{p} = \hspace{0.2em} 2^n $$
Soit \( (r, n) \in \hspace{0.05em} \mathbb{N}^2\) deux entiers naturels.
On souhaite calculer la somme verticale des \( \binom{k}{r} \), de \( r\) jusqu'à \( n\).
On sait par la formule de Pascal, que :
$$ \forall (p,n) \in \hspace{0.05em}\mathbb{N}^2, \enspace p \leqslant n -1, $$
$$ \binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p} \qquad (Pascal) $$
Soit aussi que :
$$ \binom{n + 1}{p + 1} = \binom{n}{p} + \binom{n}{p + 1} \qquad (Pascal^*) $$
Soit, en remplaçant dans notre cas,
$$ \forall (r,k) \in \hspace{0.05em}\mathbb{N}^2, \enspace r +1 \leqslant k, \enspace \binom{k + 1}{r + 1} = \binom{k}{r} + \binom{k}{r + 1} $$
Et,
$$ \binom{k}{r} = \binom{k + 1}{r + 1} - \binom{k}{r + 1} \qquad (1) $$
En extractant le premier terme de la somme recherchée :
$$ \sum_{k=r}^n \binom{k}{r} = \binom{r}{r} + \sum_{k=r + 1}^n \binom{k}{r} $$
On injecte à présent \((1) \) :
$$ \sum_{k=r}^n \binom{k}{r} = \binom{r}{r} + \sum_{k=r + 1}^n \Biggl[ \binom{k + 1}{r + 1} - \binom{k}{r + 1} \Biggr] $$
On voit ici que la somme du membre de droite est une somme téléscopique, on a alors en simplifiant :
$$ \sum_{k=r}^n \binom{k}{r} = \binom{r}{r} + \binom{n + 1}{r + 1} - \binom{r+1}{r + 1} $$
$$ \sum_{k=r}^n \binom{k}{r} = 1 + \binom{n + 1}{r + 1} - 1 $$
Et finalement,
$$\forall (r, n) \in \hspace{0.05em}\mathbb{N}^2, \enspace r \leqslant n, $$
$$ \sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r +1} $$