Coefficient binomial

En mathématiques, les cœfficients 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 qu'on peut former à partir d'un ensemble contenant n éléments.

Catégories :

Analyse combinatoire - Opération

Page(s) en rapport avec ce sujet :

1.1) Donner un algorithme pour calculer le développement d'un entier x en base q...... Conclusion : ce cœfficient binomial est -il divisible par p?.... Relier les cœfficients de la décomposition en éléments simples d'une fraction de ... (source : math.univ-lille1)
3.1 Cœfficients binomiaux. Voir la derni`ere section sur la..... que seuls les éléments au-dessus de la diagonale ont besoin d'être calculés.... positif) et un poids (un entier positif). L'objectif est de remplir le sac `a dos de façon ` a..... Le cœfficient binomial est défini comme suit, pour 0 ≤ k ≤ n :... (source : docs.happycoders)
les éléments d'un corps. La représentation d'un polynôme par un circuit peut être énormément plus compacte que la donnée de la liste des cœfficients de ses... (source : staff.umh.ac)

En mathématiques, (algèbre et dénombrement) les cœfficients 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 qu'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»). Cette quantité s'exprime avec la fonction factorielle :

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

Les cœfficients binomiaux interviennent dans de nombreux domaines des mathématiques : développement du binôme, dénombrement, développement en série, lois de probabilités.

On peut les généraliser, sous certaines conditions, aux nombres complexes.

É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 envisageables), puis le deuxième élément parmi n -1 (n -1 choix envisageables), etc. le dernier élément étant choisi parmi n - k+1 éléments. Il existe par conséquent $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 en premier lieu le sous-ensemble des k éléments parmi n ( ${n \choose k}$ choix envisageables) puis ordonner la totalité pour former une liste ( $k!$ ordres envisageables). Il existe par conséquent ${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 cœfficients binomiaux d'entiers

Le cœfficient 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 ! sert à désigner la factorielle de n. On remarque qu'il existe deux notations : le cœfficient 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 cœfficients 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 rapide des cœfficients 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 cœfficients ${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. Cette méthode permet le calcul rapide des cœfficients binomiaux sans division ni multiplication.

Note : pour $k \in [\![0;n]\!]$ , le cœfficient binomial est un nombre entier.

Démonstration

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 quand $\qquad n = m + 1$ :

pour $\qquad k = 1, \cdots , m$ , la formule de Pascal $\qquad \mbox{(2)}$ 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,

tandis que ${m+1 \choose 0}=1 \qquad$ et $\qquad {m+1 \choose m+1}=1 \qquad$ .

La propriété est par conséquent vraie pour $\qquad n = m + 1 \qquad$ , elle est donc vraie pour tout $\qquad n \qquad$ .

Utilisation des cœfficients binomiaux

Développement du binôme de Newton

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

Ces nombres sont les cœfficients 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)$

A titre d'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 cœfficients binomiaux sont importants en combinatoire, parce qu'ils fournissent des formules utilisées dans des problèmes habituels de dénombrement :

Le nombre de parties à k éléments dans un ensemble à n éléments est égal à ${n \choose k}$ . C'est aussi 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 nommé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 cœfficients 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 sert à 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 on prend simultanément deux cartes au hasard. Si 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 cœfficients 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$ , quand ces deux nombres sont écrits en base $p$ .

En particulier, ${n \choose k}$ est toujours divisible par $n/\mbox{pgcd}\,(n,k)$ (pgcd veut dire plus grand commun diviseur).

La règle sert à 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 par conséquent au moins une retenue en binaire. Cela veut dire que, dans le développement binaire de $n$ , il se trouve au moins un 0 localisé 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$ . A titre d'exemple, si $n$ est de la forme $2 p - 1$ , tous ses chiffres binaires valent 1, et l'ensemble des ${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, l'ensemble des 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 envisageable 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 on pose n=-m, on a la relation suivante :

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

C'est cette forme des cœfficients binomiaux qui est utilisée dans la formule du binôme négatif mais aussi dans la définition de la loi binomiale négative

Pour tout nombre complexe z et tout entier naturel k, on définit le cœfficient binomial ${z \choose k}$ de la manière suivante :

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

C'est cette forme des cœfficients 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 à cœfficients 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}$

Le calcul de ${n \choose k}$ peut se généraliser, avec la fonction Gamma. On remarque que, pour tout entier naturel n, $n! = Γ (n + 1)$ , ainsi, 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ˆ* - \mathbb Zˆ-$ , on peut généraliser le cœfficient 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)}$

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)}$

Mais il faut prendre garde à l'ordre des limites qui ne peuvent commuter^[1] et cette définition conduit à une valeur illimitée du cœfficient binomial dans les cas non étudiés auparavant

Formules faisant intervenir les cœfficients binomiaux

On suppose que k, n sont des entiers ; z, z'des complexes.

Les formules suivantes peuvent être utiles :

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

$<img class=$ .

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

$\sum_{k=0}ˆ{n} {n \choose k} = 2ˆn \qquad (6)$

En dérivant (3), et en remplaçant x = y = 1, 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 d'une façon plus générale $\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 cœfficient 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} = \mathcal{F}(n+1) \qquad (11)$

Ici, F (n+1) sert à désigner 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).

Voir aussi

Notes et références

↑ John D. Cook, Binomial cœfficients

Recherche sur Amazon (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Coefficient_binomial.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.