Vidéo 6 : coefficients binomiaux¶
La factorielle¶
Si \(n\) est un entier strictement positif, on appelle factorielle de \(n\) le nombre suivant :
\(1\times 2\times \dots \times n.\)
La factorielle de \(n\) se note \(n!\). C’est donc le produit de tous les entiers entre 1 et \(n\).
La factorielle vérifie la propriété suivante :
\((\star)\quad (n+1)!=n!\times (n+1)\)
valable pour tout entier \(n>0\).
Voici les 5 premières factorielles :
\(\begin{array}{rcl}1! &=& 1\\2! &=& 2\\3! &=& 2\times 3=6\\4! &=& 6\times 4=24\\5! &=& 24\times 5=120\end{array}\)
La factorielle de \(n\) grandit très vite, asymptotiquement plus vite que n’importe quelle exponentielle de \(n\) (c’est-à-dire, du type \(a^n\)).
On souhaite pouvoir donner une valeur à la factorielle de \(0\). Pour cela, on s’arrange pour que la relation \((\star)\) soit encore vraie pour \(n=0\), ce qui donne :
\(1!=1\times 0!\)
ce qui impose \(\boxed{0!=1}\).
On peut démontrer que le nombre \(n!\) admet une interprétation combinatoire : c’est le nombre de permutations de \(n\) objets, autrement dit le nombre d’alignements possibles dans \(n\) emplacements de \(n\) objets. Par exemple, voici les 6 façons d’aligner trois objets nommés \(A\), \(B\) et \(C\) :
\(\begin{array}{ccc}A & B & C \\A & C & B \\B & A & C \\B & C & A \\C & A & B \\C & B & A\end{array}\)
Preuve par récurrence¶
Montrons l’assertion par récurrence sur \(n\).
Si \(n=1\) il y a bien un seul rangement possible de 1 objet.
Fixons \(n\geq 1\) et supposons que le nombre de permutations de \(n\) objets soit \(n!\). Donnons-nous un alignement de \(n+1\) cases, numérotées \(1\), \(2\), etc. \(n\) et \(n+1\) et donnons-nous \(n+1\) objets distincts \(X_1\), \(X_2, \dots, X_n, X_{n+1}\) à placer dans les cases. Pour bien distinguer, notons \(X\) l’objet \(X_{n+1}\).
Toute permutation de \(n+1\) objets placera forcément \(X\) dans l’une des \(n+1\) cases. Cette case étant connue, disons la case numéro \(k\), on obtiendra toutes les permutations des \(n+1\) objets telles que \(X\) soit dans la case \(k\) en plaçant les \(n\) objets autres que \(X\) dans les \(n\) cases restantes. Le placement de \(n\) objets dans \(n\) cases peut se faire, d’après l’hypothèse de récurrence, de \(n!\) façons. Il y a \(n+1\) possibilités de placement de l’objet \(X\) (soit à la case numéro \(k=1\), soit à la case numéro \(k=2\), etc soit à la case numéro \(k=n+1\)), et il y a \(n!\) placements par cas, donc, on obtient un nombre total de permutations valant \((n+1)\times n!=(n+1)!\) ce qui termine l’hérédité et achève la récurrence.
Le coefficient binomial¶
Si \(p\) et \(n\) sont des entiers tels que
\(0\leq p\leq n\)
alors on appelle coefficient binomial \(\dbinom{n}{p}\) le nombre suivant :
\((1)\quad \boxed{\dbinom{n}{p}=\ds\frac{n!}{p!(n-p)!} }\)
Ce nombre est lu « \(p\) parmi \(n\) ». Comme moyen mnémotechnique, on observera qu’au dénominateur, on a \(p+(n-p)=n\).
Il se trouve que \(\dbinom{n}{p}\) est un nombre entier mais cela n’a rien d’évident a priori.
La formule ci-dessus n’est pas adapté au calcul. En effet, \(n!\) peut être un nombre très grand. Ainsi, calculons par exemple \(\dbinom{11}{4}\) :
\(\dbinom{11}{4}=\ds\frac{11!}{4!7!}=\frac{39916800}{24\times 5040}=330\)
Cherchons une formule plus appropriée. Dans (1), on peut simplifier \(n!\) par \((n-p)!\). Une fois simplifié, il reste le produit des \(n-(n-p)=p\) entiers en décroissant à partir de \(n\), autrement dit les entiers \(n-k\) avec \(k\) variant de \(0\) à \(p-1\) :
\(n-0, n-1, \dots, n-(p-2), n-(p-1)\)
Comme \(n-(p-1)=n-p+1\), on obtient la jolie formule suivante :
\(\dbinom{n}{p}=\ds\frac{n(n-1)\dots (n-p+1)}{p!}\)
ou encore
\(\boxed{(2)\quad\dbinom{n}{p}=\ds\frac{n(n-1)\times\dots\times(n-p+1)}{p(p-1)\times\dots\times 1}}\)
Cette formule est particulièrement simple à retenir :
- la fraction commence comme le membre de gauche : \(n\) en haut et \(p\) en bas ;
- le numérateur comme le dénominateur sont le produit en décroissant de \(p\) entiers positifs.
Recalculons
\(\dbinom{11}{4}=\ds\frac{11\times 10\times 9\times 8}{4\times 3\times 2\times 1}=11\times 10\times 3=330\)
on voit que le calcul est beaucoup plus léger.
En particulier, de la formule (2), en isolant \(n\) et \(p\), on obtient la formule suivante :
\(\boxed{(3)\quad\dbinom{n}{p}=\ds\frac{n}{p}\dbinom{n-1}{p-1}}\)
valable si \(1\leq p\leq n\).
Symétrie¶
La formule (1) montre que \(\boxed{\ds\dbinom{n}{n-p}= \dbinom{n}{p}}\)
puisque
\(\dbinom{n}{n-p}=\ds\frac{n!}{(n-p)!(n-(n-p))!}=\ds\frac{n!}{(n-p)!p!}= \dbinom{n}{p}\)
Ainsi, \(\ds{\dbinom{11}{7}=\dbinom{11}{4}=330}\).
Valeurs remarquables¶
Si \(p=0\) alors (1) donne :
\(\dbinom{n}{p}=\ds\frac{n!}{n!\, 0!}=\ds\frac{n!}{n!}= 1\)
Si \(p=1\) alors (2) donne :
\(\dbinom{n}{p}=\ds\frac{n}{1}=n\)
Ainsi
\(\dbinom{n}{0}=\dbinom{n}{n}=1, \quad \dbinom{n}{1}=\dbinom{n}{n-1}=n.\)
Relation fondamentale¶
Nous avons calculé \(\ds\dbinom{11}{4}=330\). Calculons \(\dbinom{10}{4}\) et \(\dbinom{10}{3}\) :
\(\begin{array}{rcl}\dbinom{10}{3}&=&\ds\frac{10\times 9\times 8}{3\times 2\times 1}=10\times 3\times 4=120\\\dbinom{10}{4}&=&\ds\frac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}=10\times 3\times 7=210\end{array}\)
Comme \(120+210=330\), on a \(\ds\dbinom{11}{4}=\dbinom{10}{3}+\dbinom{10}{4}\). Cette propriété est générale :
\((4)\boxed{\quad\ds\dbinom{n}{p}+\dbinom{n}{p+1}=\dbinom{n+1}{p+1}}\)
en supposant que \(0\leq p < n\). En effet, soit \(A\) le numérateur de \(\dbinom{n}{p}\) dans \((2)\):
\(A= n(n-1)\times\dots\times(n-p+1).\)
Alors
\(\begin{array}{rcl}\dbinom{n}{p}+\dbinom{n}{p+1}&=&\ds\frac{A}{p!}+\ds\frac{A\times (n-p)}{(p+1)!}\\ &=&\ds\frac{A\times (p+1)+A\times(n-p)}{(p+1)!}\\ &=&\ds\frac{A\times (n+1)}{(p+1)!}\\ &=&\ds\frac{(n+1)n\times \dots\times(n-p+1)}{(p+1)!}\\ &=&\dbinom{n+1}{p+1}\end{array}\)
Propriété combinatoire¶
On peut démontrer que \(\dbinom{n}{p}\) est le nombre de façons de choisir \(p\) objets parmi \(n\) objets distincts. Par exemple, les façons de choisir \(3\) objets parmi \(5\) objets \(A, B, C, D\) et \(E\) sont les 10 suivantes :
\(\begin{array}{cccc|cccc}A & B & C \quad &&&\quad A & D & E\\ A & B & D \quad &&&\quad B & C & D\\A & B & E \quad &&&\quad B & C & E\\A & C & D \quad &&&\quad B & D & E\\A & C & E \quad &&&\quad C & D & E\end{array}\)
et, on a bien \(\dbinom{5}{3}=\ds\frac{5\times 4\times 3}{3\times 2\times 1}=10\).
Définition si \(p>n\)¶
On définit \(\dbinom{n}{p}=0\) si \(p>n\). Ce choix est cohérent avec la définition combinatoire de \(p\) parmi \(n\). Cette définition ne modifie pas la relation fondamentale qui est alors vraie pour tous \(n\) et \(p\) dans \(\n\).
Un coefficient binomial est un entier¶
La relation fondamentale (4) montre, par récurrence sur \(n\), que tout coefficient \(\dbinom{n}{p}\) où \(p\) est arbitraire dans \(\N\) est un entier (en bref : la somme de deux entiers est un entier).
La même relation justifie aussi, par récurrence sur \(n\), que \(\dbinom{n}{p}\) est le nombre de façons de choisir \(p\) objets parmi \(n\).