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 sous-ensembles différents à k éléments que l'on peut former à partir d'un ensemble contenant n éléments. On les note ${n \choose k}$ (lu « k parmi n » ) ou $C_n^k\,$ (lu « combinaison de k parmi n »), la première notation étant préconisée par la norme ISO 31-11. Cette quantité s'exprime à l'aide de la fonction factorielle :

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

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.

Sommaire

1 Établissement de la formule
2 Définition algébrique des coefficients binomiaux d'entiers
3 Utilisation des coefficients binomiaux
- 3.1 Développement du binôme de Newton
- 3.2 Combinatoire et statistique
4 Diviseurs et coefficients binomiaux
5 Généralisations
6 Formules faisant intervenir les coefficients binomiaux
7 Note et référence
8 Articles connexes

Établissement de la formule

L'expression de ${n \choose k}$ se détermine en utilisant les arrangements. On calcule le nombre d'arrangements ou de listes ordonnées à k éléments pris dans un ensemble en contenant n de deux façons différentes. La confrontation des deux calculs donne l'expression algébrique de ${n \choose k}$

Une liste ordonnée de k éléments pris parmi n peut être constituée en choisissant le premier élément parmi n, (n choix possibles), puis le deuxième élément parmi n − 1 (n − 1 choix possibles), etc, le dernier élément étant choisi parmi n − k + 1 éléments. Il existe donc $n(n-1)(n-2) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ listes ordonnées de k éléments pris parmi n.
Mais on peut aussi choisir d'abord le sous-ensemble des k éléments parmi n ( ${n \choose k}$ choix possibles) puis ordonner l'ensemble pour constituer une liste ( $k!$ ordres possibles). Il existe donc ${n \choose k} \times k!$ listes ordonnées de k éléments pris parmi n.

En confrontant ces deux expressions, on obtient l'expression de ${n \choose k}$ :

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

Définition algébrique des coefficients binomiaux d'entiers

Le coefficient binomial des entiers naturels n et k est noté ${n \choose k}$ ou $C_n^k$ et vaut :

$\frac{n (n -1)(n - 2)\cdots (n - k +1)}{k!} = \begin{cases}\displaystyle \frac{n!}{k!(n-k)!} & \mbox{si } k \in [\![0;n]\!] \quad\mbox{(1)} \\\qquad 0 & \mbox{sinon}\end{cases}$

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{(2)}$

Elle donne lieu au triangle de Pascal qui permet un calcul 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 ${n \choose k}, k \in [\![0;n]\!]$ figurent à la n^e 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.

Utilisation des coefficients binomiaux

Développement du binôme de Newton

Article détaillé : Formule du binôme de Newton.

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

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

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\,$ .

Combinatoire et statistique

Article détaillé : Loi binomiale.

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 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 à ${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 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 »).

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{k}{p^j}\,$ soit plus grande que la partie fractionnaire de $\frac{n}{p^j}\,$ . C'est le nombre de retenues dans la soustraction de $n$ par $k$ , lorsque ces deux nombres sont écrits en base $p$ ^[1].

En particulier, ${n \choose k}$ est toujours divisible par $\frac{n}{\mbox{PGCD}\,(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$ .

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

Généralisations

L'écriture de ${n \choose k}$ , pour tout entier n et tout entier k compris entre 1 et n, sous la forme

${n \choose k} = \frac{\prod_{i=0}^{k-1}(n-i)}{k!}$

permet d'envisager une extension possible aussi pour tout entier n négatif et tout entier k strictement positif en utilisant l'expression suivante :

${n \choose k} = \frac{\prod_{i=0}^{k-1}(n-i)}{k!}$

Si l'on pose n = −m, on a la relation suivante :

${-m \choose k} ={m+k-1\choose k}(-1)^k$

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 ${z \choose k}$ de la manière suivante :

${z \choose k} = \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!}=\frac{(z)_k}{k!}$

où $(\cdot)_k$ est le symbole de Pochhammer pour les factorielles descendantes (en particulier, ${z\choose 0}=\frac{(z)_0}{0!}=\frac11=1$ ).

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 ${z \choose k}$ 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 $p(z) = \sum_{k=0}^{d} a_k {z \choose k}$ ; 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 ${n \choose k}$ 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,

${n \choose k} = \frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(n-k+1)}$

Comme la fonction $Γ$ est définie pour tout complexe de $\C \backslash \mathbb Z_-$ , 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 :

${s \choose t} = \frac{\Gamma(s+1)}{\Gamma(t+1)\Gamma(s-t+1)}$ ;

Cette formule peut d'ailleurs s'écrire plus simplement à l'aide de la fonction bêta :

${s \choose t} = \frac{1}{(s+1)\Beta(t+1,s-t+1)}$ ;

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 :

${s \choose t} =\lim_{u\to s}\lim_{v \to t} \frac{\Gamma(u+1)}{\Gamma(v+1)\Gamma(u-v+1)}$

L'ordre des limites est important^[2]. 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 ; z, z′ des complexes.

On rappelle que :

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

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

Les formules suivantes peuvent être utiles :

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

${n \choose k} = \frac{n}{k}{n-1 \choose k-1} \qquad(k>0)$ et plus généralement ${z \choose k} = \frac{z}{k}{z-1 \choose k-1}\qquad (5)$ .

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

