Kombinatorika
Kombinatorika (2/7) · 10:16

Kombinace V předchozím videu jsme umisťovali lidi na židle a záleželo nám na tom, kdo sedí na které židli, tedy na jejich pořadí. V tomto videu si ukážeme, jak postupovat, když na pořadí nezáleží.

Navazuje na Pravděpodobnost.
- V předchozím videu jsme si ukázali, kolika různými způsoby můžeme usadit 5 lidí na 3 židle. Například toto je židle jedna, toto židle dva a toto židle tři. Řekli jsme, že na židli jedna můžeme usadit 5 lidí. Nikdo na ní nesedí. Pak budou zbývat pouze 4 lidé, takže na židli 2 můžeme usadit 4 různé lidi. A poté zbydou 3 lidé, které můžeme posadit na židli 3. Šlo o variace. Celkovy počet způsobů, kterými mohou být lidé posazeni na různá místa, jestliže nám záleží na pořadí, tedy jestliže nám záleží na tom, na které židli sedí, bude tedy roven 5 krát 4 krát 3. A jiný způsob, jak o tom můžeme přemýšlet je: 5 krát 4 krát 3 je to samé jako... To se rovná 5 krát 4 krát 3 krát 2 krát 1 nad čím? Nad 2 krát 1. A to je ta samá věc jako 5 faktoriál nad 2 faktoriál. Ale odkuď jsme vzali tuhle 2? Jak je 2 spojena s 5 a 3? Jaký je rozdíl těchto dvou čísel? Je to také 2. Je to to samé. Tohle je rovno 5 faktoriál nad 5 minus 3 faktoriál. A to je v zásadě způsob, jakým jsme zjistili, kolika způsoby můžeme umístit 5 věcí na 3 pozice. Obecný vzorec jsme se naučili v předchozím videu. Změním barvy. Jestliže chceme dát n věcí na k pozic, přičemž k musí být menší nebo rovno n. No dobře, nemusí. Ale pro naše účely budeme nyní předpokládat, že ano, protože by náš vzorec nemusel fungovat, jestliže by to tak nebylo. A to je rovno n faktoriál nad n minus k faktoriál. Vždy mi přijde těžší učit se to nazpaměť než se jen zamyslet nad tímto místem. Pak si jen řeknu, víte, 5 lidí, 5 z těch věcí může být tady. A když už je tady jedna věc, pak zbývají 4 možnosti a pak zbývají 3 možnosti. - Přemýšlím o tom tak, že vezmu prvních k členů z n faktoriál. V tomto případě vezmu první 3 členy z 5 faktoriál. 5 krát 4 krát 3. Takto počítám variace. Je to skvělé, když nám záleží na pořadí. Řekněme, že tu jsou lidé A, B, C, D, E. Takže to je 5 lidí, kteří mají být usazeni na židle. variace jsou skvělé, když uvažujeme, že trojice ABC je jiná než trojice ACB i od trojice -- já nevím -- BAC a stejně tak od trojice BCA. - Pamatujte si, že když jsme toto dělali, tak záleželo na tom, kde který člověk sedí. A v minulém videu jsme vše započítávali dvakrát, protože záleželo na tom, zda osoba A sedí na místě jedna a osoba B na místě dva. A když se prohodili, započítali jsme to znova, je to tak? Tady se prohodili. Ale co kdyby nám na tom nezáleželo? Co kdyby nám nezáleželo na tom, kdo sedí na kterém místě? Chtěli bychom pouze vědět, kolika různými způsoby se může posadit 5 lidí? Chceme započítat všechny situace, kdy lidé A, B, C sedí na místě, jako jednu situaci. Nezáleží nám na tom, kdo sedí na které židli. Záleží nám pouze na tom, aby právě tyto 3 osoby seděly. To je podmnožina sedících osob. A tak je otázkou ne kolika různými permutacemi nebo kolika různými způsoby můžeme posadit tyto osoby, ale kolik podmnožin o 3 prvcích můžeme vybrat z množiny 5 prvků? - Vím, že tak trochu chodím okolo horké kaše, ale to je to, co v podstatě jsou kombinace. Kombinace jsou podobné variacím, ale nezáleží nám na pořadí. Takže jak to spočítat? Když jsme počítali variace použitím tohoto předpisu, počítali jsme například ABC, ACB, BAC, BCA a podívejme se. Měly by tu být ještě dvě další trojice. CAB a CBA. Započítali jsme každou z těchto 6 uspořádaných trojic. Ale v našich kombinacích budeme chtít něco jiného. Je to vše v podstatě stejná kombinace, protože nám nezáleží na pořadí. Takže pro jakékoli 3 různé lidi, kteří jsou na těchto místech, budeme mít 6 trojic, které počítáme, když děláme variace. Takže když chceme kombinace, jen to vydělíme počtem způsobů, kterými můžeme přesadit 3 lidi na 3 místa. To je v podstatě to, co tu děláme. Takže kolika různými způsoby můžeme posadit 3 lidi na 3 místa? No, to je trochu jiný problém. Na první místo můžeme umístit 3 různé osoby, na druhé 2 různé osoby a na poslední místo-- tak to nám zbývá jen jedna osoba. Takže se to rovná 3 faktoriál, který je roven 6. Tohle je rovno 3 faktoriál, který se rovná 6. Doufám, že vás nematu. Snažím se jen říct, že když jsme dělali variace, počítali jsme všechna různá pořadí, v nichž mohli být lidé posazeni. A teď se ptám, kolika různými způsoby se mohou lidé posadit? Bude to počet míst faktoriál protože když máme 3 lidi na 3 místech nebo řekněme 4 lidi na 4 místech. Čtvrté místo mohou obsadit 4 lidé, druhé místo mohou mít 3 a třetí místo 2 a poslední místo může mít pouze 1. Takže počet míst faktoriál zde znamená, kolika způsoby se na ně mohou tři stejní lidé posadit. Když máme přesně ty stejné osoby, které udělají škatulata, hejbejte se na těch samých židlích. Takže abychom určili kombinaci, když bychom chtěli říct, kolik lidí-- řekněme kdybychom měli 5 lidí. Kolik různých skupin po 3 může být usazeno? A nechceme to započítat vícekrát. A nechceme to započítat vícekrát. Neznám slovo pro počítání něčeho šest krát. Bude to stejný případ jako u variací, ale vydělíme to vším, co jsme zahrnuli navíc. Budeme prostě dělit počtem způsobů, kterým mohou být 3 lidé usazeni na 3 místa. A to je 3 faktoriál. - A doufám, že to dává smysl. Možná udělám více příkladů v dalších videích. A určitě si o ně řekněte, jestliže si myslíte, že je to příliš matoucí. Takže obecně, jakými různými způsoby můžeme vybrat n věcí? Nebo počet kombinací, jak může být n věcí vybráno do množin o velikosti r, kde r je menší nebo rovno n. Spočítáme, kolika různými způsoby můžeme umístit n věcí na r míst, a vydělíme r faktoriálem. - Budeme to dělit počtem způsobů, kterými můžou být tytéž věci na r místech přeskupeny, protože nechceme započítat několikrát totéž. A když se vrátíme ke vzorci tady nahoře, tak toto bylo k, ale nyní jsme řekli, že to je r. Je to podobné jako u variací. U variací to bylo n faktoriál nad n minus r faktoriál. A nyní to ještě vydělíme r faktoriál. Takže to se rovná-- jen to napíšu. Toto se často píše jako n kombinace r. Jiným způsobem je n kombinace r. Nazývá se to binomický koeficient a my z nich uděláme celou řadu, protože se to objevuje v polynomiálním rozvoji, když vezmete polynom a umocníte ho. Ale toto se rovná n faktoriál nad r faktoriál děleno n minus r faktoriál. To si můžete zapamatovat. Víte, je to užitečné, když chcete dělat věci rychleji v testech. Ale je důležité přemýšlet o tom, kde se to vzalo. n faktoriál nad n minus r faktoriál-- to jsou jen variace. A co to vůbec bylo? No, to bylo pouze prvních r činitelů, No, to bylo pouze prvních r činitelů, r největších činitelů z n faktoriálu. To je vše. A pak, když uděláme kombinace, vydělíme je r fakroiálem, protože to chceme vydělit všemi různými uskupeními, kterými se mohou titéž lidé posadit na r míst. Nebo míčky mohou být umístěny do r hrníčků. Takže v situaci, kdy chceme vědět, kolika různými způsoby mohou být vybrány skupiny po 3 z 5 lidí nebo z 5 dopisů, bude to 5 faktoriál nad 3 faktoriál krát 5 minus 3 faktoriál. A to je 5 krát 3 krát 2 krát 1 nad-- 3 faktoriál je 6. Dáme to na chvíli bokem. Děleno 2 faktoriál. 2 krát 1. Všimněte si, že tohle je totéž jako u variací. Tento člen se jen zbaví dvou nejnižších činitelů. Dostanete 5 krát 3. Promiňte, je tu ještě 4. 5 krát 4 krát 3, čímž bychom dostali variace. A pak to vydělíme 6, protože dostaneme 6 trojic pro každou kombinaci. Možná vás to zmátlo. Ale i tak, dostaneme (5 krát 4 krát 3) děleno 6. A to je co? 5 krát 12 děleno 6, což je rovno 5 krát 2. Je tu 10 možných způsobů, jak můžeme vybrat skupiny po 3 z množiny 5 věcí. Uvidíme se u dalšího videa.
video