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 :
Lecture et expressions dans divers langages informatiques
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 :
binom(n,k) ou comb(n,k) dans les modules math ou scipy de Python[2] ;
n \choose k en LaTeX (ou \binom{n}{k} avec amsmath).
Établissement de la formule
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
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 :
1
7
21
35
35
21
7
1
8 :
1
8
28
56
70
56
28
8
1
Les coefficients pour 0 ≤ k ≤ n 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.
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
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 :
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 nentiers 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 nentiersstrictement positifs dont la somme vaut k est égale à (nombre de n-compositions de k).
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 :
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 »).
Propriétés arithmétiques des coefficients binomiaux
Divisibilité
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 k⁄pj soit plus grande que la partie fractionnaire de n⁄pj. C'est le nombre de retenues dans l'addition de k et n – k, lorsque ces deux nombres sont écrits en basep[9],[10].
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 kimpliquen. 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
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
Élargissement du domaine de définition
Jusqu'à présent le coefficient binomial était défini pour k et n entiers naturels avec k ≤ n. 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 :
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 k ≤ n 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êtaB :
.
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.
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 r ≥ n ≥ 0)[18] :
.
Encadrement et approximations
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 :
↑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.
↑ ab 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. (consulté le ), p. 5
↑ 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).
Scottish-born scenic designer and artist George GordonPortrait of George Gordon, published in June 1899.BornGeorge Cameron Gordon(1839-06-11)11 June 1839Edinburgh, ScotlandDied12 June 1899(1899-06-12) (aged 60)Melbourne, Victoria, AustraliaOccupation(s)theatre scenic artist; artistSpouseMarion JonesParentWilliam Gordon & Jane (née Stephens) George Cameron Gordon (11 June 1839 – 12 June 1899) was a Scottish-born scenic designer and artist in Australia. His father was in the same li...
Trans Bandar Lampung adalah sistem bus raya terpadu yang mulai beroperasi pada tanggal 01 April 2019 di Kota Bandar Lampung, Lampung. Layanan Bus Rapid Transit ini diciptakan untuk memudahkan mobilitas warga Bandar Lampung agar mau menggunakan transportasi publik.[1] Trans Bandar LampungDidirikan01 April 2019Wilayah layanan Kota Bandar LampungJenis layananbus raya terpaduRute4 koridorJumlah perhentianhalte dalam tahap pembangunanOperator Dinas Perhubungan Kota Bandar Lampung Tarif yan...
Pour les articles homonymes, voir Tchicaya. Jean Félix-Tchicaya Fonctions Député du département du Gabon 18 novembre 1945 – 10 juin 1946(6 mois et 23 jours) Législature 1re Assemblée nationale constituante Groupe politique Union républicaine et résistante Député du département du Gabon 2 juin 1946 – 27 novembre 1946(5 mois et 25 jours) Législature 2e Assemblée nationale constituante Groupe politique Union républicaine et résistante Député du départeme...
Gradualisme filetik dibandingkan dengan keseimbangan bersela (bawah). Gradualisme filetik adalah model evolusi yang menjelaskan bahwa sebagian besar spesiasi bersifat lambat, seragam, dan berangsur-angsur.[1] Seluruh spesies secara perlahan mengalami perubahan menjadi spesies yang baru. Dalam sudut pandang ini, tidak ada garis batas yang jelas antara spesies nenek moyang dengan spesies baru. Gradualisme filetik sering kali dianggap berlawanan dengan teori keseimbangan bersela, yang me...
Опис файлу Опис Театр Темних Пелюсток. Обкладинка альбому Джерело solarice.com.ua Час створення 2008 Автор зображення ХОЛОDНЕ СОНЦЕ Ліцензія див. нижче Ліцензування Це зображення є обкладинкою музичного альбому або синглу. Найімовірніше, авторськими правами на обкладинку волод�...
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Chiodos discography – news · newspapers · books · scholar · JSTOR (November 2023) (Learn how and when to remove this template message) Chiodos discographyChiodos on Warped Tour in 2009Studio albums4Music videos9EPs3Singles9 Chiodos was an American post-hardcore...
Chatterjee in 2009 Abir Chatterjee is an Indian actor who mainly works in Bengali cinema. He started his career with Bengali television and made his debut in Bengali cinema in 2009 as a lead with Cross Connection. He has acted in many Bengali serials including Proloy Asche, Shasuri Zindabad, Khuje Berai Kacher Manush, Banhishikha, Sudhu Tomari Jonno, Ek Aakasher Niche, Janmobhumi.[1][2][3][4] He appeared in Bengali movies as Byomkesh Bakshi and Feluda.[5 ...
Pemilihan Umum Bupati Bangli 2020201520259 Desember 2020[1]Kandidat Calon Sang Nyoman Sedana Arta I Made Subrata Partai PDI-P Partai Golongan Karya Pendamping I Wayan Diar Ngakan Kutha Parwata Peta persebaran suara Peta Bali yang menyoroti Kabupaten Bangli Bupati dan Wakil Bupati petahanaI Made Gianyar danSang Nyoman Sedana Arta Partai Demokrasi Indonesia Perjuangan Bupati dan Wakil Bupati terpilih Sang Nyoman Sedana Arta dan I Wayan Diar Partai Demokrasi Indonesia Perjuangan S...
1954 film by Joseph Pevney This article is about the 1954 film. For similar uses, see Playgirl (disambiguation). PlaygirlTheatrical release posterDirected byJoseph PevneyScreenplay byRobert BleesStory byRay BuffumProduced byAlbert J. CohenStarringShelley WintersBarry SullivanColleen MillerCinematographyCarl E. GuthrieEdited byVirgil W. VogelProductioncompanyUniversal PicturesDistributed byUniversal PicturesRelease date April 21, 1954 (1954-04-21) Running time85 minutesCountryUn...
Ar Raihan beralih ke halaman ini. Untuk kegunaan lain, lihat Ar Raihan (disambiguasi).Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Yayasan Ar Raihan – berita · surat kabar · buku · cendekiawan · JSTOR Artikel ini terlalu bergantung pada referensi dari s...
Music club on Große Freiheit street in Hamburg's St. Pauli district, West Germany For the Japanese punk band, see The Star Club. For the British rock band, see Starclub The Star-ClubEntrance to the Star-Club, Hamburg. 1968LocationHamburg, GermanyPublic transit ReeperbahnOwnerManfred Weissleder and Horst FascherTypeNightclub, music venueGenre(s)Rock and rollCapacity2,000Opened1962Closed1969 The Star-Club was a music club in Hamburg, Germany, that opened on Friday 13 April 1962, and was initia...
Series of 16-bit minicomputers This article is about the PDP–11 series of minicomputers. For the PDP–11 processor architecture, see PDP-11 architecture. PDP–11A PDP–11/40 CPU is at the bottom, with a TU56 dual DECtape drive installed above it.DeveloperDigital Equipment CorporationProduct familyProgrammed Data ProcessorTypeMinicomputerRelease date1970; 53 years ago (1970)Lifespan1970–1997Discontinued1997; 26 years ago (1997)Units soldaround 600,000...
Metro Mall in Athens, Greece. Mediterranean Cosmos in Thessaloniki, Greece. This is a list of shopping malls in Greece, listed in alphabetical order, by region. Region/City Mall Size (TBA) Athens Atehnian Capitol Athens Heart Athens Metro Mall Attica Department Store AVENUE Mall The Golden Hall Mall The Mall Athens McArthurGlen Designer Outlet Athens River West Mall SmartPark West Plaza Shopping Centre Heraklion Talos Plaza Corinth Mare West Thessaloniki Makedonia Mall Mediterranean Cosmos On...
Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. Troli yang digunakan untuk melayani jasa boga minuman di dalam kereta Jasa boga atau yang lebih dikenal dengan katering adalah istilah umum untuk wirausaha yang melayani pemesanan berbagai macam masakan (makanan dan minuman) baik untuk pesta maupun untuk penunjang kebutuhan suatu instansi. Jasa ini di inisiasi untuk me...
Japanese javelin thrower For the New Zealand banker and economist, see Roderick Deane. This article needs to be updated. The reason given is: Article needs updating from 2015 to 2023. Updating what can be updated.. Please help update this article to reflect recent events or newly available information. (October 2023)Roderick Genki DeanDean at the 2012 Japan Championships (Athletics)Personal informationNationality JapanBorn (1991-12-30) 30 December 1991 (age 31)Kobe, JapanHeight1.82&...
2013 Indian filmRomanceDirected byDarling SwamyWritten byDarling SwamyProduced byG. Srinivasa RaoSreenivasa Kumar Naidu (SKN)StarringPrinceDimple ChopadeManasaSaikumar PBhargaviCinematographyJ. Prabhakar ReddyEdited byS. B. UddhavMusic bySai KarthikProductioncompanyGood Cinema GroupRelease date 2 August 2013 (2013-08-02) [1]CountryIndiaLanguageTelugu Romance is a 2013 Telugu-language comedy film directed by Darling Swamy and produced by G. Srinivasa Rao and Sreenivasa ...
Men's association football team This article is about the men's team. For the women's team, see United Arab Emirates women's national football team. United Arab EmiratesNickname(s)Al Abyad (The White One)Eyal Zayed (Sons of Zayed)AssociationUAE Football AssociationConfederationAFC (Asia)Sub-confederationWAFF (West Asia)Head coachPaulo BentoCaptainKhalid EisaMost capsAdnan Al Talyani (161)Top scorerAli Mabkhout (85)Home stadiumVariousFIFA codeUAE First colours Second colours FIFA rankingCurren...