V kapitole Intuitivní kombinatorika jsme řešili příklady více méně stejným způsobem na stejných principech. Nyní si je zobecníme a nadefinujeme obvyklou terminologii.
pravidlo součtu: Jestliže nějaký objekt A můžeme vybrat m způsoby a jiný objekt B lze vybrat n způsoby, potom výběr „buď A nebo B“ je možné provést m+n způsoby.
pravidlo součinu: Jestliže nějaký objekt A můžeme vybrat m způsoby a jestliže po každém takovém výběru lze jiný objekt B vybrat n způsoby, potom výběr „A a zároveň B“ je možné provést m.n způsoby. Uvažme následující postup výběru předmětů z množiny obsahující konečný počet plně od sebe rozeznatelných předmětů.
Mechanismus výběru: Je dána množina M obsahující n různých prvků. Z množiny M vybereme jeden prvek a odložíme ho stranou, za ním vybereme další a odložíme vedle prvního, atd, až jich vybereme celkem k; 0 k n. Z vybraných prvků stranou se stala k-tice. Zdůrazněme: vybrané prvky nevracíme zpět. Zajímá nás: 1) Kolik různých uspořádaných k-tic (rozeznáváme pořadí prvků) můžeme takto dostat? 2) Kolik různých neuspořádaných k-tic (nerozeznáváme pořadí prvků) můžeme takto dostat?
Definice: Uspořádaná k-tice z n prvků se nazývá variace k-té třídy z n prvků a jejich počet se značí V(k,n). Uspořádaná n-tice z n prvků se nazývá permutace z n prvků a jejich počet se značí P(n). Permutace je zvláštní případ variace P(n) = V(n,n). Neuspořádaná k-tice z n prvků se nazývá kombinace k-té třídy z n prvků a jejich počet se značí K(k,n). Poznámka: Neuspořádané k-tice z n prvků jsou vlastně podmnožiny o k prvcích získané z množiny obsahující n prvků.
Věta vzorců o počtech: Počet variací k-té třídy z n prvků je Počet permutací z n prvků je Počet kombinací k-té třídy z n prvků je
V(k,n) = n.(n-1).(n-2)....(n-k+1) P(n) = V(n,n) = n! n K(k,n) = V(k,n)/P(k) = ( k)
Úkol: U následujících příkladů určete, zda se jedná o permutace, kombinace nebo variace: a) Tomáš, Honza, Věra si podávají ruku. Kolik bude podání ruky? b) Pravidelný osmiúhelník má vrcholy K, L, M, N, O, P, Q, R. Kolik existuje trojúhelníků, které mají vrchol ve vrcholech osmiúhelníka. c) Karel, Pavel, Dušan, Eva a Karla běží závod na 100 m. Kolika způsoby je možné sestavit trojici vítězů, které budou stát na stupni vítězů? d) S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 5 poslanců. Určete počet všech možných pořadí vystoupení jednotlivých poslanců. e) Kolika způsoby mohou Petr, Karel, Zdeněk, František a Dušan ráno na táboře nastoupit do řady? f) Kolika způsoby je možné sestavit vlajku, která má být složena ze tří různobarevných pruhů, máme-li k dispozici barvu zelenou, černou, žlutou, fialovou, bílou? g) Kolika způsoby je možné sestavit vlajku, která má být složena ze tří různobarevných pruhů, máme-li k dispozici barvu zelenou, černou, žlutou? 3
8
odpověď: a) kombinace ( 2) = 3; b) kombinace ( 3) = 56; c) variace 5.4.3 = 60; d) permutace 5! = 120; e) permutace 5! = 120; f) variace 5.4.3 = 60; g) permutace 3! = 6;
Příklad 1: Kolik přirozených čísel větších než 3000 lze vytvořit z cifer 1,2,3,4, jestliže se žádná cifra nesmí opakovat? Řešte a) intuitivně, b) vzorci (permutace, kombinace, variace) řešení
Příklad 2: Kolik přímek je určeno 10 body, jestliže a) žádné tři z nich neleží v jedné přímce b) právě čtyři leží v jedné přímce řešení
Příklad 3: V rovině jsou dány dvě různé rovnoběžné přímky a, b. Na přímce a leží m různých bodů, na přímce b n různých bodů. Určete počet všech (nedegenerovaných) trojúhelníků, které mají tři vrcholy v uvedených bodech dvěma různými způsoby. řešení
Příklad 4: Kolika způsoby lze rozdat 52 karet mezi 4 hráče, aby a) v listu 1. hráče byla právě 4 srdce b) hráč č. 1 a 3 měli dohromady všechny krále řešení
Příklad 5: Ve třídě se vyučuje 11 předmětům. Kolik různých rozvrhů na pondělí je možné sestavit, když se v pondělí vyučuje 6 hodin a každý předmět může mít nejvýše jednu hodinu. řešení
Příklad 6: Karel má 4 knihy v češtině a 3 v angličtině a všechny mají název začínající na jiné písmeno. Kolika způsoby je může umístit do knihovny a) bez ladu b) tak, aby byly zleva nejprve knihy v češtině, a pak v angličtině c) tak, aby byly seřazeny podle abecedy řešení
Příklad 7: Do tanečního kurzu dochází 15 chlapců a 24 dívek. Kolik tanečních párů je možné sestavit? Určete dvěma způsoby. řešení
Příklad 8: V lavici je 5 žáků A,B,C,D,E. Kolika způsoby je můžeme přesadit a) vůbec b) A bude sedět na kraji c) B, C budou sedět vedle sebe d) C na kraji a A, D vedle sebe řešení
Příklad 9: Kolik má n-úhelník úhlopříček? n>3 řešení
Příklad 10: Kolika způsoby lze seřadit 10 lidí a) do řady, b) do kruhu? Kolika způsoby lze seřadit 5 chlapců a 5 dívek c) do řady d) do kruhu, aby vedle sebe nebyli dva jedinci stejného pohlaví? řešení
Příklad 11: a) Kolika způsoby lze vybrat 5 karet do listu z balíčku 52 karet? b) Kolika způsoby lze vybrat 5 karet stejné barvy z balíčku 52 karet? řešení
Příklad 12: Kolik čtyřciferných čísel menších než 4000 lze utvořit z cifer 1,3,5,7,9, nemají-li se cifry opakovat? řešení
Příklad 13: Kolika způsoby lze ze šachovnice vybrat 3 pole tak, aby neměla všechna tři stejnou barvu? řešení
Příklad 14: Na večírku při slavnostním přípitku si všech 10 přítomných přiťuklo každý s každým. Kolikrát zaznělo cinknutí skleniček? řešení
Příklad 15: Deset přátel si při odchodu na prázdniny slíbilo poslat vzájemně pohlednice z cest. Kolik pohlednic bylo celkem rozesláno? řešení
Následující příklady jsou taková upoutávka na to, co nás čeká v další kapitole. Pokuste se je vyřešit sami, ať máte být na co hrdí. V další kapitole najdete řešení na porovnání. Příklad 16: Město čtvercového půdorysu je vymezeno 5 ulicemi od jihu k severu a 6 ulicemi od západu na východ. Kolik cest existuje mezi jihozápadním rohem A a severovýchodním rohem B, smí-li se chodit jen na východ a na sever? Příklad 17: Kolika způsoby lze rozdělit 40 jablek mezi 3 děti?
Příklad 18: Aranžér má do výlohy umístit tři stejné svetry bílé, dva stejné svetry modré a čtyři stejné svetry červené. Pro svetry si vybral potřebných 9 míst. Kolika způsoby může svetry na tato místa umístit? ŘEŠENÍ Řešení příkladu 1: čísla jsou založena na pozičním systému, a tedy záleží na pořadí a) čtyřciferné číslo = čtyři pozice Aby vzniklo čtyřciferné číslo z cifer 1,2,3,4 větší než 3000, smí být na 1. místě jen 3 nebo 4; na ostatních místech je to jedno. Na 1. místě máme 2 možností na 2. místě už jen 3 možností, atd. 2.3.2.1 = 12 b) Záleží na pořadí a spotřebujeme všechny prvky, jde o permutace Všech možností jak uspořádat 4 prvky ze čtyř je P(4). Do tohoto počtu jsou zahrnuty i ta čísla, která začínají 1, což nevyhovuje zadání a musíme je odečíst. 1 na začátku představuje tolik trojciferných čísel, které se dají vytvořit ze tří cifer 2,3,4 a těch je P(3). Stejně musíme odečíst čtyřciferná čísla, která začínají na 2. Celkem jde tedy o P(4) – 2.P(3) = 4! – 2.3! = 12 čísel zpět Řešení příkladu 2: přímka je určena dvěma body a nezáleží na pořadí, jde o kombinace 10 a) K(2,10) = ( 2) = 45 b) čtyři body na jedné přímce vytvářejí stále jednu přímku, ale v předchozím případě jsou 4 započítány v počtu K(2,4) = ( 2) = 6 a musíme je odečíst; ale pozor, tu jednu, kterou vytvářejí, započítat musíme K(2,10) – K(2,4) + 1 = 45 – 6 + 1 = 40 zpět Řešení příkladu 3: trojúhelník je definován třemi nekolineárními (neleží na jedné přímce) body; nezáleží na pořadí, tedy jde o kombinace m+n
a) z (m+n) bodů lze vytvořit ( 3) trojúhelníků; ale některé z nich jsou degenerované (pouze úsečky, nejsou to trojúhelníky) a to vždy, když 3 body jsou vybrány pouze z přímky a, m n resp. b. Takových je na přímce a celkem ( 3) a na přímce b celkem ( 3). Celkem trojúhelníků dle zadání je
(m+n3) – (m3) – (n3)
b) Aby vznikl trojúhelník a ne jen úsečka, musíme vybírat jeden bod z přímky a a dva z b resp. jeden bod z přímky b a dva z a n jeden z přímky a je možné vybrat m způsoby a dva z přímky b ( 2) způsoby m
jeden z přímky b je možné vybrat n způsoby a dva z přímky a ( 2) způsoby za použití pravidla součinu a součtu dospějeme k výsledku n
m.( 2)
+ n.(m2)
Jde o vyjádření stejného počtu, tedy musí platit
(m+n3) – (m3) – (n3) = m.(n2) + n.(m2)
převeďme odčítání na druhou stranu rovnosti (m+n3) = (m3) + m.(n2) + n.(m2) + (n3) x x a užijme známé vlastnosti kombinačních čísel ( 0) = 1 a ( 1) = x; dostaneme tento vztah, který lze zobecnit z 3 na k
(m+n3) = (m0)(n3) + (m1)(n2) + (m2)(n1) + (m3)(n0) Je-li 0
k
m,n, pak platí
m n k
m n 0 k
m n 1 k 1
...
m
n k 1 1
m n k 0
zpět Řešení příkladu 4: karetní list: nezáleží na pořadí rozdání, kombinace; dále použijeme pravidla součinu; hráči jsou předem očíslováni, s těmi se již žádné záměny nedělají a)
1.hráč dostane 4 srdce ze 13 a z 39 nesrdcí zbývajících 9 karet (do 13) 2.hráč pak ze zbytku 39 karet svých 13 3.hráč ze zbytku 26 karet svých 13 4.hráč ze zbytku 13 karet svých 13
(134)(399) (3913) (2613) (1313) b)
vezmeme 4 krále ze 4 a k nim dalších 22 karet ze zbývajících 48 z této hromádky pak vybereme 1. hráči 13 karet z 26 a 3. hráči 13 z 13 a zbývajících 26 karet rozdáme mezi 2. a 4. hráče
(44)(4822) (2613)(1313) (2613)(1313) zpět
Řešení příkladu 5: vyučovací hodiny jsou uspořádány, 6 hodin a 11 předmětů, tedy jde o variace V(6,11) = 11.10.9.8.7.6 = 332 640
zpět Řešení příkladu 6: a) 7 rozlišitelných knih na 7 míst, záleží na pořadí, tedy permutace P(7) = 7! b) použijeme pravidlo součinu: v češtině P(4), v angličtině P(3), celkem P(4)P(3)=4!3! c) každý název začíná jiným písmenem, tím je uspřádání určeno => jediná možnost zpět Řešení příkladu 7: a) v tanečním páru na pozici pána máme 15 možností, na pozici dámy 24, celkem tedy 24.15 možností b) máme celkem 39 lidí; taneční pár představuje 2 lidi a nezáleží na pořadí (Anna+Karel je 39 týž pár jako Karel+Anna); z 39 lidí vybrat 2 je ( 2) možností, ale musíme odečíst páry stejného pohlaví, tedy
(392) – (242) – (152) = (241)(151) = 24.15 opět tu máme vztah
(15+242) = (150)(242) + (241)(151) + (152) (240) zpět Řešení příkladu 8: a) 5 žáků, 5 pozic, záleží na pořadí, permutace P(5) = 5! b) A může sedět vlevo nebo vpravo, když ho usadíme, zbývá 4 pozice na 4 žáky 2P(4)=2.4! c) žáky B a C můžeme posadit jako BC nebo CB, tedy 2 způsoby a dál s nimi můžeme pracovat jako s jedním prvkem: máme 4 žáky A, BC, D, E a 4 místa 2P(4)=2.4! d) žáka C můžeme posadit 2 způsoby, žáky A,D 2 způsoby vedle sebe a dál s nimi počítat jako s jedním prvkem, výsledek 2.2P(3) = 2.2.3! zpět Řešení příkladu 9: Spojnice dvou vrcholů n-úhelníka je buď úhlopříčka, nebo strana. Stran je celkem n. Vybereme-li 2 body z n vrcholů, nezáleží na pořadí, získáme všechny možné dvojice. Počet úhlopříček pak určuje rozdíl (n2) – n = n(n-3)/2 Odsud je známý vzorec počet úhlopříček je dán vzorcem n(n-3)/2. zpět
Řešení příkladu 10: a) 10 rozlišitelných lidí seřadíme do 10 místné řady (permutace) P(10)=10! b) Jestliže těchto 10 lidí (obecně n) posadíme ke kulatému stolu, je rozlišitelné pouze koho kdo má po levici a po pravici. Proto v řadě různá seřazení ABCDEFGHIJ, BCDEFGHIJA, EFGHIJABCD, atd v kruhu dávají jediné; těchto protočení (A zleva až nakonec vpravo, atd) je přesně tolik, kolik je účastníků tedy 10 (obecně n). Celkový počet způsobů seřazení do kruhu tedy je P(10)/10=10!/10=9! obecně P(n)/n=P(n-1)=(n-1)! c) Očíslujme si pozice v řadě od 1 do 10. Aby nikde nebyli vedle sebe dva chlapci či dvě dívky, zařídíme jednoduše tak, že budeme chlapce rozmisťovat na lichá (sudá) čísla a dívky na sudá (lichá) čísla – to představuje 2 možnosti. Umístit 5 chlapců (5 dívek) na 5 míst, záleží na pořadí, představuje permutaci P(5). Celkem možností jak uspořádat do řady 5 chlapců a 5 dívek aniž by spolu sousedilo stejné pohlaví je 2.P(5).P(5) = 2.5!.5! d) ad c) ale do kruhu; s odvoláním na ad b) je celkový počet možností ad c) děleno 10 2.P(5).P(5)/10 = 2.5!.5!/10 = 5!.4! zpět Řešení příkladu 11: Vybírat karty z balíčku karet do listu (tak se to obvykle myslí) nezáleží na pořadí a jde tedy o kombinace. 52 V prvním případě jde o K(5.52) = ( 5) v druhém případě vybíráme z karet stejné barvy, zato máme 4 možnosti jak stejnou barvu 13 zvolit 4.K(5,13) = 4.( 5) zpět Řešení příkladu 12: Jde o 4 místa z pěti prvků a záleží na uspořádání, variace. Buď uvažujeme, že na 1. pozici musí být jen číslice 1,3 a zbytek je už libovolný, nebo určíme všechny čtyřciferná čísla a odečteme ty, které začínají na 5,7,9. 2.V(3,4) = V(4,5) - 3.V(3,4) zpět Řešení příkladu 13: Vybrat ze šachovnice 3 pole => nezáleží na pořadí, tedy kombinace. Buď vybereme z bílých (z černých) polí jedno pole a z černých (z bílých) dvě pole, nebo budeme postupovat tak, že z celé šachovnice vybereme 3 pole a pak odečteme nevhodné výběry = všechny trojice stejné barvy 32
opět se objevuje známý vzorec
32
64
32
2.( 1)( 2) = ( 3) – 2.( 3)
rozepište sami
(32+323) = (320)(323) + … zpět
Řešení příkladu 14: Když si A ťukl s B, bylo to zároveň B s A. Nezáleží na pořadí, jde o kombinace (102) = 45 zpět Řešení příkladu 15: když A pošle pohlednici B není to totéž, jako B posílá A. Záleží na pořadí, variace. V(9,10) = 10.9 = 90 zpět KONEC
