Kombinace - Combination

V matematice je kombinace výběr položek ze sbírky, takže na pořadí výběru nezáleží (na rozdíl od permutací ). Například vzhledem ke třem plodům, řekněme jablko, pomeranč a hruška, existují tři kombinace dvou, které lze z této sady čerpat: jablko a hruška; jablko a pomeranč; nebo hruška a pomeranč. Více formálně, je k - kombinace z nastavené S je podmnožinou k- odlišných prvků S . Pokud má sada n prvků, je počet k -kombinací roven binomickému koeficientu

${\ Displaystyle {\ binom {n} {k}} = {\ frac {n (n-1) \ dotsb (n-k+1)} {k (k-1) \ dotsb 1}},}$

které lze zapsat pomocí faktoriálů jako kdykoli a které je nulové, když . Množina všech k -kombinací množiny S se často označuje . ${\ displaystyle \ textstyle {\ frac {n!} {k! (nk)!}}}}$${\ Displaystyle k \ leq n}$${\ displaystyle k> n}$${\ displaystyle \ textstyle {\ binom {S} {k}}}$

Kombinace se týkají kombinace n věcí pořízených k najednou bez opakování. Odkázat na kombinace, ve které je povoleno opakování, podmínek k -selection, k- - multiset nebo K -combination s opakováním se často používají. Pokud by ve výše uvedeném příkladu bylo možné mít dva z jakéhokoli druhu ovoce, byly by ještě 3 2 výběry: jeden se dvěma jablky, jeden se dvěma pomeranči a jeden se dvěma hruškami.

Přestože byla sada tří plodů dostatečně malá na to, aby sepsal kompletní seznam kombinací, s rostoucí velikostí sady to bude nepraktické. Například, poker ruka může být popsán jako 5-kombinace ( K  = 5) karet z paluby 52 karet ( n  = 52). Všech 5 karet ruky je odlišných a na pořadí karet v ruce nezáleží. Existuje 2 598 960 takových kombinací a šance na náhodnou remízu jedné ruky je 1 /2 598 960.

Počet k -kombinací

3prvkové podmnožiny 5prvkové sady

Počet k- -combinations z dané množiny S o n prvků je často označován za elementární kombinatorika textech , nebo variace jako například , , , nebo dokonce (druhá forma je standardní ve francouzštině, rumunštině, ruštině, čínštině a polštině texty). Stejné číslo se však vyskytuje v mnoha dalších matematických kontextech, kde je označeno (často čten jako „ n choose k “); zejména se vyskytuje jako koeficient v binomickém vzorci , odtud jeho název binomický koeficient . Pro vztah lze definovat všechna přirozená čísla k najednou ${\ Displaystyle C (n, k)}$${\ displaystyle C_ {k}^{n}}$${\ displaystyle {} _ {n} C_ {k}}$${\ displaystyle {}^{n} C_ {k}}$${\ displaystyle C_ {n, k}}$${\ displaystyle C_ {n}^{k}}$${\ displaystyle {\ tbinom {n} {k}}}$${\ displaystyle {\ tbinom {n} {k}}}$

${\ Displaystyle (1+X)^{n} = \ sum _ {k \ geq 0} {\ binom {n} {k}} X^{k},}$

ze kterého je zřejmé, že

${\ displaystyle {\ binom {n} {0}} = {\ binom {n} {n}} = 1,}$

a dál,

${\ displaystyle {\ binom {n} {k}} = 0}$pro k  >  n .

Abychom viděli, že tyto koeficienty počítají k -kombinace ze S , lze nejprve zvážit kolekci n odlišných proměnných X _s označených prvky s ze S a rozšířit součin přes všechny prvky  S :

${\ displaystyle \ prod _ {s \ in S} (1+X_ {s});}$

