Vérifié contenu

Coefficient binomial

Sujets connexes: Mathématiques

Saviez-vous ...

Cette sélection se fait pour les écoles par la charité pour enfants lire la suite . enfants SOS est le plus grand organisme de bienfaisance du monde en donnant des enfants orphelins et abandonnés la chance de la vie familiale.

En mathématiques , en particulier dans la combinatoire , un coefficient binomial est un coefficient de l'un des termes de l'expansion de la binomiale (x + y) n. Familièrement donné, dire il ya n garnitures à pizza à choisir, si l'on veut faire cuire une pizza avec exactement k différentes garnitures, le coefficient binomial exprime la façon dont de nombreux types de telles k pizzas -topping sont possibles.

Définition

Étant donné un entier non négatif et n un nombre entier k, le coefficient binomial est défini comme étant le nombre naturel

{N \ choisir k} = \ frac {n \ cdot (n-1) \ cdots (n-k + 1)} {k \ cdot (k-1) \ cdots 1} = \ frac {n!} {K ! (nk)!} \ quad \ mbox {if} \ n \ geq k \ geq 0 \ qquad (1)

et

{N \ choisir k = 0} \ quad \ mbox {if} k <0 \ mbox {} ou k> n

n! désigne la factorielle de n.

Selon Nicholas J. Higham, le {N \ choose k} la notation a été introduit par Albert von Ettinghausen en 1826 , bien que ces chiffres étaient déjà connus des siècles avant que (voir le triangle de Pascal ). Alternatifs incluent notations C (n, k), k n C ou C ^ {k} _ {n} , Dans lequel l'ensemble de C signifie combinaison ou choisir. En effet, un autre nom pour le coefficient binomial est de choisir la fonction, et le coefficient binomial de n et k est souvent lu comme «n choisir k".

Les coefficients binomiaux sont le coefficients dans l'expansion de la distribution binomiale (x + y) n (où son nom):

(X + y) ^ n = \ sum_ {k = 0} ^ {n} {n \ choisir k} ^ {x} nk y ^ k. \ Qquad (2)

Ce est généralisée par la théorème binomial, ce qui permet à l'exposant n est négatif ou un non entier. Voir l'article sur combinaison.

Interprétation combinatoire

L'importance des coefficients binomiaux (et la motivation pour l'autre nom «choisir») réside dans le fait que {\ Tbinom n k} est le nombre de façons que k objets peuvent être choisis parmi n objets, indépendamment de l'ordre. Plus formellement,

{\ Tbinom n k} est le nombre de sous-ensembles de k -Element d'un ensemble de n -Element. \ Qquad (1a)

En fait, cette propriété est souvent choisi comme une autre définition du coefficient binomial, depuis de (1a), on peut déduire (1) comme corollaire par un simple preuve combinatoire. Pour une démonstration familier, noter que dans la formule

{N \ choisir k} = \ frac {n \ cdot (n-1) \ cdots (n-k + 1)} {k \ cdot (k-1) \ cdots 1},

le numérateur donne le nombre de moyens de combler les fentes k en utilisant les options de N, où les fentes se distinguent les uns des autres. Ainsi une pizza aux champignons ajoutés avant le poulet est considérée comme différente d'une pizza avec du poulet ajouté avant champignons. Le dénominateur élimine ces répétitions parce que si les fentes de k sont indiscernables, alors tous les k! les moyens de les organiser sont considérés comme identiques.

Sur le contexte de l'informatique, il contribue également à voir {\ Tbinom n k} que le nombre de chaînes composées de uns et de zéros avec ceux de k et n - k zéros. Pour chaque sous-ensemble k de -Element, K, d'un ensemble de n -Element, N, la fonction d'indicateur, une K: N -> {0,1}, où 1 K (x) = 1 quand x K et 0 sinon, produit une chaîne binaire unique de longueur n avec exactement k ceux en alimentant K 1 au n éléments dans un ordre spécifique.

Exemple

