Coefficient binomial
En mathématiques, les coefficients binomiaux, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties de k éléments dans un ensemble de n éléments. On les note (lu « k parmi n » ) ou Ck
n (lu « combinaison de k parmi n »).
Les deux notations sont préconisées par la norme ISO 80000-2:2009[1] : la première est celle du « coefficient binomial » (2-10.4) et la seconde celle du « nombre de combinaisons sans répétition » (2-10.6).
Cette quantité s'exprime à l'aide de la fonction factorielle :
- .
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 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
La confrontation des deux calculs donne l'expression algébrique de , pour k variant de 0 à n[2] :
en particulier, (dans un ensemble à n éléments, il y a exactement une partie à 0 élément : l'ensemble vide) et de même, .
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 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
Une importante relation, la formule de Pascal, lie les coefficients binomiaux : pour tout couple (n,k) d'entiers naturels[3],
On la démontre classiquement par un raisonnement combinatoire élémentaire[4], mais on peut aussi utiliser la forme factorielle[5].
Elle donne lieu au 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 pour 0 ≤ k ≤ n figurent à la n-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. k se lit de gauche à droite sur la n-ième ligne en partant de 0 jusqu'à n.
Utilisation des coefficients binomiaux
Développement du binôme de Newton
Ces nombres sont les coefficients qui apparaissent en développant la puissance n-ième de x + y :
Par exemple, en regardant la cinquième ligne du triangle de Pascal, on obtient immédiatement que :
- .
Dérivée d'ordre n d'un produit de fonctions
Soient n 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 :
Par exemple,
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 à . C'est également le nombre de listes de longueur n, constituées de 1 et de 0, et ayant k fois l'élément 1 et n–k l'élément 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 à . 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 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 k é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 :
- 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
- Un entier n ≥ 2 est premier si et seulement si tous les pour k = 1, … , n – 1 sont divisibles par n.
- Les diviseurs premiers de possèdent la propriété suivante (théorème de Kummer sur les coefficients binomiaux (en)) :
Si p est un nombre premier et pr est la plus grande puissance de p qui divise , alors r est égal au nombre d'entiers naturels j tels que la partie fractionnaire de k⁄pj soit plus grande que la partie fractionnaire de n⁄pj. C'est le nombre de retenues dans l'addition de k et n – k, lorsque ces deux nombres sont écrits en base p[6],[7].
En particulier, est toujours divisible par (pgcd signifie plus grand commun diviseur).
La règle permet de déterminer les 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, 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 2p – 1, tous ses chiffres binaires valent 1, et tous les seront impairs. Si n = 2p, alors n possède un seul 1 dans son développement binaire, et seuls et 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 pour n < k (puisqu'il n'existe pas de sous-ensembles à k éléments d'un ensemble à n éléments si n < k), et également pour k < 0.
L'écriture de , pour tout entier n et tout entier k compris entre 1 et n, sous la forme permet d'envisager une extension possible aussi pour tout entier n négatif et tout entier k strictement positif en utilisant l'expression suivante :
Si l'on pose n = –m, on a la relation suivante :
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 z et tout entier naturel k, on définit le coefficient binomial de la manière suivante :
où est le symbole de Pochhammer pour les factorielles descendantes (en particulier, ).
C'est cette forme des coefficients binomiaux qui est utilisée dans la formule du binôme généralisée.
Pour tout entier k, l'expression est un polynôme en z de degré k à coefficients rationnels. Tout polynôme p(z) de degré d peut réciproquement être écrit sous la forme
- ;
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 peut se généraliser, à l'aide de la fonction Gamma. On remarque que, pour tout entier naturel n, n! = Γ(n+1), ainsi, l'on a, pour tout entier n et pour tout entier k inférieur ou égal à n,
Comme la fonction Γ est définie pour tout complexe de , on peut généraliser le coefficient binomial à tous complexes s et t différents des entiers négatifs et tels que s − t ne soit pas un entier négatif, par la formule :
- ;
Cette formule peut d'ailleurs s'écrire plus simplement à l'aide de la fonction bêta :
- ;
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 :
L'ordre des limites est important[8]. Cette définition donne une valeur infinie au coefficient binomial dans le cas où s est un entier négatif et t 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 k, n sont des entiers ; x, y, z, z′ des complexes.
On rappelle que :
- (formule de Pascal)
Les formules suivantes peuvent être utiles :
- et plus généralement (formule parfois dite "du pion" [9]).
En remplaçant dans (3) x = y = 1, on obtient
- ;
De nombreuses formules analogues peuvent être obtenues ainsi ; par exemple, avec x = 1 et y = −1, on obtient
- si n > 0 ;
avec x = 1 et y = i (donc y2 = −1), on obtient
- .
Dans l'identité (3), en remplaçant x par 1 et en prenant la dérivée en 1 par rapport à y, il vient
En développant (x + y)n(x + y)m = (x + y)m+n avec (3), on obtient l'identité de Vandermonde :
- et plus généralement
À partir du développement (8), en remplaçant m et r par n et en utilisant (4), on obtient
- .
En développant (x + y)2n(x – y)2n = (x2 – y2)2n et en observant le coefficient devant x2ny2n, on obtient
- .
On a
- ,
où 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).
Pour tous entiers naturels m, n et r ≥ m + n,
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[10]. Un cas particulier est (pour tous entiers r ≥ n ≥ 0)[11] :
- .
Notes et références
- ISO 80000-2:2009, Grandeurs et unités — Partie 2: Mathématiques, Première édition du 1er décembre 2009, chapitre 10 : Combinatoire
- Pour plus de détails, voir le .
- Y compris pour car . Cf. par exemple F. Benoist, B. Rivet, S. Maffre, L. Dorat et B. Touzillier, Mathématiques ECS 1re année, Dunod, (lire en ligne), p. 9.
- Voir par exemple .
- Voir par exemple Benoist et al. 2011, p. 9, ou le chapitre .
- (de) E. E. Kummer, « Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesentzen », J. Reine Angew. Math., vol. 44, , p. 93-146 (lire en ligne).
- (en) Donald E. Knuth, The Art of Computer Programming, vol. 1 : Fundamental Algorithms (lire en ligne), § 1.2.6, ex. 11.
- (en) John D. Cook, « Binomial coefficients ».
- René Adad, « Principales propriétés des coefficients binomiaux » (consulté le )
- Voir par exemple .
- Voir en:Hockey-stick identity.
Voir aussi
Articles connexes
Bibliographie
- (en) Henry W. Gould (en), Combinatorial Identities, A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, (lire en ligne)
- (en) Henry W. Gould, Tables of Combinatorial Identities, edited by J. Quaintance, 2010, vol. 1 à 8
- (en) John Riordan , Combinatorial Identities, R. E. Krieger, (1re éd. 1968, John Wiley & Sons)
Lien externe
Gérard Eguether, « Coefficients binomiaux »