má 2 ⁿ odlišných výrazů odpovídajících všem podmnožinám S , přičemž každá podmnožina dává součin odpovídajících proměnných X _s . Nyní nastavení všech X _s rovných neznačené proměnné X , takže produkt se stane (1 + X ) ⁿ , termín pro každou k -kombinaci ze S se stane X ^k , takže koeficient této síly ve výsledku se rovná počet takových k -kombinací.

Binomické koeficienty lze vypočítat explicitně různými způsoby. Chcete -li získat všechny z nich pro expanze až (1 + X ) ⁿ , lze použít (kromě již uvedených základních případů) relaci rekurze

${\ displaystyle {\ binom {n} {k}} = {\ binom {n-1} {k-1}}+{\ binom {n-1} {k}},}$

pro 0 < k < n , což vyplývá z (1 + X ) ⁿ = (1 + X ) ^{n - 1} (1 + X ) ; to vede ke konstrukci Pascalova trojúhelníku .

Pro stanovení individuálního binomického koeficientu je praktičtější použít vzorec

${\ Displaystyle {\ binom {n} {k}} = {\ frac {n (n-1) (n-2) \ cdots (n-k+1)} {k!}}}$.

Čitatel udává počet k- -permutations z n , tj, ze sekvencí k- odlišných prvků S , zatímco jmenovatel udává počet takových k- -permutations, které poskytují stejnou k -combination pokud je příkaz ignorován.

Pokud k překročí n /2, výše uvedený vzorec obsahuje faktory společné pro čitatele a jmenovatele a jejich zrušením získáte vztah

${\ displaystyle {\ binom {n} {k}} = {\ binom {n} {nk}},}$

pro 0 ≤ k ≤ n . To vyjadřuje symetrie, která je zřejmá z binomické vzorce, a může být také zřejmé, pokud jde o k- -combinations tím, že se doplněk takové kombinace, která je ( n - k ) -combination.

Nakonec existuje vzorec, který přímo ukazuje tuto symetrii a má tu výhodu, že je snadno zapamatovatelný:

${\ displaystyle {\ binom {n} {k}} = {\ frac {n!} {k! (nk)!}},}$

kde n ! označuje faktoriál z n . Získává se z předchozího vzorce vynásobením jmenovatele a čitatele ( n - k ) !, Takže je určitě výpočetně méně efektivní než tento vzorec.

Poslední vzorec lze pochopit přímo, když vezmeme v úvahu n ! permutací všech prvků S . Každá taková permutace dává k -kombinaci výběrem jejích prvních k prvků. Existuje mnoho duplicitních výběrů: jakákoli kombinovaná permutace prvních k prvků mezi sebou a konečných ( n  -  k ) prvků mezi sebou vytváří stejnou kombinaci; to vysvětluje rozdělení ve vzorci.

Z výše uvedených vzorců sledujte vztahy mezi sousedními čísly v Pascalově trojúhelníku ve všech třech směrech:

${\ displaystyle {\ binom {n} {k}} = {\ begin {cases} {\ binom {n} {k-1}} {\ frac {n-k+1} {k}} & \ quad { \ text {if}} k> 0 \\ {\ binom {n-1} {k}} {\ frac {n} {nk}} & \ quad {\ text {if}} k <n \\ {\ binom {n-1} {k-1}} {\ frac {n} {k}} & \ quad {\ text {if}} n, k> 0 \ end {cases}}}$.

Spolu s základní případy , že umožňují postupné výpočet respektive všech čísel kombinace ze stejné skupiny (řádek v Pascalova trojúhelníku), ze k- -combinations množin rostoucích velikostí, a kombinace s komplementem pevnou velikostí n - K . ${\ displaystyle {\ tbinom {n} {0}} = 1 = {\ tbinom {n} {n}}}$

Příklad kombinací počítání

Jako konkrétní příklad lze vypočítat počet možných karet pěti karet ze standardního balíčku padesáti dvou karet jako:

