Coefficient binomial

Infos
Les coefficients binomiaux interviennent dans de nombreux domaines des mathématiques : développement du binôme, dénombrement, développement en série…
Coefficient binomial

Les coefficients binomiaux interviennent dans de nombreux domaines des mathématiques : développement du binôme, dénombrement, développement en série…

Définition

Coefficient binomial d'entiers

Le coefficient binomial des entiers naturels n et k est noté n \choose k ou C_n^k et vaut : :\fracn (n -1)(n - 2)\cdots (n - k +1) = \begin\displaystyle \frac & \mbox k \in \!] \quad\mbox \\\qquad 0 & \mbox\end Ici n ! désigne la factorielle de n. 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 bien n \choose k et se lit « k parmi n ». Une importante relation, la formule de Pascal, lie les coefficients binomiaux : : n \choose k + n \choose k+1 = n+1 \choose k+1 \qquad \mbox Elle donne lieu au triangle de Pascal qui permet un calcul rapide des coefficients pour de petites valeurs de n : 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 Les coefficients n \choose k, k \in \!] figurent à la ne 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. Cette méthode permet le calcul rapide des coefficients binomiaux sans division ni multiplication. Note : pour k \in \!], le coefficient binomial est un nombre entier. Boîte déroulante |titre=Preuve | contenu=La preuve de cette propriété se fait par induction :
- Pour \qquad n = 0, c'est évident.
- Supposons que c'est vrai pour \qquad n = m, \qquad (m \ge 1) .
- Regardons ce qui se passe lorsque \qquad n = m + 1 : :pour \qquad k = 1, \cdots , m , la formule de Pascal \qquad \mbox donne m+1 \choose k = m \choose k + m \choose k-1 \qquad on y voit que \qquad m+1 \choose 1, m+1 \choose 2, \cdots , m+1 \choose m \qquad sont des entiers étant chacun la somme de deux entiers, alors que m+1 \choose 0=1 \qquad et \qquad m+1 \choose m+1=1 \qquad .
- La propriété est donc vraie pour \qquad n = m + 1 \qquad, elle est par conséquent vraie pour tout \qquad n \qquad.

Généralisation aux nombres complexes

Pour tout nombre complexe z et tout entier naturel k, on définit le coefficient binomial z \choose k de la manière suivante : :z \choose k = \fracz(z-1)(z-2)\cdots (z-k+1) \qquad (3) Pour tout entier k, l'expression z \choose k est un polynôme en z de degré k à coefficients rationnels. Tout polynôme p(z) de degré d peut être écrit sous la forme : p(z) = \sum_^ a_k z \choose k

Utilisation des coefficients binomiaux

Développement du binôme de Newton

Ces nombres sont les coefficients qui apparaissent en développant la puissance ne de x + y : : (x+y)^n = \sum_^ n \choose k x^k y^ \qquad (4) Par exemple, en regardant la cinquième ligne du triangle de Pascal, on obtient immédiatement que : :\ (x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5\, . La formule du binôme généralisé permet d'étendre la formule précédente au cas où l'exposant n est négatif ou non entier, voire même complexe.

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 :
- Le nombre de parties à k éléments dans un ensemble à n éléments est égal à n \choose k. C'est également le nombre de listes de longueur n, constituées de 1 et de 0, et ayant k = 1 et n-k = 0. Ces parties ou ces listes sont appelées des k-combinaisons sans répétition.
- Le nombre de suites de n entiers naturels dont la somme vaut k est égale à n+k-1 \choose 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).
- En probabilité et 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 k éléments parmi n différents on peut réaliser. Exemple: les quatre as d'un jeu de carte 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 :
- as de cœur et as de carreau
- as de cœur et as de trèfle
- as de cœur et as de pique
- as de carreau et as de trèfle
- as de carreau et as de pique
- 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

Les diviseurs premiers de n \choose 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 n \choose k, alors r\quad est égal au nombre d'entiers naturels j\quad tels que la partie fractionnaire de \frac\, soit plus grande que la partie fractionnaire de \frac\, . C'est le nombre de retenues dans la soustraction de n par k, lorsque ces deux nombres sont écrits en base p. En particulier, n \choose k est toujours divisible par n/\mbox\, (n, k) (pgcd signifie plus grand commun diviseur). La règle permet de déterminer les n \choose k qui sont pairs. Il suffit pour cela de prendre p=2 et r \ge 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. A l'inverse, 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^p-1, tous ses chiffres binaires valent 1, et tous les n \choose k seront impairs. Si n=2^p, alors n possède un seul 1 dans son développement binaire, et seuls n \choose 0 et n \choose n sont impairs, tous les autres sont pairs.

Formules faisant intervenir les coefficients binomiaux

Les formules suivantes peuvent être utiles : ::n \choose k = n \choose n-k \qquad (5) ::n \choose k = \fracn-1 \choose k-1 \qquad(k>0) et plus généralement z \choose k = \fracz-1 \choose k-1\qquad (6) Ces deux formules se montrent facilement à partir de la définition (1). En remplaçant dans (4) x = y = 1, on obtient :: \sum_^ n \choose k = 2^n \qquad (7) En dérivant (4), et en remplaçant x = y = 1, il vient :: \sum_^ k n \choose k = n 2^ \qquad (8) En développant (x + y)^n.(x + y)^m = (x + y)^\, avec (4), on obtient l'identité de Vandermonde : :: \sum_^ m \choose j n \choose k-j = m+n \choose k et plus généralement \sum_^ z \choose j z' \choose k-j = z+z' \choose k \qquad (9) À partir du développement (9), en remplaçant m = k = n et en utilisant (5), on obtient :: \sum_^ n \choose k^2 = 2n \choose n \qquad (10) On a, :: \sum_^ n-k \choose k = \mathcal(n+1) \qquad (11) Ici, F(n+1) désigne le n+1 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 n en utilisant (2). Et enfin, :: \sum_^ j \choose k = n+1 \choose k+1 \qquad (12) Cela peut être démontré par récurrence sur n en utilisant (2).

Voir aussi

- Arrangement Catégorie:Analyse combinatoire bg:Биномен коефициент bn:দ্বিপদী সহগ cs:Kombinační číslo da:Binomialkoefficient de:Binomialkoeffizient en:Binomial coefficient eo:Simbolo de Newton es:Coeficiente binomial fi:Binomikerroin it:Coefficiente binomiale ko:이항계수 lt:Deriniai nl:Binomiaalcoëfficiënt no:Binomialkoeffisient pl:Symbol Newtona ru:Биномиальный коэффициент sl:Binomski koeficient sr:Биномни коефицијент sv:Binomialkoefficient uk:Біноміальний коефіцієнт zh:二項式係數
Sujets connexes
Arrangement (mathématiques)   Base (arithmétique)   Binôme (mathématique)   Binôme généralisé   Combinaison (mathématiques)   Combinaison avec répétition   Combinatoire   Courbe de Bézier   Division   Dénombrement   Entier naturel   Factorielle   Identité de Vandermonde   Loi binomiale   Nombre complexe   Nombre rationnel   Plus grand commun diviseur   Polynôme   Polynôme de Bernstein   Probabilité   Raisonnement par récurrence   Somme (arithmétique)   Statistique   Suite de Fibonacci   Système binaire   Série (mathématiques)   Triangle de Pascal  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^