{7 \ choose 3} = \ frac {7!} {3! (7-3)!} = \ Frac {7 \ cdot 6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {(3 \ cdot 2 \ cdot 1) (4 \ cdot 3 \ cdot 2 \ cdot 1)} = \ frac {7 \ cdot 6 \ cdot 5} {3 \ cdot 2 \ cdot 1} = 35.

Le calcul du coefficient binomial est idéalement agencé comme ceci: ((((5/1) · 6) / 2) · 7) / 3, en alternance divisant et en multipliant des entiers croissants. Chaque division produit un résultat de nombre entier qui est lui-même un coefficient binomial.

Dérivation de l'expansion binomiale

Pour exposant 1, (x + y) est 1 x + y. Pour exposant 2, (x + y) est 2 (x + y) (x + y), qui forme le plan de la façon suivante. Les premières livraisons de facteurs soit un X ou un Y; de même pour le deuxième facteur. Ainsi pour former x 2, la seule possibilité est de choisir x de deux facteurs; de même pour y 2. Toutefois, le terme xy peut être formé par x de la première et y à partir du deuxième facteur, ou y de la première et de la seconde x facteur; ainsi il acquiert un coefficient de 2. Instance visant à exponent 3, (x + y) se réduit à 3 (x + y) 2 (x + y), où nous savons déjà que (x + y) = 2 x 2 2 xy + y 2, ce qui donne une expansion initiale de (x + y) (x 2 + y 2 xy 2). Encore une fois les extrêmes, X 3 et Y 3 se présentent d'une manière unique. Toutefois, le terme de y x 2 est soit 2 fois x xy ou x 2 y fois, par un coefficient de 3; même xy 2 se pose de deux façons, en additionnant les coefficients 1 et 2 pour donner trois.

Ceci suggère un induction. Ainsi, pour l'exposant n, chaque terme a degré total (somme des exposants) n, avec n - k facteurs de x et de y k facteurs. Si k est 0 ou n, le terme se pose que dans un sens, et nous obtenons les termes x n et y n. Si k est ni 0 ni n, alors le terme découle de deux manières, à partir de x nk-1 y k × x et y à partir de x nk k-1 × y. Par exemple, x 2 y 2 est à la fois xy 2 fois x et y x 2 y fois, d'où son coefficient est égal à 3 (le coefficient de xy 2) + 3 (le coefficient de x 2 y). Ce est l'origine du triangle de Pascal, discuté ci-dessous.

Un autre point de vue, ce est que pour former x n - k y k de n facteurs de (x + y), nous devons y choisir parmi des facteurs k et x du reste. Pour compter les possibilités, tenir compte de tous n! permutations des facteurs. Représenter chaque permutation comme une liste mélangées des numéros de 1 à n. Sélectionner un X à partir de la première n - k facteurs énumérés, et un des facteurs y k restantes; de cette manière chaque permutation contribue à l'expression x n - k y k. Par exemple, la liste <4,1, 2,3> x sélectionne des facteurs 4 et 1, et y sélectionne des facteurs 2 et 3, comme un moyen pour former le terme x 2 y 2.

(X + y 1) (x 2 + y) (x + y 3) (x + y 4)

Mais la liste distincte <1,4, 3,2> fait exactement la même sélection; la formule de coefficient binomial doit retirer cette redondance. Le n - k facteurs pour avoir x (n - k)! permutations, et les facteurs de k pour y ont k! permutations. Par conséquent n /! (N - k) k! est le nombre de façons distinctes réellement pour former le terme x n - k y k.

Une explication simple suit: On peut choisir un élément aléatoire sur n exactement n façons, un deuxième élément aléatoire dans (N-1) des moyens, et ainsi de suite. Ainsi, k éléments peuvent être récupérés sur n dans n \ cdot (n-1) \ cdot \ ldots \ cdot (n-k + 1) façons. Dans ce calcul, cependant, chaque sélection de commande indépendant se produit k! fois, comme une liste de k éléments peuvent être permutées à bien des égards. Ainsi éq. (1) est obtenue.

Le triangle de Pascal

La règle de Pascal est l'importante relation de récurrence

{N \ choisir k} + {n \ choisir k + 1} = {n + 1 \ choisir k + 1}, \ qquad (3)

qui découle directement de la définition:

\ Begin {align} {n \ choisir k} + {n \ choisir k + 1} & {} = \ frac {n!} {K! (Nk)!} + \ Frac {n!} {(K + 1 )! (n (k + 1))!} {} \\ & = \ left (\ frac {n! (k + 1)} {k! (nk)! (k + 1)} + \ frac { n! (nk)} {(k + 1)! (n (k + 1))! (nk)} \ right) \\ & {} = \ left (\ frac {n! (k + 1 + nk )} {(k + 1) (nk)} \ right) \\ & {} = \ frac {(n + 1)} {(k + 1) ((n + 1) -!!!! (k + 1))!} {} \\ & = {n + 1 \ choisir k + 1} \ end {align}

La relation de récurrence vient de prouver peut être utilisé pour prouver par induction mathématique C (n, k) est un nombre naturel pour tout n et k, ce qui ne est pas immédiatement évident à partir de la définition.

La règle de Pascal donne également lieu à triangle de Pascal :

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

numéro de rang n contient les numéros C (n, k) pour k = 0, ..., n. Il est construit en commençant par ceux à l'extérieur, puis en ajoutant toujours deux numéros adjacents et écrit la somme directement sous. Cette méthode permet le calcul rapide des coefficients binomiaux sans la nécessité pour les fractions ou multiplications. Par exemple, en regardant le numéro de la ligne 5 du triangle, on peut lire rapidement éteint que

(X + y) = 1 5 x 5 x 5 + y + 4 10 x 3 y 2 + 10 x 2 y 3 + y 4 x 5 + 1 O 5.

Les différences entre les éléments sur les autres diagonales sont les éléments de la diagonale précédent, par suite de la relation de récurrence (3) ci-dessus.

Dans le traité de 1303 AD Miroir précieux des quatre éléments, Zhu Shijie mentionné le triangle comme une ancienne méthode pour évaluer coefficients binomiaux indiquant que la méthode était connue Mathématiciens chinois cinq siècles avant Pascal .

Combinatoire et statistiques

Les coefficients binomiaux sont importants en combinatoire , car ils fournissent des formules prêtes pour certains problèmes de comptage fréquentes:

  • Chaque sertie de n éléments a \ Mathrm {C} (n, k) différents sous-ensembles comportant des éléments de k chacun (ceux-ci sont appelés k -ensembles).
  • Le nombre de chaînes de longueur n contenant les k et n - k zéros est \ Mathrm {C} (n, k).
  • Il y a \ Mathrm {C} (n + 1, k) des chaînes composées de n zéros et ceux tels que deux celles-ci sont contiguës k.
  • Le nombre de séquences constitué de n nombres naturels dont la somme est égale à k est \ Mathrm {C} (n + k-1, k) ; ce est aussi le nombre de façons de choisir k éléments d'un ensemble de n si les répétitions sont autorisés.
  • Le Nombres de Catalan ont une formule facile impliquant coefficients du binôme; ils peuvent être utilisés pour compter les diverses structures, tels que arbres et expressions entre parenthèses.

Les coefficients binomiaux se produisent également dans la formule de la loi binomiale dans les statistiques et dans la formule pour une courbe de Bézier.

Formules impliquant coefficients binomiaux

Il faut que

{N \ choisir k} = {n \ n choisissez-k}, \ qquad \ qquad (4)

Cela résulte aussitôt de la définition ou peut être vu de l'expansion (2) en utilisant (x + y) n = (y + x) n, et se reflète dans la «symétrie» numérique de triangle de Pascal .

Une autre formule est

\ Sum_ {k = 0} ^ {n} {n \ choisir k} = 2 ^ n, \ qquad \ qquad (5)

il est obtenu à partir de l'expansion (2) avec x = y = 1. Ceci est équivalent à dire que les éléments d'une rangée du triangle de Pascal ajoutent toujours à deux élevé à une puissance entière. Une preuve combinatoire de ce fait est donnée par le comptage des sous-ensembles de taille 0, taille 1, taille 2, et ainsi de suite jusqu'à la taille n de S un ensemble de n éléments. Étant donné que l'on compte le nombre de sous-ensembles de taille i pour 0 ≤ in, cette somme doit être égal au nombre de sous-ensembles de S, qui est connu pour être de 2 n.

La formule

\ Sum_ {k = 1} ^ {n} {k} {n \ choisir k} = {n} {2 ^ n-1} \ qquad (6)

résulte de l'expansion (2), après différenciation par rapport à X ou Y, puis en remplaçant x = y = 1.

Identité de Vandermonde

\ Sum_ {j} {m \ choisir j} {{nm} \ {choisir kj}} = {n \ choisir k} \ qquad (7a)

se trouve en écartement (1+ x) m (1+ x) nm = (x 1+) n avec (2). Comme C (n, k) est égal à zéro si k> n, la somme est finie pour n et m entier. L'équation (7a) généralise l'équation (3). Il tient pour arbitraire, évalués complexe m et n , Le Chu-Vandermonde identité.

Une formule est lié à

\ Sum_ {m} {m \ choisir j} {nm \ choisir kj} = {n + 1 \ choose k + 1}. \ Qquad (7b)

Alors que l'équation (7a) est vraie pour toutes les valeurs de m, l'équation (7b) est vraie pour toutes les valeurs de j.

De expansion (7a) en utilisant n = 2 m, k = m, et (4), on trouve

\ Sum_ {j = 0} ^ {m} {m \ choisir j} ^ 2 = {{2m} \ choisissez m}. \ Qquad (8)

Notons F (n + 1) les numéros de Fibonacci . On obtient une formule sur les diagonales du triangle de Pascal

\ Sum_ {k = 0} ^ {n} {{nk} \ choisir k} = \ mathrm {F} (n + 1). \ Qquad (9)

Ceci peut être prouvé par utilisant induction (3).

Aussi l'aide (3) et l'induction, on peut montrer que

\ Sum_ {j = k} ^ {n} {j \ choisir k} = {{n + 1} \ choisissez {k + 1}}. \ Qquad (10)

Encore une fois par (3) et de l'induction, on peut montrer que pour k = 0, ..., n - 1

\ Sum_ {j = 0} ^ {k} (-1) ^ j {n \ choisir j} = (-1) ^ k {{n-1} \ choisir k} \ qquad (11)

aussi bien que

\ Sum_ {j = 0} ^ {n} (-1) ^ j {n \ choisir j} = 0 \ qquad (12)

qui est lui-même un cas particulier de telle sorte que pour tout entier a = 1, ..., n - 1,

\ Sum_ {j = 0} ^ {n} (-1) ^ j {n \ choisir j} j ^ a = 0.

qui peut être montré en différenciant (2) une fois et le réglage x = -1 et y = 1.

Identités combinatoires impliquant coefficients binomiaux

Nous présentons quelques identités qui ont des preuves combinatoires. Nous avons, par exemple,

\ Sum_ {k = q} ^ {n} {n \ choisir k} {k \ choisissez q} = 2 ^ {} {nq n \ choisissez q}. \ Qquad (13)

pour {N} \ geq {q}. La preuve combinatoire va comme suit: le côté gauche compte le nombre de façons de choisir un sous-ensemble [N] d'au moins q éléments, et q éléments de marquage parmi ceux sélectionnés. Le côté droit compte le même paramètre, car il ya \ Mathrm {C} (n, q) des moyens de choix d'un ensemble de marques q et ils se produire dans tous les sous-ensembles qui contiennent en outre un sous-ensemble des éléments restants, dont il existe 2 ^ {n-q}. Cela réduit à (6) lorsque q = 1.

L'identité (8) présente également une preuve combinatoire. L'identité lit

\ Sum_ {k = 0} ^ n {n \ choisir k} ^ 2 = {2n \ n} choisir.

Supposons que vous avez 2n carrés vides disposés dans une rangée et vous souhaitez marquer (sélection) n d'entre eux. Il y a C (2n, n) façons de le faire. D'autre part, vous pouvez choisir vos places en sélectionnant n k places parmi le premier n et n-k carrés des autres n carrés. Cela donne

\ Sum_ {k = 0} ^ {n} {n \ choisir k} {n \ choisir nk} = {{2n} \ n} choisir.

Maintenant appliquer (4) pour obtenir le résultat.

Fonctions génératrices

Si nous ne savons pas à propos de coefficients binomiaux nous pourrions les obtenir en utilisant le cas marqué de la Théorème fondamental de l'énumération combinatoire. Cela se fait en définissant C (n, k) être le nombre de façons de partitionnement [N] en deux sous-ensembles, dont le premier a une taille k. Ces partitions forment une classe combinatoire avec la spécification

\ Mathfrak {S} _2 (\ mathfrak {P} (\ mathcal {Z})) = \ mathfrak {P} (\ mathcal {Z}) \ mathfrak {P} (\ mathcal {Z}).

D'où l'exponentielle générer la fonction B de la fonction de somme des coefficients binomiaux est donnée par

B (z) = \ exp {z} \ exp {z} = \ exp (2z) \ ,.

On obtient immédiatement

\ Sum_ {k = 0} ^ {n} {n \} choisir k = n! [Z ^ n] \ exp (2z) = 2 ^ n,

comme prévu. Nous célébrons le premier sous-ensemble avec \ Mathcal {U} afin d'obtenir les coefficients binomiaux eux-mêmes, ce qui donne

\ Mathfrak {P} (\ mathcal {U} \; \ mathcal {Z}) \ mathfrak {P} (\ mathcal {Z}).

On obtient ainsi la fonction génératrice bidimensionnelle

B (z, u) = \ exp uz \ exp z \ ,.

Extraire des coefficients, nous constatons que

{N \ choose k} = n! [U ^ k] [z ^ n] \ exp uz \ exp z = n! [Z ^ n] \ frac {z ^ k} {k!} \ Exp z

ou

\ Frac {n!} {K!} [Z ^ {n-k}] \ exp z = \ frac {n!} {K! \, (N-k)!},

nouveau comme prévu. Cette dérivation est inclus ici parce qu'il suit de près celle de la Stirling nombres du premier et du deuxième type, et par conséquent tend à confirmer la notation binomial de style qui est utilisé pour ces numéros.

Diviseurs de coefficients binomiaux

Les premiers diviseurs de C (n, k) peuvent être interprétés comme suit: si p est un nombre premier p et r est la plus grande puissance de p qui divise C (n, k), alors r est égal au nombre de nombres naturels j tels que la partie fractionnaire de k / p j est plus grand que la partie fractionnaire de n / p j. En particulier, C (n, k) est toujours divisible par n / pgcd (n, k).

Un résultat quelque peu surprenant par David Singmaster (1974) est que toute les divisions entières presque tous les coefficients du binôme. Plus précisément, fixer un nombre entier d et f (N) le nombre de coefficients binomiaux C (n, k) avec n <N tel que d divise C (n, k). Puis

\ Lim_ {N \ to \ infty} \ frac {f (N)} {N (N + 1) / 2 = 1}.

Comme le nombre de coefficients binomiaux C (n, k) avec n <N est N (N + 1) / 2, cela signifie que la densité des coefficients binomiaux divisible par d passe à 1.

Bounds pour coefficients binomiaux

Les limites suivantes pour C (n, k) sont satisfaites:

  • {N \ choisir k} \ le \ frac {n ^ k} {k!}
  • {N \ choisir k} \ le \ left (\ frac {n \ cdot e} {k} \ right) ^ k
  • {N \ choisir k} \ ge \ left (\ frac {n} {k} \ right) ^ k

Généralisations

Généralisation aux multinomials

Les coefficients binomiaux peuvent être généralisés à coefficients multinomiaux. Ils sont définis comme le nombre:

{N \ choisir k_1, k_2, \ ldots, k_r} = \ frac {n!} {K_1! K_2! \ Cdots k_r!}

\ Sum_ {i = 1} ^ n = rk_i

Bien que les coefficients binomiaux représentent les coefficients de (x + y) n, les coefficients multinomiaux représentent les coefficients du polynôme

(X + 1 x 2 + ... + x r) n.

Voir théorème multinomial. Le cas k = 2 donne coefficients du binôme:

{N \ choisir k_1, k_2} = {n \ choisir k_1, n-k_1} = {n \ choisir k_1} = {n \ choisir k_2}

L'interprétation combinatoire des coefficients multinomiaux est la distribution de n éléments distincts sur R conteneurs (distinctes), chacun contenant exactement k éléments i,i est l'indice du récipient.

Coefficients multinomiaux ont de nombreuses propriétés analogues à celle de coefficients du binôme, par exemple la relation de récurrence:

{N \ choisir k_1, k_2, \ ldots, k_r} = {n-1 \ choisir k_1-1, k_2, \ ldots, k_r} + {n-1 \ choisir k_1, k_2-1, \ ldots, k_r} + \ ldots + {n-1 \ choose k_1, k_2, \ ldots, k_r-1}

et la symétrie:

{N \ choisir k_1, k_2, \ ldots, k_r} = {n \ choisir k _ {\ sigma_1}, k _ {\ sigma_2}, \ ldots, k _ {\ sigma_r}}

(\ Sigma_i) est une permutation de (1,2, ..., r).

Généralisation aux entiers négatifs

Si k \ geq 0 , Puis {N \ choisir k} = \ frac {n (n-1) \ dots (n-k + 1)} {1. 2 \ dots} k = (-1) ^ k {-n + k-1 \ choisir k} se étend à toutes n .

Le coefficient binomial étend à k \ leq 0 via

{N \ choisir k} = \ begin {} cas (-1) ^ {nk} {k-1 \ choisir nk} \ quad \ mbox {if} n \ geq k, \\ (-1) ^ {nk } {k-1 \ choose -n-1} \ quad \ mbox {if} n \ leq -1. \ end {} cas

Remarquez en particulier que

{N \ choisir k = 0} \ quad \ mbox {} ssi \ begin {} n cas geq 0 \ mbox {et} \ n <k, \\ n \ geq 0 \ mbox {et} k <0, \\ n <0 \ mbox {et} n <k <0. \ end {} cas


Cela donne lieu à l'Hexagone ou Pascal Pascal Moulin.

  • Hilton, Holton et Pedersen (1997). Réflexions mathématiques. Springer. ISBN 0-387-94770-1.

Généralisation à l'argument réelle et complexe

Le coefficient binomial {Z \ choisir k} peut être définie pour tout nombre complexe z et tout nombre naturel k comme suit:

{Z \ choisir k} = \ {prod_ n = 1} ^ {k} {z k + n \ n} = plus de \ frac {z (z-1) (z-2) \ cdots (z k + 1)} {k!}. \ Qquad (14)

Cette généralisation est connu que le coefficient binomial généralisé et est utilisé dans la formulation de la binôme et satisfait les propriétés (3) et (7).

Pour k fixe, l'expression f (z) = {z \ choisir k} est un polynôme en z de degré k avec rationnels coefficients.

f (z) est l'unique polynôme de degré k satisfaisant

f (0) = f (1) = ... = f (k - 1) = 0 et f (k) = 1.

Tout polynôme p (z) de degré d peut être écrit sous la forme

p (z) = \ sum_ {k = 0} ^ {d} {a_k z \ choisir k}.

Ceci est important dans la théorie de équations de différence et différences finies, et peuvent être considérés comme un analogue discret de Théorème de Taylor . Il est étroitement apparenté à Le polynôme de Newton. Sommes alternées de ce formulaire peuvent être exprimés en Méthode de Rice.

En particulier, on peut exprimer le produit de coefficients binomiaux comme une telle combinaison linéaire:

{X \ choisissez m} {x \ n choisir} = \ sum_ {k = 0} ^ m {m + nk \ choisir k, mk, nk} {x \ choisir m + nk}

où les coefficients de connexion sont coefficients multinomiaux. En termes d'objets combinatoires marquées, les coefficients de connexion représentent le nombre de façons d'attribuer m + nk étiquettes à une paire d'objets combinatoires étiquetés de poids m et n respectivement, qui ont eu leurs étiquettes premier k identifiés ou collées ensemble, afin pour obtenir un nouvel objet combinatoire marqué de poids + m nk. (Ce est, pour séparer les étiquettes en 3 parties à appliquer à la partie collée, la partie décollée du premier objet, et la partie décollée du second objet.) À cet égard, coefficients binomiaux sont exponentiel générer des séries ce relevant factorielles sont à la série de production ordinaire.

Série du binôme de Newton

Newton série du binôme, nommé d'après Sir Isaac Newton , est l'un des plus simples Newton série:

(1 + z) ^ {\ alpha} = \ sum_ {n = 0} ^ {\ infty} {\ alpha \ choisir n} z ^ n = 1 + {\ alpha \ choose1} z + {\ alpha \ choisir 2} z ^ 2 + \ cdots.

L'identité peut être obtenue en montrant que les deux parties satisfont l'équation différentielle (1 + z) f '(z) = α f (z).

Le rayon de convergence de cette série est égal à 1. Une expression alternative est

\ Frac {1} {(1-z) ^ {\ alpha + 1}} = \ sum_ {n = 0} ^ {\ infty} {n + \ alpha \ n} choisir z ^ n

lorsque l'identité

{N \ choisir k} = (-1) ^ k {k-n-1 \ choisir k}

est appliqué.

La formule pour la série binomiale a été gravé sur la pierre tombale de Newton dans l'abbaye de Westminster en 1727.

Généralisation à Q -série

Le coefficient binomial a un généralisation q analogique connue sous le nom Binomial gaussien.

Généralisation aux cardinaux infinis

La définition du coefficient binomial peut être généralisée à cardinaux infinis en définissant:

{\ Alpha \ choisir \ beta} = | \ {B \ subseteq A: | B | = \ beta \} |

où A est un ensemble avec cardinalité \ Alpha . On peut montrer que le coefficient binomial généralisé est bien défini, en ce sens que ne importe quel ensemble nous avons choisi pour représenter le nombre cardinal \ Alpha , {\ Alpha \ choisir \ beta} restera le même. Pour cardinaux finis, cette définition coïncide avec la définition standard du coefficient binomial.

En supposant que le Axiom of Choice, on peut montrer que {\ Alpha \ choisir \ alpha} = 2 ^ {\ alpha} pour tout cardinal infini \ Alpha .

Coefficient binomial des langages de programmation

La notation {N \ choose k} est pratique à la main, mais gênant pour machines à écrire et terminaux informatiques. De nombreux langages de programmation ne offrent pas une norme sous-programme de calcul du coefficient binomial, mais par exemple le Langage de programmation J utilise le point d'exclamation: k! n.

Implémentations naïfs, comme l'extrait suivant dans C :

 int choisir (int n, int k) {
     retourner factorielle (n) / (factorielle (k) * factorielle (n - k));
 } 

sont sujettes à déborder erreurs, restreindre sévèrement la gamme de valeurs d'entrée. Une mise en œuvre directe de la première définition fonctionne bien:

 unsigned long choisissez longue (n non signé, non signé k) {
     if (k> n)
         return 0;

     if (k> n / 2)
         k = nk;  // Plus vite

     long double accum = 1;
     (i unsigned = 0; i ++ <k;)
          accum = accum * (n-k + i) / i;

     retour accum + 0,5;  // Éviter l'erreur d'arrondi
 }

Utilisation La règle de Pascal {N \ choisir k} = {n-1 \ choisir k-1} + {n-1 \ choisir k} L'algorithme pour le coefficient binomial peut être rédigé en forme récursive:

     choisir la fonction (n: entier, k: Integer): Integer
         si k = 0 ou k = n alors
             choisissez = 1
         autre
             choisissez = choisir (n-1, k-1) + choisir (n-1, k)
         fin si
     Fonction d'extrémité
Récupéré à partir de " http://en.wikipedia.org/w/index.php?title=Binomial_coefficient&oldid=205936848 "