${\ Displaystyle {52 \ choose 5} = {\ frac {52 \ times 51 \ times 50 \ times 49 \ times 48} {5 \ times 4 \ times 3 \ times 2 \ times 1}} = {\ frac {311 {,} 875 {,} 200} {120}} = 2 {,} 598 {,} 960.}$

Alternativně lze použít vzorec z hlediska faktoriálů a zrušit faktory v čitateli proti částem faktorů ve jmenovateli, po kterém je požadováno pouze vynásobení zbývajících faktorů:

${\ displaystyle {\ begin {alignedat} {2} {52 \ choose 5} & = {\ frac {52!} {5! 47!}} \\ [5pt] & = {\ frac {52 \ times 51 \ krát 50 \ krát 49 \ krát 48 \ krát {\ zrušit {47!}}} {5 \ krát 4 \ krát 3 \ krát 2 \ krát {\ zrušit {1}} \ krát {\ zrušit {47!}}} } \\ [5pt] & = {\ frac {52 \ times 51 \ times 50 \ times 49 \ times 48} {5 \ times 4 \ times 3 \ times 2}} \\ [5pt] & = {\ frac { (26 \ times {\ cancel {2}}) \ times (17 \ times {\ cancel {3}}) \ times (10 \ times {\ cancel {5}}) \ times 49 \ times (12 \ times { \ cancel {4}})} {{\ cancel {5}} \ times {\ cancel {4}} \ times {\ cancel {3}} \ times {\ cancel {2}}}} \\ [5pt] & = {26 \ times 17 \ times 10 \ times 49 \ times 12} \\ [5pt] & = 2 {,} 598 {,} 960. \ end {alignedat}}}$

Další alternativní výpočet, ekvivalentní prvnímu, je založen na psaní

${\ displaystyle {n \ choose k} = {\ frac {(n-0)} {1}} \ times {\ frac {(n-1)} {2}} \ times {\ frac {(n-2 )} {3}} \ times \ cdots \ times {\ frac {(n- (k-1))} {k}},}$

který dává

${\ displaystyle {52 \ choose 5} = {\ frac {52} {1}} \ times {\ frac {51} {2}} \ times {\ frac {50} {3}} \ times {\ frac { 49} {4}} \ times {\ frac {48} {5}} = 2 {,} 598 {,} 960}$.

Při vyhodnocení v následujícím pořadí, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 , to lze vypočítat pouze pomocí celočíselné aritmetiky. Důvodem je, že když dojde k každé dělení, mezivýsledek, který je produkován, je sám o sobě binomickým koeficientem, takže nikdy nedochází k žádným zbytkům.

Použití symetrického vzorce z hlediska faktoriálů bez provádění zjednodušení poskytuje poměrně rozsáhlý výpočet:

${\ displaystyle {\ begin {aligned} {52 \ choose 5} & = {\ frac {n!} {k! (nk)!}} = {\ frac {52!} {5! (52-5)! }} = {\ frac {52!} {5! 47!}} \\ [6pt] & = {\ tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,000,000,000} {120 \ krát 258,623,241,168,160 ,} 960. \ end {aligned}}}$

Výčet k -kombinací

Jeden může vyjmenovat všechny K -combinations daného souboru S z n prvků v nějakém pevném pořadí, který zavádí bijection z intervalu čísel se souborem těchto k- -combinations. Za předpokladu, že S je samo seřazeno, například S = {1, 2,…, n }, existují dvě přirozené možnosti pro uspořádání jeho k -kombinací: nejprve porovnáním jejich nejmenších prvků (jako na obrázcích výše) nebo porovnáním jejich největších prvky jako první. Druhá možnost má tu výhodu, že přidání nového největšího prvku do S nezmění počáteční část výčtu, ale pouze přidá nové k -kombinace větší sady po předchozích. Opakováním tohoto procesu lze výčet neomezeně prodloužit k -kombinacemi stále větších sad. Pokud navíc intervaly celých čísel začínají na 0, pak k -kombinace na daném místě i ve výčtu lze snadno vypočítat z i a takto získaná bijekce je známá jako kombinatorický číselný systém . Ve výpočetní matematice je také známý jako „hodnost“/„hodnocení“ a „odkrytí“. ${\ displaystyle {\ tbinom {n} {k}}}$

