Coefficient binomial

En mathématiques, les coefficients binomiaux, définis pour tout entier naturel Modèle:Mvar et tout entier naturel Modèle:Mvar inférieur ou égal à Modèle:Mvar, donnent le nombre de parties de Modèle:Mvar éléments dans un ensemble de Modèle:Mvar éléments. On les note $\textstyle {n \choose k}$ (lu « k parmi n » ) ou Modèle:Mvar (lu « combinaison de k parmi n »), la première notation étant préconisée par la norme ISO 31-11. Cette quantité s'exprime à l'aide de la fonction factorielle :

${n \choose k}=C_{n}^{k}\,={\frac {n!}{k!(n-k)!}}$.

Les coefficients binomiaux interviennent dans de nombreux domaines des mathématiques : développement du binôme en algèbre, dénombrements, développement en série, lois de probabilités, etc.

On peut les généraliser, sous certaines conditions, aux nombres complexes.

Établissement de la formule

L'expression $\textstyle {n \choose k}$ du nombre de parties à Modèle:Mvar éléments, c'est-à-dire du nombre de [[Combinaison (mathématiques)|Modèle:Mvar-combinaisons]] dans un ensemble à Modèle:Mvar éléments, se détermine en calculant de deux façons différentes le nombre de [[arrangement|Modèle:Mvar-arrangements]] dans cet ensemble, à savoir

$A_{n}^{k}={\frac {n!}{(n-k)!}}={n \choose k}k!$

La confrontation des deux calculs donne l'expression algébrique de $\textstyle {n \choose k}$, pour Modèle:Mvar variant de 0 à Modèle:Mvar :

$C_{n}^{k}={n \choose k}={\frac {n!}{k!(n-k)!}}\qquad {\mbox{(1)}}$

en particulier, $\textstyle {n \choose 0}={\frac {n!}{1\times n!}}=1$ (dans un ensemble à Modèle:Mvar éléments, il y a exactement une partie à 0 élément : l'ensemble vide) et de même, $\textstyle {n \choose n}={\frac {n!}{n!\times 1}}=1$.

Si Modèle:Mvar est strictement négatif ou strictement supérieur à Modèle:Mvar, le coefficient binomial est nul.

Exemple : Dans un ensemble à 4 éléments {a,b,c,d}, il y a $\textstyle {4 \choose 2}=6$ parties à deux éléments, à savoir : {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}.

Propriété récursive des coefficients binomiaux d'entiers Modèle:Ancre

Une importante relation, la formule de Pascal, lie les coefficients binomiaux : pour tout couple Modèle:Math d'entiers naturels,

${n \choose k}+{n \choose k+1}={n+1 \choose k+1}\qquad {\mbox{(2)}}$

On la démontre classiquement par un raisonnement combinatoire élémentaire, mais on peut aussi utiliser la forme factorielle.

Elle donne lieu au triangle de Pascal qui permet un calcul des coefficients pour de petites valeurs de Modèle:Mvar :

0 :									1
1 :								1		1
2 :							1		2		1
3 :						1		3		3		1
4 :					1		4		6		4		1
5 :				1		5		10		10		5		1
6 :			1		6		15		20		15		6		1
7 :		1		7		21		35		35		21		7		1
8 :	1		8		28		56		70		56		28		8		1

Les coefficients $\textstyle {n \choose k}$ pour 0 ≤ Modèle:Mvar ≤ Modèle:Mvar figurent à la Modèle:Mvar-ième ligne. Le triangle est construit en plaçant des 1 aux extrémités de chaque ligne et en complétant la ligne en reportant la somme des deux nombres adjacents de la ligne supérieure. Modèle:Mvar se lit de gauche à droite sur la Modèle:Mvar-ième ligne en partant de 0 jusqu'à Modèle:Mvar.

Utilisation des coefficients binomiaux

Développement du binôme de Newton

Modèle:Article détaillé Ces nombres sont les coefficients qui apparaissent en développant la puissance Modèle:Mvar-ième de Modèle:Math :

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}\qquad (3)$

Par exemple, en regardant la cinquième ligne du triangle de Pascal, on obtient immédiatement que :

$\ (x+y)^{5}=x^{5}+5x^{4}y+10x^{3}y^{2}+10x^{2}y^{3}+5xy^{4}+y^{5}\,$ .

