En mathématiques, les coefficients binomiaux, ou coefficients du binôme, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties à k éléments d'un ensemble à n éléments. On les note^[1] ${\displaystyle \textstyle {n \choose k}}$ - qui se lit « k parmi n » - ou ${\displaystyle \textstyle {C_{n}^{k}}}$, la lettre C étant l'initiale du mot « combinaison »

Les coefficients binomiaux s'expriment à l'aide de la fonction factorielle :

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

Ils 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.

Lecture et expressions dans divers langages informatiques

Le coefficient binomial ${\displaystyle \textstyle {n \choose k}}$ se lit « k parmi n » en français, mais « n choose k » en anglais. Cette inversion de l'ordre de n et k se retrouve dans les langages informatiques ; par exemple, ${\displaystyle \textstyle {n \choose k}}$ se note :

• binom(n,k) ou comb(n,k) dans les modules math ou scipy de Python^[2]
• binomial(n,k) en Maple^[3]
• Binomial[n,k] en Mathematica^[4]
• \binom{n}{k} ou n \choose k en LaTex

Établissement de la formule

L'expression ${\displaystyle \textstyle {n \choose k}}$ du nombre de parties à k éléments, c'est-à-dire du nombre de k-combinaisons dans un ensemble à n éléments, se détermine en calculant de deux façons différentes le nombre de k-arrangements dans cet ensemble, à savoir

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

La confrontation des deux calculs donne l'expression algébrique de ${\displaystyle \textstyle {n \choose k}}$, pour k variant de 0 à n^[5] :

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

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

Si k est strictement négatif ou strictement supérieur à n, le coefficient binomial est nul.

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

Définition récursive des coefficients binomiaux

Une importante relation, la formule de Pascal, lie les coefficients binomiaux : pour tout couple (n,k) d'entiers naturels^[6],