Existuje mnoho způsobů, jak vyjmenovat k kombinací. Jedním ze způsobů je navštívit všechna binární čísla menší než 2 ⁿ . Vyberte si ty čísla, které mají K nenulový bitů, ačkoli toto je velmi neefektivní a to i pro malé n (např n = 20 by vyžadovalo návštěvu kolem jednoho milionu čísel, přičemž maximální počet povolených k- kombinací je asi 186 tisíc pro k = 10). Pozice těchto 1 bitů v takovém počtu je specifickou k -kombinací množiny {1, ..., n }. Dalším jednoduchým a rychlejším způsobem je sledovat k indexová čísla vybraných prvků, počínaje {0 .. k −1} (na základě nuly) nebo {1 .. k } (na jednom) jako první povolená kombinace k a pak se opakovaně přesouvá na další povolenou kombinaci k -zvýšením posledního indexového čísla, pokud je nižší než n -1 (na základě nuly) nebo n (na základě jednoho) nebo posledního indexového čísla x, které je menší než indexové číslo po něm mínus jeden, pokud takový index existuje, a resetování čísel indexů po x na { x +1, x +2, ...}.

Počet kombinací s opakováním

A k - kombinace s opakováním , nebo k - multikombinace , nebo vícenásobná velikost k z množiny S je dána sadou k ne nutně odlišných prvků S , kde není brán v úvahu řád: dvě sekvence definují stejnou vícenásobnou, pokud jedno lze získat od druhého permutací podmínek. Jinými slovy, je to vzorek k prvků ze sady n prvků umožňujících duplikáty (tj. S náhradou), ale bez ohledu na různá uspořádání (např. {2,1,2} = {1,2,2}). Ke každému prvku S přiřaďte index a uvažujte o prvcích S jako typech objektů, pak můžeme nechat označit počet prvků typu i ve více podskupině. Počet vícenásobných podskupin velikosti k je pak počet nezáporných celočíselných řešení diophantské rovnice : ${\ displaystyle x_ {i}}$

${\ Displaystyle x_ {1}+x_ {2}+\ ldots+x_ {n} = k.}$

Pokud S má n prvků, počet takových k -vícenásobných sad je označen,

${\ displaystyle \ left (\! \! {\ binom {n} {k}} \! \! \ right),}$

zápis, který je analogický s binomickým koeficientem, který počítá k -podmnožiny. Tento výraz, n multichoose k , lze také zadat z hlediska binomických koeficientů:

${\ Displaystyle \ left (\! \! {\ binom {n} {k}} \! \! \ right) = {\ binom {n+k-1} {k}}.}$

Tento vztah lze snadno prokázat pomocí reprezentace známé jako hvězdy a mříže .

Důkaz

Řešení výše uvedené diofantické rovnice může být reprezentováno hvězdami , oddělovačem ( pruhem ), pak více hvězd, dalším oddělovačem atd. Celkový počet hvězd v této reprezentaci je k a počet tyčí je n - 1 (protože rozdělení na n částí vyžaduje n -1 oddělovače). Řetězec k + n - 1 symbolů (hvězdy a pruhy) tedy odpovídá řešení, pokud je v řetězci k hvězd. Jakékoli řešení lze znázornit výběrem k z k + n - 1 pozic pro umístění hvězd a vyplnění zbývajících pozic pruhy. Například řešení rovnice může být reprezentováno ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$${\ Displaystyle x_ {1} = 3, x_ {2} = 2, x_ {3} = 0, x_ {4} = 5}$${\ displaystyle x_ {1}+x_ {2}+x_ {3}+x_ {4} = 10}$

