Coefficient binomial

Le coefficient binomial des entiers naturels n et k, noté ${n \choose k}$ (anciennement $C_n^k$ ) vaut :

$\frac{n!}{k!(n-k)!} \quad \mbox{si } n\geq k\geq 0 \qquad \mbox{(1)}$

$0 \quad \mbox{si } k<0 \mbox{ ou } k>n.$

Ici m ! désigne la factorielle de m. On remarque qu'il existe deux notations : le coefficient binomial de n et k s'écrit

$C_n^k\,$ ou $C(n,k)\,$ et se lit « combinaison de k parmi n » ou aussi « cnk »,
ou encore s'écrit :

${n \choose k}$ et se lit « k parmi n ».

Ces nombres sont les coefficients qui apparaissent en développant la puissance n^e de x + y :

$(x+y)^n = \sum_{k=0}^{n} C_n^k x^k y^{n-k} \qquad (2)$

Ceci est généralisé par le binôme généralisé, qui permet à l'exposant n d'être négatif ou non entier.

Une importante relation, la formule de Pascal, lie les coefficients binomiaux :

$C_n^k + C_n^{k+1} = C_{n+1}^{k+1}$ (3)

Elle donne lieu au triangle de Pascal :

ligne 0                     1
 ligne 1                   1   1
 ligne 2                 1   2   1
 ligne 3               1   3   3   1
 ligne 4             1   4   6   4   1
 ligne 5           1   5   10  10   5   1
 ligne 6         1   6   15  20  15   6   1
 ligne 7       1   7   21  35  35   21  7   1

lequel contient les nombres $C_n^k$ à la n^e ligne. Le triangle est construit en plaçant des uns aux extrémités et en complétant la ligne en reportant la somme des deux nombres adjacents de la ligne supérieure. Cette méthode permet le calcul rapide des coefficients binomiaux sans division ni multiplication. Par exemple, en regardant la cinquième ligne du triangle, on peut voir immédiatement que :

$:(x + y)^5 = 1.x^5 + 5.x^4.y + 10.x^3.y^2 + 10.x^2.y^3 + 5.x.y^4 + 1.y^5\,$ .

Le triangle a été décrit par Zhu Shijie en 1303 dans son livre le Miroir de Jade des Quatre Inconnues. Dans ce livre, Zhu présente le triangle comme une méthode ancienne (de plus 200 années avant son temps) pour déterminer les coefficients du binôme, et indique que la méthode était connue des mathématiciens chinois cinq siècles avant Pascal. Le mathématicien arabe al-Karaji (953 - 1029) a également obtenu le triangle de Pascal plus d'un demi-millénaire avant Pascal.

Si vous colorez dans ce triangle tous les nombres pairs et retirez tous les nombres impairs vous obtenez le triangle de Sierpinski. Essayez de colorer les multiples de 3, 4, 5, et ainsi de suite et voyez quels motifs émergent !

Sommaire

1 Combinatoire et statistique

2 Diviseurs et coefficients binomiaux

3 Formules faisant intervenir les coefficients binomiaux

4 Généralisation aux nombres complexes

5 Voir aussi

Combinatoire et statistique

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

tout ensemble fini à n éléments possède $C_n^k$ parties différentes ayant k éléments chacune (ces parties sont appelées des k-combinaisons)
Le nombre de n-listes (listes de longueur n) ayant k uns et n-k zéros est égal à $C_n^k$
il y a $C_{n+1}^k$ listes ayant k uns n zéros telles que jamais deux zéros ne soient adjacents. ( ceci est faux )
Le nombre de suites de n entiers naturels dont la somme vaut k est égale à $C_{n+k-1}^k$ ; c'est aussi le nombre de façons de choisir k éléments d'un ensemble à n éléments si les répétitions sont permises (nombre de combinaisons avec répétition).

Les coefficients de binôme apparaîssent aussi dans la formule d'une distribution binomiale en probabilité et statistique, dans les polynômes de Bernstein et dans l'équation paramétrique d'une courbe de Bézier.

Diviseurs et coefficients binomiaux

Les diviseurs premiers de $C_n^k$ possèdent la propriété suivante : Si $p\quad$ est un nombre premier et $p^r\quad$ est la plus grande puissance de $p\quad$ qui divise $C_n^k$ , alors $r\quad$ est égal au nombre d'entiers naturels $j\quad$ tels que la partie fractionnaire de $\frac{k}{p^j}\,$ soit plus grande que la partie fractionnaire de $\frac{n}{p^j}\,$ . En particulier, $C_n^k$ est toujours divisible par $n/\mbox{pgcd}\,(n,k)$ (pour pgcd voir ici).

Formules faisant intervenir les coefficients binomiaux

Les formules suivantes peuvent être utiles :

Cette formule des compléments, provient du développement de (2) et de $(x + y)^n = (y + x)^n\,$ .

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

$\sum_{k=0}^{n} C_n^k = 2^n \qquad (6)$

En dérivant (2), et en remplaçant x = y = 1, il vient

$\sum_{k=1}^{n} k C_n^k = n 2^{n-1} \qquad (7)$

En développant ( $x + y)^n.(x + y)^m = (x + y)^{m +n}\,$ avec (2), on obtient la formule de Vandermonde :

$\sum_{j=0}^{k} C_m^j C_n^{k-j} = C_{m+n}^k \qquad (8)$

(remarquons que C(n, k) est égale à zéro si k > n). Cette relation généralise (3).

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

$\sum_{k=0}^{n} (C_n^k)^2 = C_{2n}^n \qquad (9)$

On a,

$\sum_{k=0}^{n} C_{n-k}^k = \mathrm{F}(n+1) \qquad (10)$

Ici, F(n+1) désigne le n+1 è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 n en utilisant (3).

Et enfin,

$\sum_{j=k}^{n} C_j^k = C_{n+1}^{k+1} \qquad (11)$

Cela peut être démontré par récurrence sur n en utilisant (3).

Généralisation aux nombres complexes

Le coefficient binomial ${z \choose k}$ peut être défini pour tout nombre complexe z et tout entier naturel k de la manière suivante :

${z \choose k} = \frac{z(z-1)(z-2)\dots (z-k+1)}{k!} \qquad (12)$

Cette généralisation est utilisée dans la formulation du théorème du binôme et satisfait les propriétés (3) et (8).

Pour tout entier k, l'expression ${z \choose k}$ est un polynôme en z de degrée k à coefficients rationnels. Tout polynôme p(z) de degré d peut être écrit sous la forme

$p(z) = \sum_{k=0}^{d} a_k {z \choose k}$

avec des constantes a_k.

Voir aussi

Arrangement