Factorielles et coefficients binomiaux

Plan du chapitre "Calculs algébriques"

Factorielle d’un entier

Définition
On pose {0!=1}, et pour tout {n} de {\mathbb{N}^{*}}, on note {n!=n\;(n-1)!}.
Le symbole {n!} se lit “factorielle {n}“.

Remarques :

  • L’énoncé précédent est un exemple de définition récursive.
  • Pour tout {n} de {\mathbb{N}^{*}}, l’entier {n!} est le produit des entiers de {1} à {n}, c’est-à-dire {n!=\displaystyle\prod_{k=1}^nk}
  • On retiendra les valeurs :
    {\qquad 0!=1}, {1!=1}, {2!=2}, {3!=6}, {4!=24}, {5!=120}, {6!=720}, {7!=5040}.
  • L’entier {n!} désigne le nombre de permutations d’un ensemble à {n} éléments (c’est-à-dire de bijections de cet ensemble sur lui-même). Par exemple les {3!=6} permutations des lettres du mot {abc} sont : {abc}, {acb}, {bac}, {bca}, {cab} et {cba}.
  • Pour les grandes valeurs de {n}, on verra plus tard la formule de Stirling : {n!\sim n^{n}\text{e}^{-n}\sqrt{2\pi n}}.
    La signification de {\sim} est que le quotient des deux expressions tend vers {1} quand {n} tend vers {+\infty}.
    Par exemple, pour {n=20}, on a {\begin{cases}n!=2432902008176640000\\n^{n}\text{e}^{-n}\sqrt{2\pi n}\approx 2.42278684676\cdot 10^{18}\end{cases}}

Coefficients binomiaux

Définition (combinaisons de p éléments parmi n)
Soient {n} et {p} deux entiers, avec {0\le p\le n}. Soit {E} un ensemble fini possédant {n} éléments.
On note {\dbinom{n}{p}} le nombre de sous-ensemble de {E} possédant {p} éléments.

Remarques :

  • L’ensemble {E} dont il est question ici est évidemment sans importance.
    Par exemple, dans l’ensemble {E=\{a,b,c,d,e\}}, il y a {10} parties à trois éléments, qui sont {\{a,b,c\}}, {\{a,b,d\}}, {\{a,b,e\}}, {\{a,c,d\}}, {\{a,c,e\}}, {\{a,d,e\}}, {\{b,c,d\}}, {\{b,c,e\}}, {\{b,d,e\}}, {\{c,d,e\}}
  • Le coefficient {\dbinom{n}{p}} se lit “{p} parmi {n}“.
  • Si {E} a {n} éléments, il y a dans {E} : une seule partie vide, donc {\dbinom{n}{0}=1}.
    De même, il y a une seule partie à {n} éléments ({E} lui-même), donc {\dbinom{n}{n}=1}.
  • On étend la définition en posant {\dbinom{n}{p}=0} si {p\lt 0} ou {p>n} (ce qui est assez logique).

Proposition
Soient {n} et {p} deux entiers, avec {0\le p\le n}. On a l’égalité {\dbinom{n}{p}=\dfrac{n!}{p!\,(n-p)!}}

Démonstration
  Pour voir ce contenu, vous devez : 

Relations entre coefficients binomiaux

Proposition
On a les identités {\dbinom{n}{p}=\dbinom{n}{n-p}}, et {\dbinom{n}{p}=\dbinom{n-1}{p}+\dbinom{n-1}{p-1}}.

Démonstration
  Pour voir ce contenu, vous devez : 

La deuxième formule, avec {\dbinom{n}{0}=\dbinom{n}{n}=1}, permet de calculer les {\dbinom np} de proche en proche.
On place souvent les {\dbinom{n}{p}} dans un tableau triangulaire, de lignes et colonnes numérotées à partir de {0}.
Le coefficient {\dbinom{n}{p}} s’y place à l’intersection de la ligne d’indice {n} et de la colonne d’indice {p}.
Le tableau obtenu est connu sous le nom de “triangle de Pascal” :
{\begin{array}{c|c|c|c|c|c|c|c|c|}&p=0&p=1&p=2&p=3&p=4&p=5&p=6&\,\cdots\,\cr n=0&1& & & & & & &\cr n=1&1&1& & & & & &\cr n=2&1&2&1& & & & &\cr n=3&1&3&3&1& & & &\cr n=4&1&4&6&4&1& & &\cr n=5&1&5&10&10&5&1& &\cr n=6&1&6&15&20&15&6&1&\cr\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\ddots\cr n&\dbinom n0&\dbinom n1&\dbinom n2&\dbinom n3&\dbinom n4&\dbinom n5&\dbinom n6&\ddots\cr\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\cr\end{array}}
Proposition
On a les trois égalités :
{\dbinom n{p+1}=\dfrac{n-p}{p+1}\,\dbinom np,\quad\dbinom np=\dfrac np\,\dbinom {n-1}{p-1},\quad \dbinom np=\dfrac n{n-p}\,\dbinom {n-1}p}

Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (Formule du binôme)
Pour tous {x,y} de {\mathbb{C}}, et pour tout {n} de {\mathbb{N}} : {(x+y)^n=\displaystyle\sum_{k=0}^n\dbinom nk\,x^k\,y^{n-k}}.
En particulier : {(1+x)^n=\displaystyle\sum_{k=0}^n\dbinom nk\,x^k}.
Démonstration
  Pour voir ce contenu, vous devez : 

En particulier, pour tous {x} et {y} de {\mathbb{C}} :

  • {(x+y)^2=x^2+2xy+y^2}
  • {(x-y)^2=x^2-2xy+y^2}
  • {(x+y)^3=x^3+3x^2y+3xy^2+y^3}
  • {(x-y)^3=x^3-3x^2y+3xy^2-y^3}
  • {(x+y)^4=x^4+4x^3y+6x^{2}y^2+4xy^3+y^{4}}
  • {(x-y)^4=x^4-4x^3y+6x^{2}y^2-4xy^3+y^{4}}

Page précédente : sommes et produits
Page suivante : systèmes linéaires