$${\ Displaystyle \ bigstar \ bigstar \ bigstar | \ bigstar \ bigstar || \ bigstar \ bigstar \ bigstar \ bigstar \ bigstar.}$$

Počet takových řetězců je počet způsobů, jak umístit 10 hvězd na 13 pozic, což je počet 10 multisubsetů sady se 4 prvky. ${\ textstyle {\ binom {13} {10}} = {\ binom {13} {3}} = 286,}$

Bijection mezi 3 podmnožinami 7-sady (vlevo) a 3-více sadami s prvky z 5-sady (vpravo).
To to ilustruje .${\ textstyle {\ binom {7} {3}} = \ left (\! \! {\ binom {5} {3}} \! \! \ right)}$

Stejně jako u binomických koeficientů existuje mezi těmito mnohočetnými výrazy několik vztahů. Například pro , ${\ Displaystyle n \ geq 1, k \ geq 0}$

${\ Displaystyle \ left (\! \! {\ binom {n} {k}} \! \! \ right) = \ left (\! \! {\ binom {k+1} {n-1}} \ !\!\že jo).}$

Tato identita vyplývá z výměny hvězd a pruhů ve výše uvedeném znázornění.

Příklad počítání vícenásobných sad

Pokud například máte  v nabídce na výběr čtyři druhy koblih ( n = 4) a chcete tři koblihy ( k  = 3), lze počet způsobů, jak vybrat koblihy s opakováním, vypočítat jako

${\ Displaystyle \ left (\! \! {\ binom {4} {3}} \! \! \ right) = {\ binom {4+3-1} {3}} = {\ binom {6} { 3}} = {\ frac {6 \ krát 5 \ krát 4} {3 \ krát 2 \ krát 1}} = 20.}$

Tento výsledek lze ověřit vypsáním všech 3 multisubsetů sady S = {1,2,3,4}. To je zobrazeno v následující tabulce. Druhý sloupec uvádí koblihy, které jste si skutečně vybrali, třetí sloupec ukazuje nezáporná celočíselná řešení rovnice a poslední sloupec představuje řešení a hvězdičky a pruhy. ${\ displaystyle [x_ {1}, x_ {2}, x_ {3}, x_ {4}]}$${\ displaystyle x_ {1}+x_ {2}+x_ {3}+x_ {4} = 3}$

Ne.	3-více sad	Rov. Řešení	Hvězdy a tyče
1	{1,1,1}	[3,0,0,0]	${\ displaystyle \ bigstar \ bigstar \ bigstar |||}$
2	{1,1,2}	[2,1,0,0]	${\ displaystyle \ bigstar \ bigstar | \ bigstar ||}$
3	{1,1,3}	[2,0,1,0]	${\ displaystyle \ bigstar \ bigstar || \ bigstar |}$
4	{1,1,4}	[2,0,0,1]	${\ displaystyle \ bigstar \ bigstar ||| \ bigstar}$
5	{1,2,2}	[1,2,0,0]	${\ displaystyle \ bigstar | \ bigstar \ bigstar ||}$
6	{1,2,3}	[1,1,1,0]	${\ displaystyle \ bigstar | \ bigstar | \ bigstar |}$
7	{1,2,4}	[1,1,0,1]	${\ displaystyle \ bigstar | \ bigstar || \ bigstar}$
8	{1,3,3}	[1,0,2,0]	${\ displaystyle \ bigstar || \ bigstar \ bigstar |}$
9	{1,3,4}	[1,0,1,1]	${\ displaystyle \ bigstar || \ bigstar | \ bigstar}$
10	{1,4,4}	[1,0,0,2]	${\ displaystyle \ bigstar ||| \ bigstar \ bigstar}$
11	{2,2,2}	[0,3,0,0]	${\ displaystyle | \ bigstar \ bigstar \ bigstar ||}$
12	{2,2,3}	[0,2,1,0]	${\ displaystyle | \ bigstar \ bigstar | \ bigstar |}$
13	{2,2,4}	[0,2,0,1]	${\ displaystyle | \ bigstar \ bigstar || \ bigstar}$
14	{2,3,3}	[0,1,2,0]	${\ displaystyle | \ bigstar | \ bigstar \ bigstar |}$
15	{2,3,4}	[0,1,1,1]	${\ displaystyle | \ bigstar | \ bigstar | \ bigstar}$
16	{2,4,4}	[0,1,0,2]	${\ displaystyle | \ bigstar || \ bigstar \ bigstar}$
17	{3,3,3}	[0,0,3,0]	${\ displaystyle || \ bigstar \ bigstar \ bigstar |}$
18	{3,3,4}	[0,0,2,1]	${\ displaystyle || \ bigstar \ bigstar | \ bigstar}$
19	{3,4,4}	[0,0,1,2]	${\ displaystyle || \ bigstar | \ bigstar \ bigstar}$
20	{4,4,4}	[0,0,0,3]	${\ displaystyle ||| \ bigstar \ bigstar \ bigstar}$

