28 Kombinatorika – met. Stručný přehled teorie Kombinatorika je součástí finitní matematiky, která studuje konečné soubory (množiny a uspořádané k-tice, k N). Kombinatorická pravidla Ø Kombinatorické pravidlo součinu Počet všech uspořádaných k-tic, jejichž první člen lze vybrat n[1] způsoby, druhý člen po výběru prvního n[2] způsoby, ....., k-tý člen po výběru všech předchozích n[k] způsoby, je roven číslu p, pro které platí : p = n[1 .] n[2 . … . ]n[k ] Ø Kombinatorické pravidlo součtu Jsou-li A[1 , ]A[2], ....., A[n ] konečné množiny, které mají po řadě p[1], p[2], ....., p[n] prvků, přičemž každé dvě z nich jsou disjunktní, pak platí: = p[1 ]+ p[2 ]+ … + p[n ] [ ] Skupiny,[ ]v nichž záleží na pořadí prvků[] Variace k-té třídy z n prvků bez opakování , - představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje nejvýše jednou (k, n N, k ≤ n). počet všech popsaných variací: V[(k, n)] = n.(n - 1).(n - 2). … . (n - k + 1) = Variace k-té třídy z n prvků s opakováním - představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje nejvýše k-krát (k, n N). počet všech popsaných variací: V´[(k, n) ]= n^k ^ Permutace z n prvků bez opakování = variace n-té třídy z n prvků bez opakování - představuje každou uspořádanou n-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje právě jednou. počet všech popsaných permutací: P[(n)] = V [(n, n)] = n.(n - 1).(n - 2). … .1 = n! Pozn.: n! …. čteme n faktoriál Permutace k prvků s opakováním z n prvků (k, n N, k > n) – představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý prvek vyskytuje aspoň jednou. Nechť se v uspořádané k-tici první prvek vyskytuje k[1]-krát, druhý prvek k[2]-krát, třetí prvek k[3]-krát, ......, n-tý prvek k[n]-krát. Přitom k = k[1]+k[2]+…+k[n.] počet všech popsaných permutací s opakováním: P´[k1, k2, ..., kn] (k) = Skupiny,[ ]v nichž nezáleží na pořadí prvků Kombinace k-té třídy z n prvků bez opakování - je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý z nich vyskytuje nejvýše jednou (k, n N, k ≤ n). počet všech popsaných kombinací: K[ (k, n) ]= = čteme „n nad k“ Kombinace k-té třídy z n prvků s opakováním - je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý z nich vyskytuje nejvýše k-krát. počet všech popsaných kombinací: K´[(k, n) ]= Pravidla pro práci s kombinačními čísly a faktoriály: Faktoriál n! Pro každé n přirozené: n! = n.(n - 1).(n - 2). ... .2.1 Pro n = 0 definujeme: 0! = 1 Kombinační číslo Pro všechna n, k celá nezáporná, k ≤ n : Některé základní vlastnosti kombinačních čísel: 1) 2) pro k ≤ n 3) pro k < n. Met.: Kombinatorika představuje relativně náročné téma, je však pro studenty zajímavá, hravá, pestrá. Učitel toho musí využít a dosáhnout u studentů co nejlepšího pochopení kombinatorických jevů a problémů a naučit je optimálním pohledům na kombinatorické úlohy a způsobům jejich řešení. Pokud by se mu to nepodařilo, měli by studenti potíže nejen s kombinatorikou, ale později i s mnoha dalšími oblastmi matematiky, do kterých ve větší či menší míře kombinatorika zasahuje (např. Pravděpodobnost, …). Úvod kombinatoriky by měl rozhodně patřit kapitole o faktoriálech a kombinačních číslech. Studenti by měli být důkladně seznámeni s oběma těmito matematickými objekty, jejich nadefinováním, podmínkami jejich existence, pravidly pro počítání s nimi, měli by dokonale zvládat středoškolskou úroveň úprav výrazů, důkazů rovností i řešení rovnic a nerovnic s faktoriály a kombinačními čísly. Až budou řešit např. slovní kombinatorické úlohy, musí už mít faktoriály a kombinační čísla „v malíčku“. Řada kombinatorických úloh potřebuje k řešení znalost dvou základních pravidel, tedy kombinatorického pravidla součtu a kombinatorického pravidla součinu. Jakmile učitel s těmito pravidly studenty seznámí, měl by zařadit několik jednoduchých úloh, díky kterým studenti jejich podstatu lépe pochopí: Př. V první restauraci nabízejí 3 druhy polévek, 8 druhů hlavních jídel a 4 druhy nápojů. Ve druhé restauraci mají jen 2 druhy polévek, ale 10 druhů hlavních jídel a 5 druhů nápojů. Kolika způsoby si host může vybrat oběd za předpokladu, že a) zvolil první restauraci a bude jíst hlavní jídlo a nápoj? b) zvolil první restauraci a bude jíst polévku, hlavní jídlo a nápoj? c) bude vybírat restauraci a jíst polévku, hlavní jídlo a nápoj? Řeš.: a) hlavní jídlo … 8 možností, nápoj … 4 možnosti počet všech možností (kombinatorické pravidlo součinu) … 8.4 = 32 b) polévka … 3 možnosti, hlavní jídlo … 8 možností, nápoj … 4 možnosti počet všech možností (kombinatorické pravidlo součinu) … 3.8.4 = 96 c) první restaurace … 3.8.4 = 96 možností druhá restaurace … 2.10.5 = 100 možností počet všech možností (kombinatorické pravidlo součtu) … 96 + 100 = 196 Učitel musí k výuce přistupovat se stálým vědomím toho, že kombinatorika studuje dva typy konečných souborů, které jsou principiálně odlišné: ● uspořádané k-tice, k N, v nichž záleží na pořadí prvků, ● množiny, ve kterých na pořadí prvků nezáleží. Učitel musí především naučit studenty spolehlivě rozpoznat, s kterým z uvedených dvou typů souborů mají v zadané kombinatorické úloze pracovat. Zkušenosti ukazují, že to některým studentům dělá občas potíže. Pozn.: Studentům je dobré poradit, aby si ze zadaných prvků vytvořili třeba trojici, pak v ní vyměnili pořadí prvků a promysleli si, zda jde o tutéž trojici nebo o trojici jinou: Př.1: Nechť jsou Adam, Bedřich a Cyril tři studenti. Vytvořme z nich trojici pro a) službu ve třídě: b) první tři místa v soutěži: Př.2: Tóny c, e, g zahrané a) najednou (souzvuk) na klavír: b) postupně na trubku (jako souzvuk nelze): . Vzorce, kterých je kombinatorika plná, si studenti jistě lépe zapamatují, když je jimi učitel nezasype, ale ukáže jim, jak se odvozují. Navíc, a to je jistě ještě mnohem důležitější, tak studenti uvidí další příklad toho, jak se matematika buduje a tvoří. Vzorce je třeba dokázat matematickou indukcí (některé – podle času). 1. Konečné soubory prvků, ve kterých záleží na pořadí prvků – variace, – variace s opakováním, – permutace, – permutace s opakováním 1 2 3 4 5 x 12 13 14 15 21 x 23 24 25 31 32 x 34 35 41 42 43 x 45 51 52 53 54 x 231 234 235 z každé uspořádané dvojice se vytvoří 3 uspořádané trojice 521 523 524 ……….. ① Variace k-té třídy z n prvků (prvky se nesmí opakovat) Textové pole: Zobecnění: M={1,2,3,…,n} V_((1,n) )=n V_((2,n) )=n.(n-1) V_((3,n) )=n.(n-1).(n-2) ………….. V_((k,n) )=n.(n-1).(n-2).….(n-k+1)=(n.(n-1).(n-2).….(n-k+1).(n-k).….3.2.1)/((n-k).….3.2.1)=n!/(n-k)! ② Variace k-té třídy z n prvků s opakováním 1 2 3 4 5 11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 41 42 43 44 45 51 52 53 54 55 231 232 233 234 235 z každé uspořádané dvojice se vytvoří 5 uspořádaných trojic 521 522 523 524 525 ……….. Zobecnění: ………….. ③ Permutace z n prvků (prvky se nesmí opakovat) Permutace z n prvků = variace k-té třídy z n prvků: ④ Permutace s opakováním V této množině je k[1] = 4 prvků typu x a k[2] = 3 prvků typu y, tedy celkem k = k[1] + k[2] = 7 prvků. Počet permutací (bez opakování) z těchto prvků je . Jedna z těchto permutací je např. . Kdybychom z této permutace tvořili další tak, že bychom všechny prvky typu y nechali na „svých“ místech a „promíchávali“ bychom pouze prvky typu x, získali bychom spolu s původní celkem 4! permutací. Ty všechny by ovšem splynuly v jedinou permutaci v okamžiku, kdy bychom přestali rozlišovat prvky typu x, tj. zavedli bychom . Množina M by se změnila na , vybraná permutace by se změnila na a počet permutací (teď už s opakováním prvku x) by se změnil na . Když přestaneme rozlišovat navíc i prvky typu y, bude a počet permutací s opakováním bude Textové pole: Zobecnění: M={x,…,x,y,…,y,……,z,…,z} Přitom k_1+k_2+⋯+k_n=k. Počet všech permutací s opakováním z prvků množiny M je P_(k_(1,) k_2,…,k_n)^´ (k)=k!/(k_1 !.k_2 !.….k_n !) 2. Konečné soubory prvků, ve kterých nezáleží na pořadí prvků – kombinace, – kombinace s opakováním ① Kombinace k-té třídy z n prvků (prvky se nesmí opakovat) Textové pole: M={1,2,3,4,5} Vytvořme variace 3. třídy z těchto pěti prvků. Je jich V_((3,5) )= 5!/(5-3)! . Uvědomme si, že např. 123, 132, 213, 231, 312, 321 představuje 3! = 6 různých variací, ale jedinou kombinaci třetí třídy z pěti prvků. Podobně každých 3! variací vytvořených „promícháním“ každé trojice prvků množiny M představuje jedinou kombinaci. Proto K_((3,5) )=V_((3,5) )/3!=5!/(5-3)!.3! . Textové pole: Zobecnění: M={1,2,3,…,n} K_((k,n) )=V_((k,n) )/k!=n!/((n-k)!.k!)=(■(n@k)) Pozn.: … Skutečnost, že v čitateli i jmenovateli posledního zlomku je stejný počet činitelů, umožňuje velmi zjednodušit výpočet kombinačních čísel: Např.: 1) místo ; 2) …. využití pravidla ② Kombinace k-té třídy z n prvků s opakováním Aby učitel dosáhl pochopení tvorby kombinací s opakováním u co největšího počtu studentů, měl by jim na začátku ukázat několik konkrétních příkladů: Př.: Nechť . Vypište několik kombinací s opakováním páté třídy ze tří prvků množiny M a pokuste se zjistit, kolik takových kombinací existuje. Řeš.: ……. Jak zjistit počet všech možných kombinací s opakováním páté třídy ze tří prvků? 1. způsob …. Použít vzorec , tedy 2. způsob …. Využít skutečnosti, že každou kombinaci s opakováním lze jednoduše převést na permutaci s opakováním. V případě tří prvků stačí vytvořit prostor s dvěma oddělovači (oddělovačů je vždy o jeden méně než prvků – viz obrázek). Pak zvolíme dva grafické znaky: – první pro oddělovač …. např. │ – druhý jako značku registrující přítomnost prvku v „jeho“ prostoru …. např. • Je evidentní, že všechny kombinace s opakováním páté třídy ze tří prvků dokážeme zobrazit pomocí pouhých dvou druhů znaků: pět modrých teček odpovídá pěti použitým prvkům (páté třídě), dvě červené rysky představují dva potřebné oddělovače). Zároveň je jasné, že na pořadí těchto znaků záleží. Proto musíme pracovat s permutacemi s opakováním: Tento druhý způsob řešení úlohy je jednoduchý, srozumitelný a logický, takže jej studenti mohou používat vždy, když hledají počet kombinací s opakováním, a to aniž by si museli pamatovat nepříjemný vzorec. Navíc díky němu může učitel studentům ukázat, jak lze ke vzorci dojít: . Základní poznatky: Poznámka: Ve výsledcích příkladů 2 – 6 této části uveďte také druh kombinatorické skupiny, kterou příklad procvičuje. 1) MA 2017 Čtyřciferné přirozené číslo se má sestavit ze čtyř různých číslic. Na prvním místě má být číslice 2 a na místě desítek lichá číslice. (Daným podmínkám vyhovují např. čísla 2 430 a 2 793.) Kolik různých čísel je možné uvedeným způsobem sestavit? a) 21 b) 240 c) 280 d) 360 e) jiný počet [C] 2) Je dána množina M = {1, 2, 3, 4, 5}. a) Kolik trojciferných čísel, v nichž se neopakují cifry, lze vytvořit z jejich prvků? [60, variace 3. třídy z 5 prvků bez opakování] b) Kolik z nich je dělitelných pěti? [12, variace bez opakování] c) Kolik pěticiferných čísel bez opakování číslic lze vytvořit z prvků množiny M? [120, permutace z 5 prvků (bez opakování) nebo variace 5. třídy z 5 prvků bez opakování] Met.: Učitel by měl ukázat studentům dva způsoby řešení a nechat na studentech, který z nich si vyberou, až budou psát prověrku: 1. způsob: užitím vzorců a) ; b) Poslední cifra musí být 5, obsazujeme tedy jen první dvě pozice v čísle a nesmíme už použít 5 … ; c) 2. způsob: užitím kombinatorického pravidla součinu: Textové pole: 5 možností → Textové pole: 4 možnosti → Textové pole: 3 možnosti → Textové pole: 4 možnosti→ Textové pole: 3 možnosti → Textové pole: 1 možnost → Textové pole: 5 možností → Textové pole: 4 možnosti → Textové pole: 3 možnosti → Textové pole: 2 možnosti → Textové pole: 1 možnost → Pozn.: Zadání úlohy by měl učitel ještě zkomplikovat tím, že mezi prvky množiny M zařadí nulu. Pak může být např. . Předchozí výpočet je potom třeba doplnit o vyřazení všech trojic, které mají nulu na prvním místě. Úlohu lze nejprve využít jako prémiovou úlohu, jejíž správné řešení může učitel odměnit … 3) Řešte úlohu č. 2 pro případ, kdy se cifry mohou opakovat. [a) 125, variace 3. třídy z 5 prvků s opakováním b) 25, variace s opakováním c) 3125, variace 5. třídy z 5 prvků s opakováním] 4) Kolik existuje osmiciferných čísel, ve kterých jsou 3 dvojky, 1 pětka a 4 šestky? [280, 8 členné permutace s opakováním typu P´[3,1,4](8)] 5) Kolik existuje tříprvkových podmnožin množiny M? [10, kombinace 3. třídy z 5 prvků bez opakování] 6) Student psal v matematice během pololetí 7 písemných prací a známky na konci pololetí uspořádal od nejlepších po nejhorší, např. 1, 1, 2, 3, 3, 4, 5. Kolik různých výsledků mohl student získat? [330, kombinace 7. třídy z 5 prvků s opakováním] 7) Vyjádřete jedním kombinačním číslem: a) b) [a) b) ] Typové příklady standardní náročnosti 8) MA 2016 Je dána rovnice s neznámou n N: Jaké je řešení rovnice? A) 11 B) 10 C) 9 D) 8 E) jiné řešení [A] 9) Kolik přímek je určeno 12 body, jestliže: a) žádné tři body neleží na přímce? b) čtyři z nich leží na přímce? [66, 61] 10) S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete počet: a) všech možných pořadí jejich vystoupení. b) všech možných pořadí jejich vystoupení, v nichž vystupuje A po E. c) všech možných pořadí jejich vystoupení, v nichž vystupuje A ihned po E [720, 360, 120] 11) MA 2014 Trenér vybírá z 5 děvčat a 4 chlapců šestičlennou skupinu, v níž budou 3 dívky a 3 chlapci. Kolika způsoby lze šestičlennou skupinu za těchto podmínek sestavit? A) 16 B) 20 C) 40 D) 180 E) jiným počtem [C] 12) V sérii 12 výrobků jsou 3 vadné. Kolika způsoby lze z nich vybrat 6 výrobků, z nichž právě 2 jsou vadné? [378] 13) a) Z kolika prvků lze vytvořit 600 variací druhé třídy bez opakování? [25] b) Kolik prvků dává 55 kombinací 2. třídy bez opakování? [11] 14) a) Upravte a určete podmínky pro n: [ ] b) Řešte v Z: [5] 15) Řešte rovnici a nerovnici: a) b) < 72 [a) {5}, b) {8, 9}] Rozšiřující cvičení 16) V novinovém stánku lze koupit 10 druhů pohledů, přičemž každý druh je k dispozici v 50 exemplářích. Určete, kolika způsoby lze zakoupit: a) 15 pohledů b) 51 pohledů c) 8 různých pohledů [1 307 504; K´(51, 10) - 10; 45]