Dérivée d'ordre n d'un produit de fonctions

Soient Modèle:Mvar un entier supérieur ou égal à 1, et Modèle:Mvar et Modèle:Mvar deux fonctions Modèle:Mvar fois dérivables en un point Modèle:Mvar, alors leur produit Modèle:Mvar est aussi Modèle:Mvar fois dérivable au point Modèle:Mvar, et la dérivée d'ordre Modèle:Mvar est donnée par la formule de Leibniz :

$(fg)^{(n)}(x)=\sum _{k=0}^{n}{n \choose k}\ f^{(n-k)}(x)\ g^{(k)}(x).$

Par exemple, $(fg)'''=f'''g+3f''g'+3f'g''+g'''f.$

Combinatoire et statistique

Modèle:Article détaillé Les coefficients binomiaux sont importants en combinatoire, parce qu'ils fournissent des formules utilisées dans des problèmes fréquents de dénombrement :

• Le nombre de parties à Modèle:Mvar éléments dans un ensemble à Modèle:Mvar éléments est égal à $\textstyle {n \choose k}$. C'est également le nombre de listes de longueur Modèle:Mvar, constituées de 1 et de 0, et ayant Modèle:Mvar fois l'élément 1 et Modèle:Mvar l'élément 0. Ces parties ou ces listes sont appelées des [[Combinaison (mathématiques)|Modèle:Mvar-combinaisons]] sans répétition.
• Le nombre de suites de Modèle:Mvar entiers naturels dont la somme vaut Modèle:Mvar est égale à $\textstyle {n+k-1 \choose k}$. C'est aussi le nombre de façons de choisir Modèle:Mvar éléments d'un ensemble à Modèle:Mvar éléments si les répétitions sont permises (nombre de combinaisons avec répétition).
• En théorie des probabilités et en statistique, les coefficients de binôme apparaissent dans la définition de la loi binomiale.
• Ils interviennent dans la définition des polynômes de Bernstein et dans l'équation paramétrique d'une courbe de Bézier.
• D'un point de vue plus intuitif, ce nombre permet de savoir combien de tirages de Modèle:Mvar éléments parmi n différents on peut réaliser. Exemple : les quatre as d'un jeu de cartes sont face contre table, on veut savoir combien de possibilités de jeu il existe si l'on prend simultanément deux cartes au hasard. Si l'on suit la formule il y en a six.

  Pour s'en persuader, voici la liste des mains :

  1. as de cœur et as de carreau
  2. as de cœur et as de trèfle
  3. as de cœur et as de pique
  4. as de carreau et as de trèfle
  5. as de carreau et as de pique
  6. as de trèfle et as de pique

Il n'existe pas d'autres possibilités vu que l'ordre n'importe pas (« carreau - pique » est équivalent à « pique - carreau »).

Diviseurs et coefficients binomiaux

• Un entier Modèle:Math est premier si et seulement si tous les $\textstyle {n \choose k}$ pour Modèle:Math sont divisibles par Modèle:Mvar.

• Les diviseurs premiers de $\textstyle {n \choose k}$ possèdent la propriété suivante (Modèle:Lien) :

Si Modèle:Mvar est un nombre premier et Modèle:Mvar est la plus grande puissance de Modèle:Mvar qui divise $\textstyle {n \choose k}$, alors Modèle:Mvar est égal au nombre d'entiers naturels Modèle:Mvar tels que la partie fractionnaire de Modèle:Mvar soit plus grande que la partie fractionnaire de Modèle:Mvar. C'est le nombre de retenues dans l'addition de Modèle:Mvar et Modèle:Mvar, lorsque ces deux nombres sont écrits en base Modèle:MvarModèle:,.

En particulier, $\textstyle {n \choose k}$ est toujours divisible par $\textstyle {\frac {n}{\mathrm {pgcd} \,(n,k)}}$ (pgcd signifie plus grand commun diviseur).

La règle permet de déterminer les $\textstyle {n \choose k}$ qui sont pairs. Il suffit pour cela de prendre Modèle:Math et Modèle:Math. La soustraction de Modèle:Mvar par Modèle:Mvar nécessite donc au moins une retenue en binaire. Cela signifie que, dans le développement binaire de Modèle:Mvar, il se trouve au moins un 0 situé au même rang qu'un 1 dans le développement binaire de Modèle:Mvar.

À l'inverse, $\textstyle {n \choose k}$ est impair si, à chaque fois que Modèle:Mvar possède un 1 dans son développement binaire, il en est de même de Modèle:Mvar au même rang. On dit que Modèle:Mvar implique Modèle:Mvar. Par exemple, si Modèle:Mvar est de la forme Modèle:Math, tous ses chiffres binaires valent 1, et tous les $\textstyle {n \choose k}$ seront impairs. Si Modèle:Math, alors Modèle:Mvar possède un seul 1 dans son développement binaire, et seuls $\textstyle {n \choose 0}$ et $\textstyle {n \choose n}$ sont impairs, tous les autres sont pairs.

Généralisations

Tout d'abord, comme dit plus haut, l'interprétation combinatoire amène à poser conventionnellement $\textstyle {n \choose k}=0$ pour Modèle:Math (puisqu'il n'existe pas de sous-ensembles à Modèle:Mvar éléments d'un ensemble à Modèle:Mvar éléments si Modèle:Math), et également $\textstyle {n \choose k}=0$ pour Modèle:Math.

L'écriture de $\textstyle {n \choose k}$, pour tout entier Modèle:Mvar et tout entier Modèle:Mvar compris entre 1 et Modèle:Mvar, sous la forme $\textstyle {n \choose k}={\frac {\prod _{i=0}^{k-1}(n-i)}{k!}}$ permet d'envisager une extension possible aussi pour tout entier Modèle:Mvar négatif et tout entier Modèle:Mvar strictement positif en utilisant l'expression suivante :

${n \choose k}={\frac {\displaystyle \prod _{i=0}^{k-1}(n-i)}{k!}}$

Si l'on pose Modèle:Math, on a la relation suivante :

${-m \choose k}={m+k-1 \choose k}(-1)^{k}$

C'est cette forme des coefficients binomiaux qui est utilisée dans la formule du binôme négatif ainsi que dans la définition de la loi binomiale négative

Pour tout nombre complexe Modèle:Mvar et tout entier naturel Modèle:Mvar, on définit le coefficient binomial $\textstyle {z \choose k}$ de la manière suivante :

${z \choose k}={\frac {z(z-1)(z-2)\cdots (z-k+1)}{k!}}={\frac {(z)_{k}}{k!}}$

où $(\cdot )_{k}$ est le symbole de Pochhammer pour les factorielles descendantes (en particulier, $\textstyle {z \choose 0}={\frac {(z)_{0}}{0!}}={\frac {1}{1}}=1$).

C'est cette forme des coefficients binomiaux qui est utilisée dans la formule du binôme généralisée.

Pour tout entier Modèle:Mvar, l'expression $\textstyle {z \choose k}$ est un polynôme en Modèle:Mvar de degré Modèle:Mvar à coefficients rationnels. Tout polynôme Modèle:Math de degré Modèle:Mvar peut réciproquement être écrit sous la forme

$p(z)=\sum _{k=0}^{d}a_{k}{z \choose k}$ ;

on aboutit ainsi, par exemple, aux formules de Faulhaber.

Une autre généralisation importante des coefficients binomiaux part de la formule du multinôme, laquelle permet de définir les coefficients multinomiaux.

Enfin, le calcul de $\textstyle {n \choose k}$ peut se généraliser, à l'aide de la fonction Gamma. On remarque que, pour tout entier naturel Modèle:Mvar, Modèle:Math, ainsi, l'on a, pour tout entier Modèle:Mvar et pour tout entier Modèle:Mvar inférieur ou égal à Modèle:Mvar,

${n \choose k}={\frac {\Gamma (n+1)}{\Gamma (k+1)\Gamma (n-k+1)}}$

Comme la fonction Modèle:Math est définie pour tout complexe de $\mathbb {C} \backslash \mathbb {Z} _{-}$, on peut généraliser le coefficient binomial à tous complexes Modèle:Mvar et Modèle:Mvar différents des entiers négatifs et tels que Modèle:Mvar ne soit pas un entier négatif, par la formule :

${s \choose t}={\frac {\Gamma (s+1)}{\Gamma (t+1)\Gamma (s-t+1)}}$;

Cette formule peut d'ailleurs s'écrire plus simplement à l'aide de la fonction bêta :

${s \choose t}={\frac {1}{(s+1)\mathrm {B} (t+1,s-t+1)}}$;

On peut tenter d'unifier les définitions avec la fonction Gamma, en résolvant le problème de pôles de cette fonction par un passage à la limite :

${s \choose t}=\lim _{u\to s}\lim _{v\to t}{\frac {\Gamma (u+1)}{\Gamma (v+1)\Gamma (u-v+1)}}$

L'ordre des limites est important. Cette définition donne une valeur infinie au coefficient binomial dans le cas où Modèle:Mvar est un entier négatif et Modèle:Mvar n'est pas un entier (ce qui n'est pas en contradiction avec la définition précédente puisqu'elle ne prenait pas en compte ce cas là).

Formules faisant intervenir les coefficients binomiaux

On suppose que Modèle:Math sont des entiers ; Modèle:Math des complexes.

On rappelle que :

${n \choose k}+{n \choose k+1}={n+1 \choose k+1}\qquad {\mbox{(2)}}$ (formule de Pascal)

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}\qquad (3)$ (formule du binôme de Newton)

Les formules suivantes peuvent être utiles :

${n \choose k}={n \choose n-k}\qquad (4)$

${n \choose k}={\frac {n}{k}}{n-1 \choose k-1}\qquad (k>0)$ et plus généralement ${z \choose k}={\frac {z}{k}}{z-1 \choose k-1}\qquad (5)$.

En remplaçant dans (3) Modèle:Math, on obtient

$\sum _{k=0}^{n}{n \choose k}=2^{n}\qquad (6)$ ;

De nombreuses formules analogues peuvent être obtenues ainsi ; par exemple, avec Modèle:Math et Modèle:Math, on obtient

$\sum _{k=0}^{n}(-1)^{k}{n \choose k}=0$ si Modèle:Math ;

avec Modèle:Math et Modèle:Math (donc Modèle:Math), on obtient

$\sum _{k=0}^{n}(-1)^{k}{n \choose 2k}=\operatorname {Re} ((1+i)^{n})=2^{n/2}\cos(n\pi /4)$.

Dans l'identité (3), en remplaçant Modèle:Mvar par 1 et en prenant la dérivée en 1 par rapport à Modèle:Mvar, il vient

$\sum _{k=1}^{n}k{n \choose k}=n2^{n-1}\qquad (7)$

En développant Modèle:Math avec (3), on obtient l'identité de Vandermonde :

$\sum _{j=0}^{r}{n \choose j}{m \choose r-j}={n+m \choose r}$ et plus généralement $\sum _{j=0}^{r}{z \choose j}{z' \choose r-j}={z+z' \choose r}\qquad (8)$

À partir du développement (8), en remplaçant Modèle:Mvar et Modèle:Mvar par Modèle:Mvar et en utilisant (4), on obtient

$\sum _{j=0}^{n}{n \choose j}^{2}={2n \choose n}\qquad (9)$.

En développant Modèle:Math et en observant le coefficient devant Modèle:Math, on obtient

$\sum _{k=0}^{2n}(-1)^{k}{2n \choose k}^{2}=(-1)^{n}{2n \choose n}\qquad (10)$ .

On a

$\sum _{k=0}^{n}{n-k \choose k}=F(n+1)\qquad (11)$,

où Modèle:Math désigne le Modèle:Math-ième terme de la suite de Fibonacci. Cette formule sur les diagonales du triangle de Pascal peut être démontrée par une récurrence sur Modèle:Mvar en utilisant (2).

Pour tous entiers naturels Modèle:Mvar, Modèle:Mvar et Modèle:Math,

$\sum _{j=n}^{r-m}{\binom {j}{n}}{\binom {r-j}{m}}={\binom {r+1}{m+n+1}}\qquad (12)$

Cet analogue de l'identité de Vandermonde (8) peut se démontrer de la même façon, à partir de la formule du binôme négatif. Un cas particulier est (pour tous entiers Modèle:Math) :

$\sum _{j=n}^{r}{\binom {j}{n}}={\binom {r+1}{n+1}}$.

Voir aussi

Bibliographie

• Modèle:Ouvrage
• Modèle:En Henry W. Gould, Modèle:Lang, 2010, vol. 1 à 8
• Modèle:Ouvrage