${\displaystyle {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^[7], mais on peut aussi utiliser la forme factorielle^[8].

Elle est à la base de la construction du triangle de Pascal qui permet un calcul rapide des coefficients pour de petites valeurs de n :

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 ${\displaystyle \textstyle {n \choose k}}$ pour 0 ≤ k ≤ n figurent à la ligne d'indice n. 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. k se lit de gauche à droite sur la ligne d'indice n en partant de 0 jusqu'à n.

Utilisation des coefficients binomiaux

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

Si n est un entier supérieur ou égal à 1, et f et g deux fonctions n fois dérivables en un point x, alors leur produit fg est aussi n fois dérivable au point x, et la dérivée d'ordre n est donnée par la formule de Leibniz :

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

Par exemple, ${\displaystyle (fg)'''=f'''g+3f''g'+3f'g''+g'''f.}$

Propriétés arithmétiques des coefficients binomiaux

Divisibilité

• Un entier n ≥ 2 est premier si et seulement si tous les ${\displaystyle \textstyle {n \choose k}}$ pour k = 1, … , n – 1 sont divisibles par n.

Démonstration

Pour 0 < k < n, de (formule du pion)

${\displaystyle k{n \choose k}=n{n-1 \choose k-1}}$

on déduit que :

• si n est premier, comme il ne divise pas k, il divise ${\displaystyle \textstyle {n \choose k}}$ d'après le lemme d'Euclide ;
• si n est composé et si k est un de ses facteurs premiers, alors n ne divise pas

${\displaystyle {n \choose k}={\frac {n}{k}}{n-1 \choose k-1}}$

car k ne divise pas

${\displaystyle {n-1 \choose k-1}={\frac {(n-1)(n-2)\ldots (n-k+1)}{(k-1)!}}}$

puisque k, divisant n, ne divise aucun des k – 1 entiers qui le précèdent.

• Les diviseurs premiers de ${\displaystyle \textstyle {n \choose k}}$ possèdent la propriété suivante (théorème de Kummer (coefficients binomiaux)) :

Si p est un nombre premier et p^r est la plus grande puissance de p qui divise ${\displaystyle \textstyle {n \choose k}}$, alors r est égal au nombre d'entiers naturels j tels que la partie fractionnaire de ^k⁄_p^j soit plus grande que la partie fractionnaire de ⁿ⁄_p^j. C'est le nombre de retenues dans l'addition de k et n – k, lorsque ces deux nombres sont écrits en base p^[9],[10].

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

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

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

Généralisations

Élargissement du domaine de définition

Jusqu'à présent le coefficient binomial ${\textstyle {n \choose k}}$ était défini pour k et n entiers naturels avec k ≤ n. Il existe plusieurs manières d'étendre le domaine de définition (ces différentes extensions de la définition étant compatibles les unes avec les autres).

• Tout d'abord, l'interprétation combinatoire des coefficients binomiaux amène à poser ${\textstyle {n \choose k}=0}$ pour n < k. En effet, il n'existe pas de sous-ensembles à k éléments d'un ensemble à n éléments si n < k.

• Pour tout entier naturel n et tout entier naturel k compris entre 0 et n, le coefficient binomial ${\textstyle {n \choose k}}$ satisfait la formule ${\textstyle {n \choose k}={\frac {1}{k!}}\prod _{i=0}^{k-1}(n-i)}$. Le terme de droite dans cette égalité a toujours un sens lorsque n est un entier relatif et même un nombre réel ou complexe et lorsque k est un entier naturel quelconque. Si l'on utilise le symbole de Pochhammer ${\displaystyle (\cdot )_{k}}$ pour les factorielles descendantes, alors pour tout nombre réel ou complexe z et entier naturel k on peut définir le coefficient binomial ${\textstyle {z \choose k}}$ par la formule : ${\displaystyle {z \choose k}={\frac {1}{k!}}\prod _{i=0}^{k-1}(z-i)={\frac {z(z-1)(z-2)\cdots (z-k+1)}{k!}}={\frac {(z)_{k}}{k!}}}$. C'est cette définition des coefficients binomiaux qui est utilisée dans la formule du binôme négatif, dans la formule du binôme généralisée ainsi que dans la définition de la loi binomiale négative (généralisée à un premier paramètre réel).

• Il existe une autre manière de définir ${\textstyle {n \choose k}}$ pour k entier naturel et n entier relatif par la formule : ${\displaystyle {n \choose k}={-n+k-1 \choose k}(-1)^{k}}$qui ramène au cas initial lorsque n est négatif.

• Il est possible de poser ${\textstyle {n \choose k}=0}$ lorsque k est un entier négatif. L'avantage de cette convention est qu'elle conserve la plupart des formules établies jusqu'ici vraies.
• La définition de ${\textstyle {n \choose k}}$ peut se généraliser, à l'aide de la fonction gamma Γ. Pour tout entier naturel n, n! = Γ(n+1), ainsi, pour tout entier naturel n et pour tout entier naturel k ≤ n on a : ${\displaystyle {n \choose k}={\frac {\Gamma (n+1)}{\Gamma (k+1)\Gamma (n-k+1)}}}$. Comme la fonction Γ est définie pour tout complexe qui n'est pas un entier négatif ou nul, on peut généraliser le coefficient binomial à tous complexes w et z qui ne sont pas des entiers négatifs ou nuls et tels que z - w ne soit pas un entier négatif ou nul, par la formule : ${\displaystyle {z \choose w}={\frac {\Gamma (z+1)}{\Gamma (w+1)\Gamma (z-w+1)}}}$. Cette formule peut d'ailleurs s'écrire plus simplement à l'aide de la fonction bêta B : ${\displaystyle {z \choose w}={\frac {1}{(z+1)\mathrm {B} (w+1,z-w+1)}}}$.
• Enfin, il est possible d'unifier toutes les définitions précédentes avec la fonction gamma, en résolvant le problème de pôles de cette fonction par un passage à la limite : ${\displaystyle {z \choose w}=\lim _{u\to z}\lim _{v\to w}{\frac {\Gamma (u+1)}{\Gamma (v+1)\Gamma (u-v+1)}}}$. Dans cette dernière formule, l'ordre des limites est important^[12]. Cette définition donne une valeur infinie au coefficient binomial dans le cas où z est un entier négatif non nul et w n'est pas un entier strictement négatif.

Récapitulatif des généralisations^[13]

Généralisation	Domaine de définition	Définition	Notations et remarques
${\displaystyle {\binom {n}{k}}}$	${\displaystyle n\in \mathbb {N} }$ ${\displaystyle k\in \{0,1,\dots ,n\}}$	${\displaystyle {\frac {n!}{k!(n-k)!}}}$	${\displaystyle n!=1\times 2\times \dots \times n}$ ${\displaystyle 0!=1}$
${\displaystyle {\binom {n}{k}}}$	${\displaystyle n\in \mathbb {N} }$ ${\displaystyle k\in \mathbb {N} }$	${\displaystyle \left\{{\begin{array}{cl}{\frac {n!}{k!(n-k)!}}&{\text{ si }}k\leq n\\0&{\text{ sinon}}\end{array}}\right.}$
${\displaystyle {\binom {z}{k}}}$	${\displaystyle z\in \mathbb {C} }$ ${\displaystyle k\in \mathbb {N} }$	${\displaystyle {\frac {(z)_{k}}{k!}}}$	${\displaystyle (z)_{k}=z(z-1)\dots (z-k+1)}$ ${\displaystyle (z)_{0}=1}$
${\displaystyle {\binom {z}{k}}}$	${\displaystyle z\in \mathbb {C} }$ ${\displaystyle k\in \mathbb {Z} }$	${\displaystyle \left\{{\begin{array}{cl}{\frac {(z)_{k}}{k!}}&{\text{ si }}k\geq 0\\0&{\text{ sinon}}\end{array}}\right.}$
${\displaystyle {\binom {z}{w}}}$	${\displaystyle z\in \mathbb {C} \setminus (-\mathbb {N} )^{*}}$ ${\displaystyle w\in \mathbb {C} \setminus (-\mathbb {N} )^{*}}$ ${\displaystyle z-w\notin (-\mathbb {N} )^{*}}$	${\displaystyle {\frac {\Gamma (z+1)}{\Gamma (w+1)\Gamma (z-w+1)}}}$	${\displaystyle \Gamma }$ désigne la fonction gamma. ${\displaystyle (-\mathbb {N} )^{*}=\{-1,-2,-3,\dots \}}$
${\displaystyle {\binom {z}{w}}}$	${\displaystyle z\in \mathbb {C} }$ ${\displaystyle w\in \mathbb {C} }$	${\displaystyle \lim _{u\to z}\lim _{v\to w}{\frac {\Gamma (u+1)}{\Gamma (v+1)\Gamma (u-v+1)}}}$	${\displaystyle {\binom {z}{w}}=\infty {\text{ si }}z\in (-\mathbb {N} )^{*}{\text{ et }}w\notin (-\mathbb {N} )^{*}}$ ${\displaystyle {\binom {z}{w}}=0{\text{ si }}z,w\notin (-\mathbb {N} )^{*}{\text{ et }}z-w\in (-\mathbb {N} )^{*}}$

Formules faisant intervenir les coefficients binomiaux

On suppose que k, n sont des entiers ; x, y, z, z′ des complexes.

On rappelle que :

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

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

Les formules suivantes peuvent être utiles :

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

${\displaystyle {n \choose k}={\frac {n}{k}}{n-1 \choose k-1}\qquad (k>0)}$ et plus généralement ${\displaystyle {z \choose k}={\frac {z}{k}}{z-1 \choose k-1}\qquad (5)}$ (formule parfois dite « du pion »^[14]).

En remplaçant dans (3) x = y = 1, on obtient

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

De nombreuses formules analogues peuvent être obtenues ainsi ; par exemple, avec x = 1 et y = −1, on obtient

${\displaystyle \sum _{k}(-1)^{k}{n \choose k}=0}$ si n > 0 ;

avec x = 1 et y = i (donc y² = −1), on obtient

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

Dans l'identité (3), en remplaçant x par 1 et en prenant la dérivée en 1 par rapport à y, il vient

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

En développant (1 + x)ⁿ(1 + x)^m = (1 + x)^m+n avec (3), on obtient l'identité de Vandermonde :

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

À partir du développement (8), en remplaçant m et r par n et en utilisant (4), on obtient

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

En développant (1 + x)²ⁿ(1 – x)²ⁿ = (1 – x²)²ⁿ et en observant le coefficient devant x²ⁿ, on obtient

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

On a

${\displaystyle \sum _{k}{n-k \choose k}=F_{n+1}\qquad (11)}$,

où F_n+1 désigne le (n+1)-ième terme de la suite de Fibonacci^[15].

Pour tous entiers naturels m, n et r ≥ m + n,

${\displaystyle \sum _{j}{\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^[16]. Un cas particulier est (pour tous entiers r ≥ n ≥ 0)^[17] :

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

Encadrement et approximations

L'encadrement suivant fait intervenir le nombre de Neper et est valable pour toute valeur de k et n^[18] :

${\displaystyle \forall \,1\leqslant k\leqslant n,\left({\frac {n}{k}}\right)^{k}\leqslant {\binom {n}{k}}<\mathrm {e} ^{k}\left({\frac {n}{k}}\right)^{k}}$

L'écart entre les deux bornes croit exponentiellement, c'est pourquoi il peut être préférable d'utiliser un équivalent asymptotique lorsque l'on connait le comportement de k par rapport à celui de n. Grâce à la formule de Stirling, lorsque n et k tendent vers l'infini on a :

${\displaystyle {\binom {n}{k}}\sim {\sqrt {\frac {n}{2\pi k(n-k)}}}\cdot {\frac {n^{n}}{k^{k}(n-k)^{n-k}}}}$.

Mais pour être plus précis, il faut particulariser à différents régimes asymptotiques^[18],[19]. Dans les cas ci-dessous, ${\displaystyle h(\alpha )=-\alpha \log _{2}\alpha -(1-\alpha )\log _{2}(1-\alpha )}$ est la fonction entropie binaire (en).

• cas 1 : si ${\displaystyle n\rightarrow \infty }$, ${\displaystyle k>1}$ et ${\displaystyle k={\mathcal {O}}(1)}$ alors ${\displaystyle {\binom {n}{k}}={\frac {n^{k}\prod _{j=0}^{k}(1-{\frac {j}{n}})}{k!}}={\frac {n^{k}}{k!}}\left(1-{\frac {k(k-1)}{2n}}+{\mathcal {O}}\left({\frac {1}{n^{2}}}\right)\right)}$ ;
• cas 2 : si ${\displaystyle k\rightarrow \infty }$ et ${\displaystyle k={\mathcal {o}}(n)}$ alors ${\displaystyle {\binom {n}{k}}\sim {\frac {2^{nh\left({\frac {k}{n}}\right)}}{\sqrt {2\pi k}}}}$^[18] ;
• cas 3 : si ${\displaystyle n\rightarrow \infty }$ et ${\displaystyle k/n\to \alpha \in \left]0,1\right[}$ alors ${\displaystyle {\binom {n}{k}}\sim {\frac {2^{nh(\alpha )}}{\sqrt {2\pi \alpha (1-\alpha )n}}}={\frac {1}{\sqrt {2\pi \alpha (1-\alpha )n}}}\left({\frac {1}{\alpha ^{\alpha }(1-\alpha )^{1-\alpha }}}\right)^{n}}$^[19].

Notes et références

Voir aussi