Aller au contenu

Coefficient binomial

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Théorème de Kummer)

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, sont des entiers donnant le nombre de parties (ou sous-ensembles, non ordonnés) à k éléments d'un ensemble à n éléments. On les note[1] — qui se lit « k parmi n » — ou , la lettre C étant l'initiale du mot « combinaison ».

Les coefficients binomiaux sont donnés par :

,

ou, de manière équivalente, mais plus compacte, à l'aide de la fonction factorielle :

.

Ils interviennent dans de nombreux domaines des mathématiques : formule 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

[modifier | modifier le code]

Le coefficient binomial 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, se note :

Établissement de la formule

[modifier | modifier le code]

Le coefficient binomial est le nombre de parties à k éléments dans un ensemble à n éléments. Par 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}. Dans un jeu de cartes à 52 cartes, il y a mains possibles de 5 cartes (l'ordre des cartes dans une main ne compte pas).

On dit aussi que est le nombre de k-combinaisons dans un ensemble à n éléments. Il se détermine en calculant de deux façons différentes le nombre de façon de choisir éléments de cet ensemble dans un ordre donné, autrement dit de k-arrangements dans cet ensemble. Premièrement on a :

.

En effet, on choisit le premier élément parmi les éléments de l'ensemble, le deuxième élément parmi éléments (puisque l'on ne peut pas reprendre le premier élément), le troisième parmi , etc. Deuxièment, on a

.

En effet, on choisit une partie de k éléments, que l'on peut permuter de façons différentes pour obtenir un ordre donné. La confrontation des deux calculs donne l'expression algébrique de , pour k variant de 0 à n[5] :

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.

Définition récursive des coefficients binomiaux

[modifier | modifier le code]

La formule de Pascal lie les coefficients binomiaux : pour tout couple (n,k) d'entiers naturels[6],

On la démontre par un raisonnement combinatoire[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 : 21 35 35 21
8 : 28 56 70 56 28

Les coefficients pour 0 ≤ kn 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

[modifier | modifier le code]

Développement du binôme de Newton

[modifier | modifier le code]
Visualisation des coefficients binomiaux dans , , , .

Ces nombres sont les coefficients qui apparaissent en développant la puissance n-ième de x + y :

Par exemple, on a :

En regardant la cinquième ligne du triangle de Pascal, on obtient les valeurs des coefficients binomiaux. Ainsi :

.

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

[modifier | modifier le code]

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 :

Par exemple,

Combinatoire et statistique

[modifier | modifier le code]

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 à (nombre de n-compositions faibles de 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 k-combinaisons avec répétition de n objets).
  • Le nombre de suites de n entiers strictement positifs dont la somme vaut k est égale à (nombre de n-compositions de k).
  • En théorie des probabilités et en statistique, les coefficients binomiaux 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 :
    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 »).

Propriétés arithmétiques des coefficients binomiaux

[modifier | modifier le code]

Divisibilité

[modifier | modifier le code]
  • Un entier n ≥ 2 est premier si et seulement si tous les pour k = 1, … , n – 1 sont divisibles par n.

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 kpj soit plus grande que la partie fractionnaire de npj. 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, 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 2m – 1, tous ses chiffres binaires valent 1, et tous les seront impairs. Si n = 2m, alors n possède un seul 1 dans son développement binaire, et seuls et sont impairs, tous les autres sont pairs.

Une conséquence du théorème de Wilson est que n ≥ 2 est premier si et seulement si tous les sont congrus à modulo n (pour ) [11]. Par exemple, les nombres de la 6e ligne du triangle de Pascal ( 1, 6 ,15, 20, 15, 6, 1) deviennent, après correction par , (0,7,14,21,14,7,0), tous multiples de 7.

Coefficients binomiaux égaux à des puissances

[modifier | modifier le code]

On a , mais pour , Erdős a démontré en 1951 que le coefficient binomial n'est ni un carré, ni aucune puissance d'ordre supérieure [12].

Généralisations

[modifier | modifier le code]

Élargissement du domaine de définition

[modifier | modifier le code]