Počet k -kombinací pro všechny k

Počet k -kombinací pro všechna k je počet podmnožin sady n prvků. Existuje několik způsobů, jak zjistit, že toto číslo je 2 ⁿ . Pokud jde o kombinace, což je součet n -té řady (počítáno od 0) binomických koeficientů v Pascalově trojúhelníku . Tyto kombinace (podmnožiny) jsou vyjmenovány 1 číslicemi sady základních 2 čísel čítajících od 0 do 2 ⁿ  - 1, kde každá pozice číslice je položkou ze sady n . ${\ textstyle \ sum _ {0 \ leq {k} \ leq {n}} {\ binom {n} {k}} = 2^{n}}$

Vzhledem k tomu, 3 karty očíslované 1 až 3, existuje 8 různých kombinací ( podmnožin ), včetně prázdné sady :

${\ Displaystyle | \ {\ {\}; \ {1 \}; \ {2 \}; \ {1,2 \}; \ {3 \}; \ {1,3 \}; \ {2,3 \}; \ {1,2,3 \} \} | = 2^{3} = 8}$

Reprezentace těchto podmnožin (ve stejném pořadí) jako základní 2 číslice:

0 - 000

1 - 001

2 - 010

3 - 011

4 - 100

5 - 101

6 - 110

7 - 111

Pravděpodobnost: výběr náhodných kombinací

Existují různé algoritmy pro výběr náhodné kombinace z dané sady nebo seznamu. Odmítnutí vzorkování je extrémně pomalé pro velké velikosti vzorků. Jedním ze způsobů, jak efektivně vybrat k -kombinaci z populace velikosti n, je iterovat přes každý prvek populace a v každém kroku vybrat tento prvek s dynamicky se měnící pravděpodobností . (viz odběr vzorků z nádrže ). ${\ textstyle {\ frac {k-\#{\ text {ukázky vybrány}}} {n-\#{\ text {ukázky navštíveny}}}}}$

Viz také

Poznámky

Reference

• Benjamin, Arthur T .; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof , The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
• Erwin Kreyszig , Advanced Engineering Mathematics , John Wiley & Sons, INC, 1999.
• Mazur, David R. (2010), Combinatorics: A Guided Tour , Mathematical Association of America, ISBN 978-0-88385-762-5
• Ryser, Herbert John (1963), Combinatorial Mathematics , The Carus Mathematical Monographs 14, Mathematical Association of America

externí odkazy

• Topcoder tutoriál o kombinatorice
• C kód pro generování všech kombinací n prvků vybraných jako k
• Mnoho běžných typů problémů s permutací a kombinací matematiky s podrobnými řešeními
• Neznámý Formula U kombinací, když volby se mohou opakovat a objednávka dělá ne ohledu na to,
• Kombinace s opakováním (podle: Akshatha AG a Smitha B)
• Hod kostkami s daným součtovým problémem Aplikace kombinací s opakováním na házení více kostkami