$\sum_{k=0}^{n} {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 $\sum_{k=0}^{n} (-1)^k{n \choose k} = 0$ ; avec x = 1 et y = i (donc y² = −1), on obtient $\sum_{k=0}^{n} (-1)^k{n \choose 2k} = \operatorname{Re}((1+i)^n)=2^{n/2}\cos (n\pi/4)$ .

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

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

En développant ( $x + y)^n(x + y)^m = (x + y)^{m +n}\,$ avec (3), on obtient l'identité de Vandermonde :

$\sum_{j=0}^{k} {m \choose j} {n \choose k-j} = {m+n \choose k}$ et plus généralement $\sum_{j=0}^{k} {z \choose j} {z' \choose k-j} = {z+z' \choose k} \qquad (8)$

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

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

En développant $(x+y)^{2n}(x-y)^{2n}=(x^2-y^2)^{2n}\,$ et en observant le coefficient devant $x^{2n}y^{2n}\,$ , on obtient

$\sum_{k=0}^{2n} (-1)^k{2n \choose k}^2 = (-1)^n {2n \choose n} \qquad (10)$

On a,

$\sum_{k=0}^{n} {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. 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=k}^{n} {j \choose k} = {n+1 \choose k+1} \qquad (12)$

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

Note et référence

↑ Théorème de Kummer (1852). cf Knuth, The art of computer programming, Vol.1 (Fundamental algorithms), Addison-Wesley, 2ème édition, p.68
↑ John D. Cook, Binomial coefficients

Articles connexes

v · d · m

Opérations binaires

Numériques	En ensemble ordonné	Structurelles	Autres

Élémentaires $+$ Addition $-$ Soustraction $\times$ Multiplication $\div$ Division $\hat{}$ Puissance Arithmétiques $div$ Quotient euclidien $mod$ Reste euclidien $pgcd$ PGCD $ppcm$ PPCM Combinatoires $()$ Coefficient binomial $A$ Arrangement	Ensembles de parties $\cup$ Union $\backslash$ Complémentation $\cap$ Intersection $Δ$ Différence symétrique Ordre total $min$ Minimum $max$ Maximum Treillis $\wedge$ Borne inférieure $\vee$ Borne supérieure	Ensembles $\times$ Produit cartésien $\dot{\cup}$ Somme disjointe $\hat{}$ Puissance ensembliste Groupes $\oplus$ Somme directe $\ast$ Produit libre $\wr$ Produit en couronne Modules $\otimes$ Produit tensoriel $Hom$ Homomorphisme $Tor$ Torsion $Ext$ Extension Arbres $\vee$ Enracinement Variétés connexes $\#$ Somme connexe Espaces pointés $\vee$ Bouquet $\wedge$ Smash produit $\ast$ Joint	Fonctionnelles $\circ$ Composition de fonctions $\ast$ Produit de convolution Vectorielles $\cdot$ Produit scalaire $\wedge$ Produit vectoriel $\times\,$ Produit vectoriel généralisé Algébriques $[,]$ Crochet de Lie ${,}$ Crochet de Poisson $\wedge$ Produit extérieur Homologiques $\smile$ Cup produit $\cdot$ Produit d'intersection Séquentielles $+$ Concaténation

Logique booléenne : $\land$ ET (conjonction) • $\lor$ OU (disjonction) • $\oplus$ OU exclusif • $\Rightarrow$ IMP (implication) • $\Leftrightarrow$ EQV (équivalence)

Portail des mathématiques

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Coefficient binomial de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Coefficient Binomial — En mathématiques, (algèbre et dénombrement) les coefficients binomiaux , définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de sous ensembles différents à k éléments que l on peut former à partir… … Wikipédia en Français
Coefficient binômial — Coefficient binomial En mathématiques, (algèbre et dénombrement) les coefficients binomiaux , définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de sous ensembles différents à k éléments que l on… … Wikipédia en Français
Coefficient binomial — ● Coefficient binomial chacun des entiers naturels (0≤p≤n) qui interviennent dans la formule du binôme donnant (x + y)n. ( ) … Encyclopédie Universelle
binomial — binomial, iale, iaux [ binɔmjal, jo ] adj. • mil. XVe; de binôme ♦ Math. Relatif au binôme. Coefficient binomial : coefficient de la formule du binôme de Newton. Loi binomiale : loi de statistique d un phénomène à deux événements complémentaires… … Encyclopédie Universelle
Binomial coefficient — The binomial coefficients can be arranged to form Pascal s triangle. In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the… … Wikipedia
Binomial — In elementary algebra, a binomial is a polynomial with two terms: the sum of two monomials. It is the simplest kind of polynomial except for a monomial.The binomial a^2 b^2 can be factored as the product of two other binomials:: a^2 b^2 = (a +… … Wikipedia
Coefficient — Sur les autres projets Wikimedia : « Coefficient », sur le Wiktionnaire (dictionnaire universel) En mathématiques un coefficient est un facteur multiplicatif qui dépend d un certain objet, comme une variable (par exemple, les… … Wikipédia en Français
Binomial — Binôme Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
binomial coefficient — n. Math. 1. the coefficient of any term in the expansion of (x + a) n 2. the number of combinations of a specified size that can be drawn from a given set … English World dictionary
Binomial theorem — The binomial coefficients appear as the entries of Pascal s triangle. In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power… … Wikipedia

Dictionnaires et Encyclopédies sur 'Academic'

Coefficient binomial

Sommaire

Établissement de la formule

Définition algébrique des coefficients binomiaux d'entiers