\begin{align}\binom{n}{p}=&\dbinom{n}{n-p} \label{eq:prop5-1} \\\binom{n}{p}=&\dbinom{n-1}{p-1}+\dbinom{n-1}{p}\quad\text{pour $n\ge 1$ et $p\ge 1$} \label{eq:prop5-2} \\\end{align}
Pour démontrer ces formules, il y a deux méthodes :
- utiliser les définitions de ces nombres comme quotient de factorielles (méthode fastidieuse),
- utiliser un peu de combinatoire.
Nous allons prendre la méthode 2.
- Pour l’équation $\eqref{eq:prop5-1}$ :
$\dbinom{n}{n-p}$ est le nombre de parties à $(n-p)$ éléments d’un ensemble à $n$ éléments et $\dbinom{n}{p}$ est le nombre de partie à $p$ éléments d’un ensemble à $n$ éléments.
Or, si nous disposons d’un ensemble de $n$ éléments, prendre une partie à $p$ éléments est la même chose que laisser une partie à $(n-p)$ éléments
D’où :\[\binom{n}{n-p}=\binom{n}{p}.\]- Pour l’équation $\eqref{eq:prop5-2}$ :
Soit $E$ un ensemble à $n$ éléments. Particularisons un de ces élé-ments en le nommant $\alpha$.
Former une partie (ou combinaison) de $p$ éléments de $E$, c’est alors ou bien choisir l’élément $\alpha$ et $(p-1)$ éléments parmi les $n-1$ restants ou bien choisir $p$ éléments parmi les $(n-1)$ éléments distincts de $\alpha$.
Nous avons :\begin{align*}\binom{n}{p}&\text{ parties (ou combinaison) de $p$ éléments de $E$} \\\binom{n-1}{p-1}&\text{ parties (ou combinaison) de $p$ éléments de $E$ avec l’élément $\alpha$} \\\binom{n-1}{p}&\text{ parties (ou combinaison) de $p$ éléments de $E$ sans l’élément $\alpha$}\end{align*}Donc, comme le nombre de parties à $p$ éléments est la somme du nombre de parties à $p$ éléments avec $\alpha$ et du nombre de parties à $p$ éléments sans $\alpha$, nous obtenons :\[\binom{n}{p}=\binom{n-1}{p-1}+\binom{n-1}{p}.\]
Cette dernière formule permet de calculer $\dbinom{n}{p}$ connaissant $\dbinom{n-1}{p-1}$ et $\dbinom{n-1}{p}$.
De cette propriété découle le triangle de Pascal qui permet de calculer très rapidement (et sans utiliser les quotients de factorielles) les coefficients $\dbinom{n}{p}$ pour des valeurs de $n$ relativement petites.
Il s’agit d’un triangle de nombres dont pour une ligne donnée (numérotée $n$), nous avons tous les coefficients binomiaux $\dbinom{n}{p}$ pour $0\le p\le n$.
Chaque ligne a un élément de plus que la précédente.
Chaque ligne commence et finit par un $1$ (cf. $\dbinom{n}{0}=\dbinom{n}{n}=1$).
Mis à part le premier et le dernier élément, chaque terme s’obtient grâce à la formule de Pascal : \begin{array}{|c|o|c|}\hline\color{#333333}{\dbinom{n-1}{p-1}} & + & \color{#333333}{\dbinom{n-1}{p}} \\\hline & = & \color{#333333}{\dbinom{n}{p}} \\ \hline\end{array}
Selon cette formule de Pascal, nous construisons ainsi le Triangle de Pascal :\begin{array}{|l|l|l|l|l|l|l|l|l|}\hlinen\diagdown p & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\\hline0 & 1 \\\hline1 & 1 & 1 \\\hline2 & 1 & 2 & 1 \\\hline3 & 1 & 3 & 3 & 1 \\\hline4 & 1 & 4 & \color{#333333}{6} & \color{#333333}{4} & 1 \\\hline5 & 1 & 5 & 10 & \color{#333333}{10} & 5 & 1 \\\hline6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 \\\hline\ldots \\\hline\end{array}
Comme conséquence immédiate des formules de Pascal et de la construction du triangle de Pascal, nous obtenons à l’intersection de la ligne $n$ et de la colonne $p$, le coefficient $\dbinom{n}{p}$.