Jusqu'à présent le coefficient binomial était défini pour k et n entiers naturels avec kn. 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 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 satisfait la formule . 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 pour les factorielles descendantes, alors pour tout nombre réel ou complexe z et entier naturel k on peut définir le coefficient binomial par la formule :
    .
    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 pour k entier naturel et n entier relatif par la formule :
    qui ramène au cas initial lorsque n est négatif.
  • Il est possible de poser 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 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 kn on a :
    .
    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 :
    .
    Cette formule peut d'ailleurs s'écrire plus simplement à l'aide de la fonction bêta B :
    .
  • 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 :
    .
    Dans cette dernière formule, l'ordre des limites est important[13]. 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[14]
Généralisation Domaine de définition Définition Notations et remarques

désigne la fonction gamma.

Coefficients multinomiaux

[modifier | modifier le code]

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

Formules faisant intervenir les coefficients binomiaux

[modifier | modifier le code]

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

On rappelle que :

(formule de Pascal)
(formule du binôme de Newton)

Les formules suivantes peuvent être utiles :

et plus généralement (formule parfois dite « du pion »[15]).

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 (1 + x)n(1 + x)m = (1 + x)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 (1 + x)2n(1 – x)2n = (1 – x2)2n et en observant le coefficient devant x2n, on obtient

.

On a

,

Fn+1 désigne le (n+1)-ième terme de la suite de Fibonacci[16].

Pour tous entiers naturels m, n et rm + 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[17]. Un cas particulier est (pour tous entiers rn ≥ 0)[18] :

.

Encadrement et approximations

[modifier | modifier le code]

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

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 :

.

Mais pour être plus précis, il faut particulariser à différents régimes asymptotiques[19],[20]. Dans les cas ci-dessous, est la fonction entropie binaire (en).

  • cas 1 : si , et alors  ;
  • cas 2 : si et alors [19] ;
  • cas 3 : si et alors [20].

Notes et références

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Binomial coefficient » (voir la liste des auteurs).
  1. Les deux notations sont préconisées par la norme ISO/CEI 80000-2:2009 : 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). ISO 80000-2:2009, Grandeurs et unités — Partie 2: Mathématiques, Première édition du 1er décembre 2009, chapitre 10 : Combinatoire.
  2. « Coefficient binomial en Python ».
  3. (en) « binomial ».
  4. (en) « Binomial ».
  5. Pour plus de détails, voir le chapitre « Combinaisons sans répétition » sur Wikiversité.
  6. 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.
  7. Voir par exemple cet exercice corrigé de la leçon « Sommation » sur Wikiversité.
  8. Voir par exemple Benoist et al. 2011, p. 9, ou le chapitre « Formule du binôme » de la leçon « Sommation » sur Wikiversité.
  9. (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).
  10. (en) Donald E. Knuth, The Art of Computer Programming, vol. 1 : Fundamental Algorithms (lire en ligne), § 1.2.6, ex. 11.
  11. Vincent Beck, « Variations autour du théorème de Wilson », 2020-2021, corollaire 10.
  12. Martin Aigner, Günter M. Ziegler, Raisonnements divins, Springer, , p. 15-18
  13. (en) John D. Cook, « Binomial coefficients ».
  14. Ces définitions sont compatibles lorsque les domaines de définitions s'intersectent.
  15. René Adad, « Principales propriétés des coefficients binomiaux » (consulté le )
  16. Cf. Propriété 12 de la suite de Fibonacci.
  17. Voir par exemple cet exercice corrigé de la leçon sur les séries génératrices sur Wikiversité.
  18. Voir en:Hockey-stick identity.
  19. a b et c (en) Shagnik Das, « A brief note on estimates of binomial coefficients », Voir la formule 5. Et la formule 7, moins précise que la borne fournie dans wiki mais qui a le même comportement. Accès libre (consulté le ), p. 5
  20. a et b (en) Neven Elozovic (théorème 7.10 page 1024, prendre p=1, r=alpha et s=1-alpha), « Asymptotic expansions of gamma and related functions, binomial coefficients, inequalities and means » [« développement asymptotique de la fonction gamma et de fonctions associées, de coefficients binomiaux, d'inégalités et de moyennes »], Journal of Mathematical Inequalities, vol. 9, no 4,‎ , p. 1001-1054 (lire en ligne).

Articles connexes

[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie

[modifier | modifier le code]
  • (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

[modifier | modifier le code]

Gérard Eguether, « Coefficients binomiaux »