La relation de Pascal

Démonstrations de combinatoire (terminale)

Deux démonstrations de la relation de Pascal sont au programme de terminale générale (maths de spécialité). C’est l’objet de cette page. Nous supposerons que vous avez déjà assimilé le principe des combinaisons, du triangle de Pascal et des factorielles.

 

La relation de Pascal

Soit \(n\) et \(k\) deux entiers naturels avec \(k + 1 \leqslant n.\)

La relation est la suivante :

\[\left( {\begin{array}{*{20}{c}}
{n + 1}\\
{k + 1}
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
n\\
k
\end{array}} \right) + \left( {\begin{array}{*{20}{c}}
n\\
{k + 1}
\end{array}} \right)\]

Une illustration sur le triangle de Pascal se trouve en page de coefficient binomial.

 

Démonstration par le calcul

\(\left( {\begin{array}{*{20}{c}}
n\\
k
\end{array}} \right) + \left( {\begin{array}{*{20}{c}}
n\\
{k + 1}
\end{array}} \right)\)
\(=\) \( \frac{{n!}}{{k!(n - k)!}}\) \(+\) \(\frac{{n!}}{{(k + 1)!(n - (k + 1))!}}\) (par définition)
\( = \frac{{n!}}{{k!(n - k)!}}\) \(+\) \(\frac{{n!}}{{(k + 1)!(n - k - 1)!}}\)

Ensuite vient l’étape la moins évidente. Elle consiste à réduire au même dénominateur. Pour cela, multiplions le numérateur et le dénominateur du premier terme par \(k + 1\) et du second par \(n - k.\) Si vous maîtrisez bien les factorielles, vous conviendrez que \(k!(k + 1) = (k + 1)!\) et que \((n - k)(n - k - 1)!\) \(=\) \((n - k)!\)

Nous obtenons \(\frac{n!(k + 1)}{(k + 1)!(n - k)!}\) \(+\) \(\frac{n!(n - k)}{(k + 1)!(n - k)!}\)

Réunissons tout ceci en une seule fraction et factorisons par \(n!\)

\(\frac{n!(k + 1 + n - k)}{(k + 1)!(n - k)!}\)
\(= \frac{n!(n + 1)}{(k + 1)!(n - k)!}\)
\(= \frac{(n + 1)!}{(k + 1)!(n - k)!}\)

C’est précisément là où nous devions arriver puisque \(\left( {\begin{array}{*{20}{c}}
{n + 1}\\
{k + 1}
\end{array}} \right)\) \(=\) \(\frac{(n + 1)!}{(k + 1)(n + 1 – k – 1)!}\)  \(=\) \(\frac{(n + 1)!}{(k + 1)!(n – k)!}\)

 

Preuve par combinatoire

Une combinaison de \(k\) éléments pris parmi \(n\) est le nombre de parties de \(k\) éléments d’un ensemble de \(n\) éléments.

Donc une combinaison de \(k + 1\) éléments pris parmi \(n + 1\), qui s’écrit \(\left( {\begin{array}{*{20}{c}}
{n + 1}\\
{k + 1}
\end{array}} \right)\) est le nombre de parties de \(k + 1\) éléments d’un ensemble de \(n + 1\) éléments.

Nous allons distinguer deux possibilités. Soit l’ensemble \(E = \{e_1,e_2,…e_{n+1}\}.\) Parmi le nombre de parties cherchées, il y a celles qui contiennent \(e_{n+1}\) et celles qui ne le contiennent pas.

1- Celles qui le contiennent. Le nombre de parties de \(E\) est alors celui de \(k\) éléments pris parmi \(n.\)

Si vous ne comprenez pas pourquoi, prenez l’exemple d’une main de cinq cartes à jouer dans un jeu de 32. Vous cherchez le nombre de combinaisons possibles. Si vous savez que dans cette main se trouve la dame de pique, alors vous ne cherchez plus qu’un nombre de combinaisons de quatre cartes prises parmi 31.

2- Celles qui ne contiennent pas \(e_{n+1}.\) On cherche bien \(k + 1\) parties mais dans un ensemble de seulement \(n\) éléments puisqu’on sait que \(e_{n+1}\) est exclu.

Nous utilisons le principe additif puisque les deux parties sont disjointes (soit il y a l’élément \(e_{n+1}\) soit il n’y est pas).

Donc, si l’on formalise ceci, nous retrouvons bien :

\[\left( {\begin{array}{*{20}{c}}
{n + 1}\\
{k + 1}
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
n\\
k
\end{array}} \right) + \left( {\begin{array}{*{20}{c}}
n\\
{k + 1}
\end{array}} \right)\]

 

Bonus

En bonus et parce que vous avez tout bien suivi voici une autre démonstration exigible au programme de terminale. Nous devons prouver l’égalité suivante :

\[\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}}
n\\
k
\end{array}} \right) = {2^n}} \]

Ce n’est pas une égalité qui va vous servir tous les jours mais elle est tout de même étonnante. Toutes les parties d’un ensemble de \(n\) éléments (celles de 0 élément, celles de 1 élément, celles de 2 éléments…) s’établissent à \(2^n.\)

Mais pourquoi donc ?

Si \(k = 0\) il n’y a qu’une seule partie, l’ensemble vide. Soit \(\left( {\begin{array}{*{20}{c}}
n\\
0
\end{array}} \right)\)

Si \(k = 1\) il y en a \(n\) (il suffit de compter), soit \(\left( {\begin{array}{*{20}{c}}
n\\
1
\end{array}} \right)\)

Si \(k = 2\) nous cherchons le nombre de combinaisons de deux éléments pris parmi \(n\) donc \(\left( {\begin{array}{*{20}{c}}
n\\
2
\end{array}} \right)\)

Et ainsi de suite. Pour \(k = n\) il y en a \(\left( {\begin{array}{*{20}{c}}
n\\
n
\end{array}} \right)\) c’est-à-dire une seule partie constituée de tous les éléments de l’ensemble.

Là encore nous retrouvons notre cher principe additif.

\[\left( {\begin{array}{*{20}{c}}
n\\
0
\end{array}} \right) + \left( {\begin{array}{*{20}{c}}
n\\
1
\end{array}} \right) + ... + \left( {\begin{array}{*{20}{c}}
n\\
n
\end{array}} \right) = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}}
n\\
k
\end{array}} \right)} \]

Fort bien. Mais pourquoi est-ce égal à \(2^n\) ?

Là, c’est avec le principe multiplicatif que nous allons le montrer. La partie contient-elle le premier élément ? Deux possibilités : oui ou non. Et le deuxième ? Là encore, oui ou non. Le troisième ? Oui ou non. Nous en sommes à combien ? Déjà huit, soit \(2^3.\) Vous pouvez dessiner un arbre de dénombrement si vous n’êtes pas convaincu.

Finalement, le nombre de parties possibles est de \(2^n.\)

L’égalité est démontrée.