Coefficient binomial
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
et
o?? n! d??signe la factorielle de n.
Selon Nicholas J. Higham, le 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 , 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):
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 est le nombre de fa??ons que k objets peuvent ??tre choisis parmi n objets, ind??pendamment de l'ordre. Plus formellement,
- est le nombre de sous-ensembles de k -Element d'un ensemble de n -Element.
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
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 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
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 exactement fa??ons, un deuxi??me ??l??ment al??atoire dans des moyens, et ainsi de suite. Ainsi, ??l??ments peuvent ??tre r??cup??r??s sur n dans fa??ons. Dans ce calcul, cependant, chaque s??lection de commande ind??pendant se produit fois, comme une liste de ??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
qui d??coule directement de la d??finition:
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 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
- Il y a 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 ; 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
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
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 ≤ i ≤ n, cette somme doit ??tre ??gal au nombre de sous-ensembles de S, qui est connu pour ??tre de 2 n.
La formule
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
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 et , Le Chu-Vandermonde identit??.
Une formule est li?? ??
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
Notons F (n + 1) les num??ros de Fibonacci . On obtient une formule sur les diagonales du triangle de Pascal
Ceci peut ??tre prouv?? par utilisant induction (3).
Aussi l'aide (3) et l'induction, on peut montrer que
Encore une fois par (3) et de l'induction, on peut montrer que pour k = 0, ..., n - 1
aussi bien que
qui est lui-m??me un cas particulier de telle sorte que pour tout entier a = 1, ..., n - 1,
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,
pour La preuve combinatoire va comme suit: le c??t?? gauche compte le nombre de fa??ons de choisir un sous-ensemble 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 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 Cela r??duit ?? (6) lorsque
L'identit?? (8) pr??sente ??galement une preuve combinatoire. L'identit?? lit
Supposons que vous avez carr??s vides dispos??s dans une rang??e et vous souhaitez marquer (s??lection) n d'entre eux. Il y a fa??ons de le faire. D'autre part, vous pouvez choisir vos places en s??lectionnant n k places parmi le premier n et carr??s des autres n carr??s. Cela donne
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 ??tre le nombre de fa??ons de partitionnement en deux sous-ensembles, dont le premier a une taille k. Ces partitions forment une classe combinatoire avec la sp??cification
D'o?? l'exponentielle g??n??rer la fonction B de la fonction de somme des coefficients binomiaux est donn??e par
On obtient imm??diatement
comme pr??vu. Nous c??l??brons le premier sous-ensemble avec afin d'obtenir les coefficients binomiaux eux-m??mes, ce qui donne
On obtient ainsi la fonction g??n??ratrice bidimensionnelle
Extraire des coefficients, nous constatons que
ou
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
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:
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:
o??
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:
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, o?? 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:
et la sym??trie:
o?? est une permutation de (1,2, ..., r).
G??n??ralisation aux entiers n??gatifs
Si , Puis se ??tend ?? toutes .
Le coefficient binomial ??tend ?? via
Remarquez en particulier que
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 peut ??tre d??finie pour tout nombre complexe z et tout nombre naturel k comme suit:
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 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
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:
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:
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
lorsque l'identit??
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:
o?? A est un ensemble avec cardinalit?? . 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 , 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 pour tout cardinal infini .
Coefficient binomial des langages de programmation
La notation 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 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??