Kombinace (matematika)
Když v matematice vybereme k objektů z n rozpoznatelných objektů (očíslovaných od 1 do n ) a nezáleží na pořadí, ve kterém jsou objekty umístěny (nebo vyčísleny), můžeme je reprezentovat množinou s prvky k . Tyto kombinace se používají proto, mimo jiné, v kombinaci . Příkladem je ruka získaná současným tažením k karet ze sady n karet ; nebo v loterijní hře konečné losování (které nezávisí na pořadí vzhledu získaných míčků).
Definice
Nechť E je konečná množina z Cardinal n a k je přirozené číslo v . Kombinace této sady jsou její podmnožiny (nebo části).
K -Combination z E (nebo k -Combination bez opakování E , nebo kombinací bez opakování n prvků přijatých k, na k ), patří do K prvky E .
Poznámka: všechny K -searches z E .
Pk(E){\ displaystyle {\ mathcal {P}} _ {k} (E)}
Počet kombinací
Sada je konečná a její kardinál je binomický koeficient , také známý . My máme :
Pk(E){\ displaystyle {\ mathcal {P}} _ {k} (E)} (nek){\ displaystyle {n \ vyberte k}}VSnek{\ displaystyle C_ {n} ^ {k}}
VSnek=(nek)=NAnekk!{\ displaystyle C_ {n} ^ {k} = {n \ zvolit k} = {\ frac {A_ {n} ^ {k}} {k!}}},
kde je počet k - ujednání o E a K ! je faktoriál z k .
NAnek{\ displaystyle A_ {n} ^ {k}}
Se vzorcem pro dostaneme , který pro k ≤ n lze také napsat:
NAnek=ne!(ne-k)!{\ displaystyle A_ {n} ^ {k} = {\ frac {n!} {(nk)!}}}(nek)=ne(ne-1)...(ne-k+1)k!{\ displaystyle {n \ zvolit k} = {\ frac {n (n-1) \ ldots (n-k + 1)} {k!}}}
(nek)=ne!k!(ne-k)!{\ displaystyle {n \ zvolit k} = {\ frac {n!} {k! (nk)!}}}.
Výpočet počtu kombinací
Efektivní algoritmus pro výpočet počtu kombinací k- prvky mezi N , používá následující identity (0 ≤ k ≤ n ):
(nek){\ displaystyle {\ binom {n} {k}}}
(nek)=(nene-k){\ displaystyle {\ binom {n} {k}} = {\ binom {n} {nk}}},
A
.
(ne+1k+1)=ne+1k+1(nek){\ displaystyle {\ binom {n + 1} {k + 1}} = {\ frac {n + 1} {k + 1}} {\ binom {n} {k}}}(ne0)=1{\ displaystyle {\ binom {n} {0}} = 1}
První umožňuje snížit počet operací, které mají být provedeny, snížením na k ≤ n / 2. Následující dva ukazují, že:
(nek)=(ne-k+1)1⋅(ne-k+2)2⋅⋯⋅nek{\ displaystyle {\ binom {n} {k}} = {\ frac {(n-k + 1)} {1}} \ cdot {\ frac {(n-k + 2)} {2}} \ cdot \ cdots \ cdot {\ frac {n} {k}}}
V každém kroku výpočtu nejprve provedeme násobení, poté dělení, abychom získali celé číslo (jedná se o binomický koeficient), to znamená, že můžeme použít celočíselné dělení. Mezilehlé výpočty zůstávají řádově blízké konečnému výsledku (to by nebylo v případě, kdyby byl použit například první vzorec a faktoriální funkce).
Výpočet lze provést jednoduchou iterační smyčkou ( pro smyčku ).
Příklad
(107)=?10-7=3<7,(70)=1⇒(81)=81×1=8⇒(92)=92×8=36⇒(103)=103×36=120⇒(107)=120.{\ displaystyle {\ binom {10} {7}} =? \ quad 10-7 = 3 <7, \ quad {\ binom {7} {0}} = 1 \ Rightarrow {\ binom {8} {1} } = {\ frac {8} {1}} \ krát 1 = 8 \ Rightarrow {\ binom {9} {2}} = {\ frac {9} {2}} \ krát 8 = 36 \ Rightarrow {\ binom {10} {3}} = {\ frac {10} {3}} \ krát 36 = 120 \ Rightarrow {\ binom {10} {7}} = 120.}
Pro velké hodnoty n a k je často praktičtější použít následující přibližné vzorce (ospravedlnění a další najdeme podrobněji v článku binomický koeficient ):
(nek)∼nek/k!{\ displaystyle {n \ vyberte k} \ sim n ^ {k} / k!} (pro pevné k a n směřující k nekonečnu) a (pokud n a k mají sklon k nekonečnu s ) .
k/ne→α∈]0;1[{\ displaystyle k / n \ rightarrow \ alpha \ in] 0; 1 [}(nek)∼12πα(1-α)ne(1αα(1-α)1-α)ne{\ displaystyle {\ binom {n} {k}} {\ sim} {\ frac {1} {\ sqrt {2 \ pi \ alpha (1- \ alpha) n}}} \ vlevo ({\ frac {1 } {\ alpha ^ {\ alpha} (1- \ alpha) ^ {1- \ alpha}}} \ vpravo) ^ {n}}
Seznam kombinací
Nechť A je množina s n prvky, na objekt, který není v A , a k celé přirozené číslo. Poté, abychom vytvořili části s prvky k + 1, vytvoříme části k + 1 prvků A , stejně jako části k prvků A, ke kterým přidáme { a }. Jinými slovy :
NA∪{na}{\ displaystyle A \ cup \ {a \}}
Pk+1(NA∪{na})=Pk+1(NA)∪{X∪{na}∣X∈Pk(NA)}{\ displaystyle {\ mathcal {P}} _ {k + 1} (A \ cup \ {a \}) = {\ mathcal {P}} _ {k + 1} (A) \ cup \ left \ {X \ cup \ {a \} \ mid X \ in {\ mathcal {P}} _ {k} (A) \ right \}}
( pokud k > n )
Pk(NA)=∅{\ displaystyle {\ mathcal {P}} _ {k} (A) = \ varnothing}
(Tato identita byl přímým důsledkem vzorce opakování stavět Pascalova trojúhelníku :
). Tuto identitu lze využít pro algoritmus výčtu kombinací, například prvních n celých čísel.
(ne+1k+1)=(nek+1)+(nek){\ displaystyle {\ tbinom {n + 1} {k + 1}} = {\ tbinom {n} {k + 1}} + {\ tbinom {n} {k}}}
Příklady
Nechť A je množina 5 prvků A = { a , b , c , d , e }.
- Kombinace 2 prvků mezi 5 jsou:
- ty, které obsahují dva odlišné prvky a : { b , c }, { b , d }, { b , e }, { c , d }, { c , e }, { d , e },
- ty, které obsahují a a další prvek: { a , b }, { a , c }, { a , d }, { a , e },
nebo(52)=(42)+(41)=6+4=10.{\ displaystyle {5 \ zvolit 2} = {4 \ zvolit 2} + {4 \ zvolit 1} = 6 + 4 = 10.}
- Kombinace 3 prvků vybraných z 5 prvků A jsou:
- ty, které obsahují a a další dva prvky: { a , b , c }, { a , b , d }, { a , b , e }, { a , c , d }, { a , c , e }, { a , d , e },
- ty, které obsahují tři odlišné prvky a : { b , c , d }, { b , c , e }, { b , d , e }, { c , d , e }
nebo(53)=(42)+(43)=6+4=10.{\ displaystyle {5 \ zvolit 3} = {4 \ zvolit 2} + {4 \ zvolit 3} = 6 + 4 = 10.}.
Ve skutečnosti jsou doplňkem předchozích kombinací.
Poznámky a odkazy
Poznámky
-
Demonstrace je k dispozici prostřednictvím odkazu ( viz níže ) na Kombinace Wikiversity bez opakování .
-
Toto je například ten, který používá knihovna programů s aritmetickou libovolnou přesností GMP , viz (en) Algoritmus binomických koeficientů .
Reference
-
Louis Comtet , Elementární kombinatorická analýza , str. 2 .
-
Hervé Gianella, Romain Krust, Frank Taieb a Nicolas Tosel, Vybrané problémy vyšší matematiky , str. 120 .
Podívejte se také
Kombinace s opakováním
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">