Diskrétní matematika (MA0002)
Kombinatorika: Základní kombinatorická pravidla.
Odvození kombinatorických vzorců: Permutace, variace, kombinace bez opakování a s opakováním.
Faktoriály a kombinační čísla. Binomická věta. Princip inkluze a exkluze a další kombinatorické lahůdky.
Konečné součty.
Dělitelnost celých čísel. Základní věta aritmetiky.
Dělitelnost polynomů. Hledání kořenů polynomu. Dělení polynomu polynomem. Euklidův algoritmus.
Základy teorie grafů.
Studijní text PdF MU - verze ze dne 13. října 2020 Helena Durnová Pracovní verze
Obsah
I   Teorie a příklady k procvičení 3
1 Kombinatorika 4
1.1 Základní kombinatorická pravidla................ 4
1.2 Faktoriály a kombinační čísla. Kombinatorické identity. .... 6
1.3 Aritmetický (Pascalův) trojúhelník............... 8
1.4 Odvození vzorců: variace, permutace, kombinace (bez opakování)................................ 9
1.5 Další úlohy............................ 12
1.6 Binomická věta.......................... 12
1.7 Princip inkluze a exkluze..................... 13
1.8 Problém šatnářky (speciální princip inkluze a exkluze)  .... 16
1.9 Další typy kombinatorických úloh................ 16
1.10 Kompozice a rozklady....................... 16
1.11 Rozdělování do přihrádek..................... 17
1.12 Závěrem ke kombinatorice..................... 17
2 Rekurentní vztahy. Konečné součty. 18
2.1 Fibonacciho posloupnost..................... 18
2.2 Aritmetická posloupnost...................... 18
2.3 Geometrická posloupnost..................... 19
3 Základy elementární teorie čísel 20
3.1 Znaky dělitelnosti (známe často ze ZS)............. 21
3.2 Eukleidův algoritmus....................... 22
3.3 Prvočísla a čísla složená. Základní věta aritmetiky....... 23
3.4 Úlohy na zbytkové třídy (důkazy)................ 23
4 Dělitelnost polynomu. Hledání kořenů polynomu. 24
5 Základy teorie grafů 25
1
Předmluva
Motto:
„Nevyučuj toho, kdo není připraven, aby byl vyučován."
(Jan Ámos Komenský)
Matematika provází všechny děti po celou základní školní docházku od 70. let 20. století pod tímto jménem a pod jmény jinými (počty a měřictví, či aritmetika a geometrie) ještě déle. Některé děti matematika prostě baví, některé ne, ale přesto se jí musí učit všechny, stejně jako třeba češtině či tělocviku.
V dnešní době se stalo módou chlubit se neznalostí matematiky, začněme tedy kacířskou otázkou: co by se stalo, kdybychom děti, které matematické poznatky přirozeně nechápou, povinnosti učit se matematiku zprostili? Odpovědět na ni dokážeme teprve tehdy, když si uvědomíme, jaké učitele matematiky jsme zažili a co od nás matematika vyžadovala.
Matematika se dá — s velkou nadsázkou — přirovnat ke sportu. Ani ve sportu není talent všechno; skoro u každého je potřeba trénink. Tak je tomu i s matematikou: během školní docházky se v matematice učíme postupům, které nám procvičováním přejdou do krve. A tak si při při písemném sčítání „sloupečků" i v dospělosti pomáháme prsty. Pravda, příležitostí k využití této dovednosti máme díky přítomnosti kalkulačky ve všudypřítomných mobilních telefonech pramálo, ale když bylo vynalezeno auto, také jsme nepřestali chodit pěšky a jezdit na kole.
Ve výuce matematiky se často klade důraz na správný zápis, na to, aby byl výsledek dvakrát podtržen, na to, aby znaménko rovnosti bylo v úrovni hlavní zlomkové čáry složeného zlomku. Všechny tyto věci se zvenčí mohou zdát podružnými a nepodstatnými, ale právě tyto návyky nás učí odlišovat podstatné od nepodstatného: vezměme si jako příklad pomocné výpočty psané tužkou na okraj sešitu nebo dokonce na šmírák. Podobně důraz na úpravu a dodržování pravidel není samoúčelný, nýbrž nám samotným později ve složitějších výpočtech usnadní orientaci. Během hodin matematiky se tak cvičíme v disciplíně, učíme se odlišovat podstatné od nepodstatného.
Na závěr dovolte několik vět k předkládanému textu. Je věnován některým partiím z tzv. diskrétní matematiky, zde konkrétně z teorie čísel, kombinatoriky a teorie grafů a je koncipován spíše jako vodítko k Vaší orientaci. Všechny partie zde probírané byly již popsány v řadě knih, na něž se v textu odkazujeme. Nepochopíte-li vše hned, nezoufejte a mějte na paměti, že vše lze pochopit, vyvinete-li dostatečné úsilí. Matematika je také práce.
2
Část I
Teorie a příklady k procvičení
3
Kapitola 1
Kombinatorika
Řada knih zabývajících se kombinatorikou a jejími počátky poukazuje na zálibu lidí v přeskupování a vytváření vzorů. Athanasius Kircher (1602-1680) v ní viděl největší umění a svou knihu věnovanou kombinatorice nazval Ars Magna Sciendum, Sive Combinatoria (Velké umění vědecké, neboli kombinatorika). Pro malé počty prvků jsou kombinatorické úlohy jsou pro malé počty prvků snadno řešitelné jednoduchým způsobem, totiž vypsáním všech možností. Při větším počtu však působí spíše magickým dojmem, protože vypsat všechny možnosti by trvalo příliš dlouho. Nicméně i když není v našich silách všechny možnosti vypsat, stojí za to se o to pokusit. Začneme-li totiž možnosti systematicky vypisovat, může nám to pomoci uvidět, jak budeme počítat. Toto umění vidět může působit jako magie, ale dá se docela dobře nacvičit, podobně jako si člověk zvykne číst rukopis jiného člověka nebo se naučí rozeznat jednoho brouka od jiného.
1.1   Základní kombinatorická pravidla
Kombinatorické výpočty se zakládají na několika jednoduchých pravidlech. Uveďme si je v moderním množinovém vyjádření, neboť je stručné a jednoznačné.1
Věta 1.1 (Pravidlo součtu) Nechť A, B jsou množiny, A n B = 0. Pak \AUB\ = \A\ + \B\.
Příklad 1.2 Na otázku „kolika způsoby lze na šachovnici postavit pěšáka?" lze odpovědět také rozdělením šachovnice na černá a bílá políčka. Pro variantu, jak postavit pěšáka na bílé políčko, máme 32 možností; pro variantu, kdy pěšák stojí na černém políčku, máme také 32 možností. Celkem je možností 64 = 32 + 32 (stojí-li pěšák na černém políčku, nestojí na bílém, a naopak).
Věta 1.3 (Pravidlo součinu) Nechť A, B jsou neprázdné množiny. Pak \A x B\ = \A\ ■ \B\.
Příklad 1.4 Ptáme-li se, kolika způsoby můžeme postavit na šachovnici černou a bílou dámu tak, aby černá dáma stála na černém políčku a bílá na bílém, odpověď určíme jako 32 • 32 = 1 024
xO základech teorie množin se dozvíte v předmětu Základy matematiky.
4
V následujícím příkladu zkombinujeme pravidlo součtu a součinu:
Příklad 1.5 Kolik různých slov vznikne přeházením písmen slova KOLENA tak, že se v nich samohlásky a souhlásky střídají a souhlásky jsou seřazeny abecedně?
Pokud jsou souhlásky na sudých pozicích a samohlásky na lichých, můžeme takto získat 6 slov (6 = 3! = 3- 2- l)a stejně slov získáme i tehdy, jsou-li souhlásky na lichých pozicích a samohlásky na sudých [užili jsme pravidlo součinu]. Celkem je možností 12 = 6 + 6, neboť pokud jsou souhlásky na sudých místech, nejsou na lichých místech a naopak [užili jsme pravidlo součinu].
Věta 1.6 (Přihrádkový, též zvaný Dirichletův, princip) Máme-li rozdělit n + 1 předmětů do n přihrádek, pak při libovolném rozdělení budou v alespoň jedné přihrádce alespoň dva předměty.
Příklad 1.7 V zásuvce je 12 párů červených a 12 párů modrých ponožek. Pokud bereme ponožky z přihrádky poslepu, kolik ponožek musíme vzít, abychom měli alespoň dvě ponožky téže barvy?
[Stačí vytáhnout tři ponožky.]
Všechny kombinatorické vzorce, které znáte ze střední školy, se dají odvodit pomocí pravidla součtu a pravidla součinu. Přihrádkový (Dirichletův) princip lze s výhodou použít při řešení některých příkladů.
Několik postřehů z historie kombinatoriky.
Kombinatorická pravidla jsou tak jednoduchá a samozřejmá, že těžko můžeme očekávat, že bychom v historických pramenech našli zmínky o jejich přesné formulaci.2 Zmínky o úlohách, které bychom dnes klasifikovali jako kombinatorické, nacházíme především v indických a čínských textech. První zmínky se však objevují již ve starověkém Egyptě, jak dokládá následující
úloha z Rhindova papyru s poměrně nejasným zadáním. Obsahuje sloupec (viz též ??)
domy 7
kočky 49
myši 343
pšenice 2401
hekaty 6807 19607
Podobné počty najdeme i u Fibonnacciho {Liber abaci, 1202) ve formě říkanky o sedmi starých ženách, které jdou do Říma:
Sedm starých žen šlo do Říma
každá nesla.....
Kolik....
Tyto počty se dochovaly i v dětské říkance „Když jsem šel do St. Ives": 2Biggs, N. 1979. 'Roots of combinatorics'. História Mathematica 6:109-136.
5
R79
Majetek:
domy kocky
49
1
2 801
myši
343
5 602
pšenice
2 301
SÍC
4
11204
ječmen celkem
16 807
celkem
19 G07
19 607
Obrázek 1.1: Úloha o majetku z Rhindova papyru. Převzato z knihy Vyma-zalová, Hana. Hieratické texty.
As I was going to St. Ives,
I met a man with seven wives.
Each wife had seven sacks.
In each sack there were seven cats.
Each cat had seven kits.
Kits, cats, sacks, and wives,
How many were going to St. Ives?
Mezi staré kombinatorické úlohy patří také počítání kombinací chutí nebo možnosti otevřených a zavřených dveří ( Lílavátí). Kombinatorické výpočty se obejvují také v úvahách o hazardních hrách (Huygens, Pascal, Fermat). Kombinatorická pravidla tak, jak je známe dnes, sepsal Jacob Bernoulli ve spise Uměni odhadu (Ars conjectandi), vydané v roce 1713.
1.2   Faktoriály a kombinační čísla. Kombinatorické identity.
V tomto oddíle stručně shrneme některé poznatky o faktoriálech a kombinačních číslech tak, abychom s nimi v dalším mohli počítat bez dalšího vysvětlování. Funkci faktoriál definujeme pouze pro přirozená čísla:
Definice 1.8 (Faktoriál přirozeného čísla) Pro libovolné n e N klademe n\ = 1 • 2.....n (čteme: „n faktoriál").
Dále klademe 0! = 1. Na okraj uveďme, že pojem faktoriálu lze rozšířit i mimo obor přirozených čísel; podobně i níže zmíněný pojem kombinačního čísla:
Definice 1.9 (Kombinační číslo) Pro libovolná k, n 6 N definujeme kombinační číslo takto:
(čteme: „n nad k").
6
Tabulka hodnot faktoriálů:
0!	1
1!	1
2!	2
3!	6
4!	24
5!	120
6!	720
7!	5 040
8!	40 320
9!	362 880
10!	3 628 800
Počítání s faktoriály a kombinačními čísly: Jednodušší příklady lze řešit rozepsáním faktoriálů. Kombinační číslo (£) představuje vlastně stručný zápis zlomku feT(^fc)T, Platí tedy: Q) = (nn_k).
Kombinatorické identity: pro kombinační čísla platí řada tzv. kombinatorických identit. Lze je dokázat jednak rozepsáním jednotlivých kombinačních čísel, jednak kombinatorickou úvahou. Nejznámější z nich je tato:
n\ In k) + \k + l
'n + ť vfc + ly
Lze ji jednoduše ověřit rozepsáním kombinačních čísel. Také si můžeme uvědomit, že vybíráme-li např. tři osoby ze sedmi, je z početního hlediska jedno zda počítáme trojice těch, kteří nás budou reprezentovat, nebo naopak čtveřice těch, kteří "zůstanou doma".
Uveďme některé další typy jednoduchých příkladů na toto téma::
(a) Dokažte: n! + [n — l)!n2 = (n + 1)! (Stačí na levé straně vytknout n!.)
(b) Sečtěte: - 2^ + ^ [=2]
(c) Vyjádřete jedním kombinačním číslem: (^) + (jj) ^(g0)]; (j1) + (g1)
[=(?)]; (S + fi?) [=(?)]•
Dále platí tyto jednoduché kombinatorické identity:
(Í)  (2) = (n-J
00 (E) = E) + (m) 2- = (s) + (?) + G) +
(iv) o = (s) - (?) + (;)-■
(v) (V)+(ľ)+rí1)+• • •+rr1) - +ra
(vi) o + m+r:2)+• • •+m=+rr)
(vii) l + 2 + --- + m=
(viii) l-2 + 2- 3 + 3- 4 + -- - + m-(m + l) = m(m+13)(m+2)
• + (n-l) + O
+ (-l)n-1(n-l) + (-l)nO
7
(ix) l-2-2 + 2-3-4 + 3-4-5 + --- + m-(m + l)-(m + 2) = m(m+1)(T^+2)(m+3)
w (o) o - (i) Ľ-\)+(2) Ľ-D+-+(-i)-a m=O
Jednoduchou úvahou z platnosti identity (iii) vyplývá platnost následujících identit pro sudé n:
(iii-a) 2-1 = (S) + (5) + (S) + ■ ■ • + O (iii-b) 2-1 = (?) +     +     + (n^)
a analogicky pro liché n:
(ih-c) 2-1 = (s) + (;) + (;) + ...+ j (ih-d) 2-1 = (?) + (;) + £) + ... + o
Dále platí například:
(*) 4" = (2"0+1) + ('V') + ('V') + ('V1) + • • • + (2nn+1)
Rada vztahů mezi kombinačními čísly je patrná z tzv. Pascalova (též aritmetického) trojúhelníka.
1.3   Aritmetický (Pascalův) trojúhelník
Kombinační čísla nalezneme i v tzv. aritmetickém (Pascalově) trojúhelníku. Každý jeho následující řádek vznikne tak, že do mezery mezi čísly předchozího řádku vepíšeme součty dvou čísel nad tímto místem. Postup je zřejmý z obrázku 1.2.
A
ALA A  A   3 , A A k £>    4 A
/\  b 10 io  A ^
Obrázek 1.2: Aritmetický trojúhelník
V aritmetickém trojúhelníku lze nalézt řadu vztahů mezi kombinačními čísly. Známá identita (£) + (fc^) = ("+1) se používá přímo při vytváření trojúhelníka. Z toho, jak schéma vzniklo, se také lehce dá odvodit, že součet čísel v daném řádku je dvojnásobkem součtu čísel v řádku předchozím, neboť každé číslo předchozího řádku vstupuje jako sčítanec do dvou čísel v řádku daném. Vztah naznačený na obrázku 1.3 můžete zkusit odhalit sami.
8
A   - 1 -1°
[5]
Obrázek 1.3: Aritmetický trojúhelník: některé vztahy
Rovnice s kombinačními čísly Cvičení 1.10 Najděte všechna x£N, pro něž platí:
:> (:::)-
Cvičení 1.11 Určete, pro jaká m, n G N platí:
n + 1\ _ /n + 1\ _ 5 /m + 1\ m + l/V m /     3 \m - 1/
[n = 6, m = 3]
1.4   Odvození vzorců: variace, permutace, kombinace (bez opakování).
V následujícím odvodíme pomocí pravidla součtu a součinu vzorce, které znáte ze střední školy pod názvy variace, permutace a kombinace (bez opakování a s opakováním). Postup vysvětlíme vždy na nějakém příkladu.
Variace bez opakování:
Příklad 1.12 Kolika způsoby lze na šachovnici rozestavit dámu, krále a věž? Řešení: Opakovaným použitím pravidla součinu: 64 • 63 ■ 62 — 249 984
Obecně pokud vybíráme k předmětů z celkového počtu n předmětů, přičemž k, n G N a k < n, možností je
n!
n.(n-l).(n-2).....(n - k + 1) = ^—^
9
Permutace bez opakování jsou zvláštním případem variací pro n = k. Někdy mluvíme také o pořadí.
Příklad 1.13 Kolika způsoby lze sestavit devítimístné číslo z cifer 1 až 9 takové, že se v něm cifry neopakují?
Řešení: Opakovaným použitím pravidla součinu: 9-8.....        1 = 362 880
Obecně je počet pořadí n prvků roven n! (n € N)
Příklad 1.14 Určete součet všech čtyřciferných čísel sestavených z cifer 1,2,3,4.
Řešení: 640 + 6400 + 64000 + 640000 (číslice se mohou opakovat); 60 + 600 + 6000 + 60000 (číslice se nemohou opakovat).
Kombinace bez opakování: uvědomíme si, že množství stejně početných variací a kombinací bez opakování prvků vybíraných ze stejně velké množiny spolu úzce souvisí. V podstatě stačí počet variací vhodným číslem vydělit; tímto vhodným číslem je faktoriál počtu vybíraných prvků; tj.
n!
(n- k)\k\
To je právě kombinační číslo:
(n\ n\ k) = (n-k)\k\
Příklad 1.15 Kolika způsoby lze na šachovnici rozestavit tři bílé pěšáky?
Řešení: Vyjdeme z příkladu, kdy jsme na šachovnici měli postavit krále, dámu a věž; možností bylo 64-63-62 — 249 984, Je zřejmé, že pokud na tři daná políčka postavíme tři pěšáky, je možnost jediná (pěšáci jsou stejní), zatímco krále, dámu a věž na tatáž políčka postavíme 3-2-1 = 6 způsoby.
U variant „s opakováním" začneme s odvozováním vzorců také u variací. Variace s opakováním
Příklad 1.16 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla. Kolika způsoby si mohou objednat?
Řešení: Každý z hostů má 4 možnosti, tedy 4-4-4-4-4-4-4-4-4-4-4-4 = 4*2 možností.
Podobným způsobem lze odvodit počet podmnožin množiny Aon prvcích:
2\A\ = 2n
10
Permutace s opakováním  tentokrát nejsou zvláštním případem variací.
Příklad 1.17 Kolika způsoby můžeme přeskládat písmena slova
(a) TATA
(b) POPOCATEPETL Řešení:
(a) Vypíšeme možnosti dle abecedy: A ATT, ATT A, AT AT, T A AT, TATA, TTAA. To odpovídá permutacím všech čtyř písmen vyděleným permutacemi opakujících se písmen, tj.
(b) Analogicky slovo POPOCATEPETL má 3 P, 2 0, 2 T, 2 E, 1 A, 1 C 1 L, tj. dohromady 12 písmen a možností přeházení je tedy 3J2!2!2!i!i!i!
Každý z hostů má 4 možnosti, tedy 4-4-4-4-4-4-4-4-4-4-4-4 = 4*2 možností.
Kombinace s opakováním vyžadují zvláštní přístup. Začneme „kódovat" a sestrojovat bijekce (vzájemně jednoznačná zobrazení) mezi objekty, jejichž počet máme spočítat, a objekty, jejichž počet budeme umět spočítat.
Příklad 1.18 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla. Kolika může být objednávek z hlediska kuchaře?
Řešení: Kuchaři je jedno, kdo si objednal které jídlo, zajímá ho pouze, kolik má připravit porcí jídla č. 1 až 4- Možností je (12^ľ4^_1) = (12~i2_1)
Příklad 1.19 Kolika způsoby mohu vybrat deset mincí v hodnotě 5, 10 a 20 Kč? (Máme dostatečný počet mincí každé hodnoty.) Řešení: Možností je (^f1) = (10to_1) = 66
Oba výše uvedené případy můžeme „zakódovat" pomocí nul a jedniček. V příkladě s mincemi si například můžeme představit, že mince uspořádáme podle hodnoty: nejprve dvacetikoruny, pak desetikoruny a nakonec pětikoruny. Místo dvacetikorun napíšeme do řádku příslušný počet jedniček; za ně napíšeme nulu. Pokračujeme tak, že zapíšeme tolik jedniček, kolik je desetikorun; za ně opět napíšeme nulu. Nakonec napíšeme tolik jedniček, kolik je pětikorun. Je zřejmé, že psát za nimi nulu je nadbytečné: pokud hromádka dvaceti-, deseti- a pětikorun splňuje zadání a obsahuje deset mincí, napsali jsme posud deset jedniček a dvě nuly. Je zřejmé, že mezi hromádkami mincí a permutacemi deseti jedniček a dvou nul existuje vzájemně jednoznačné zobrazení, neboli vyhovujících hromádek je právě tolik, kolik je permutací deseti jedniček a dvou nul. Ty však již umíme spočítat: jedná se o předchozí výsledek, který jsme nazvali permutace s opakováním (deseti jedniček a dvou nul).
Výše uvedené odvození můžeme zopakovat při řešení jednotlivých příkladů; je to spolehlivější než snaha dosazovat naslepo do vzorečku pro kombinace s opakováním, kdy vybíráme k prvků n druhů:
n tu   \     (k + n~1\     (k + n-l\
11
Vzoreček pro kombinace s opakováním, v němž přehodíme značení pro druhy a počet prvků ,a tedy vybíráme n prvků k druhů, totiž vypadá dost podobně:
fn + k-l\     fn + k-l\
1.5 Další úlohy
Nyní si ukážeme několik zajímavých příkladů, u kterých vhodně využijeme výše uvedené vzorce a pravidla. Jsou převzaty z jiných učebnic, zejména z výborných skript Antonína Vrby.
Příklad 1.20 Kolika způsoby lze přeskládat písmena slova LOKOMOTIVA tak, aby žádná dvě „O" nestála vedle sebe?
Řešení: Nejprve určíme, kolika způsoby lze přeskládat písmena L, K, M, T, I, V, A. To lze provést 7! způsoby. Při libovolném z těchto rozložení máme posloupnost sedmi písmen. Abychom vyhověli podmínkám, můžeme 0 vložit před nebo za tuto posloupnost nebo do mezer mezi písmeny, přičemž na každé z těchto míst lze vložit nejvýše jedno O. Taková místa můžeme vybrat (g) způsoby. Možností je tedy 7! (g).
Příklad 1.21 Krotitel má do arény přivést 4 tygry a 5 lvů tak, aby žádní dva tygři nešli za sebou. Kolika způsoby to lze provést?
Řešení: Nejrpve určíme počet seřazení tygrů a lvů bez ohledu na to, který tygr a který lev kde konkrétně bude. Symbolicky můžeme napsat, že hledáme permutace pěti L a čtyř T takových, že žádná dvě T nenásledují těsně za sebou; například LTLTLTLTL. Takových rozmístění je (^) (mezi pěti L jsou čtyři mezery, jedno místo je před prvním L a jedno za posledním; podobně jako v předchozím příkladu výběrem z těchto šesti míst čtyři místa, na něž umístíme T). V dalším kroku pak „dáme lvům a tygrům jména", což početně znamená, že například místo uvedené permutace bezejmenných tygrů LTLTLTLTL dostáváme 5! -4! Celkem je tedy možností 5!(^) -4!
1.6 Binomická věta
Věta 1.22 Necht a, b jsou proměnné, n £ N. Platí následující vztahy:
(• + ll*=(;h(")"""V + '''+(n-l)a'r,+ (")'" a analogicky
(a - bY = (™) a- - (fy a"" V + • • • + (-I)""1 fy 6" Příklad 1.23 Speciálními příklady binomické věty jsou známé vzorce:
<o+6>2=(o>2+(Oa6+G>2
12
(a - b)3
{a + b)3
(a - b)2 =
Se vzorci, které se opticky podobají binomické větě, se setkáte např. i v matematické analýze.
Binomické věty lze s výhodou užít   například při těchto výpočtech:
(a) 1015 = (100 + l)5 = 1005 + 5 • 1004 + 10 • 1003 + 10 • 1002 + 5-100 + 1
(b) 995 = (100 - l)5 = 1005 - 5 • 1004 + 10 • 1003 - 10 • 1002 + 5-100-1
V obou výše uvedených případech je výpočet jednodušší než přímo umocňovat 101 a 99.
Podobně lze umocňovat i komplexní čísla v algebraickém tvaru. Pro to, abychom mohli podobné příklady počítat, vystačíme se znalostí faktu, že každé komplexní číslo lze zapsat ve tvaru a + bi, přičemž platí i2 = — l.3
Cvičení a úkoly k zamyšlení: binomická věta
Cvičení 1.24 Dokažte binomickou větu metodou matematické indukce.
Cvičení 1.25 Dokažte binomickou větu metodou matematické indukce.
Cvičení 1.26 Určete, který sčítanec je v binomickém rozvoji y/2 + y/Š5° největší.
1.7   Princip inkluze a exkluze.
V některých kombinatorických úlohách se výsledku dobereme tak, že nejprve vezmeme počet možností, který umíme dobře spočítat, i když víme, že tak zahrneme možností příliš mnoho; poté počet upravíme například odečtením nepříznivých případů nebo vydělením. Tyto postupy jsme už použili pro odvození vzorců pro kombinace (podělením příslušného počtu variací), pro permutace s opakováním (podělením celkového počtu permutací počty permutací opakujících se písmen), a tedy i pro odvození vzorce pro výpočet kombinací s opakováním. Ukažme si tuto strategii řešení na některých dalších příkladech.
Příklad 1.27 úprava výsledku dělením - př. č. 1
3Pro ty, kteří se s komplexními čísly dosud nesetkali, doporučujeme např. knihu Emila Caldy Komplexní čísla z řady Matematika pro gymnázia nakladatelství Prométheus.
lQV222Vš28}
13
Příklad 1.28 úprava výsledku dělením - př. č. 2
Příklad 1.29 úprava výsledku odečtením - př. č. 1
Příklad 1.30 úprava výsledku odečtením - př. č. 2
Příklad 1.31 úprava výsledku odečtením - př. č. 3
Někdy nedokážeme určit výsledek pouze pomocí jediného odečtení a musíme opět nějaké možnosti přičíst.
Nej jednodušším použitím principu inkluze a exkluze je vztah pro určení počtu prvků sjednocení dvou konečných množin:
\A\JB\ = \A\ + \B\ -\AHB\
Pro odvození vztahu pro určení počtu prvů sjednocení tří množin můžeme použít například Vennovy diagramy (viz Základy matematiky). Snadno nahlédneme, že
\A U B U C\ = \A\ + \B\ + \C\ -\A n B\ - \A n C\ - \B n C\ + \A n B n C|; pro čtyři množiny:
\AUBUC\JD\ = |A| + |S| + |C| + |D|
-\AnB\ - \AnC\ - \AnD\ - \Bnc\ - \BnD\ - \cnD\ +\A n B n C| + \A n B n D\ + \A n C n D\ + \B n C n D\ - \A n B n C n D\;
pro pět množin:
U BUCUD U E\ = |A| + |5| + |C| + |D| + |£?|
-\AnB\-\AnC\-\AnD\-\AnE\-\BnC\-\BnD\-\BnE\-\cnD\-\cnE\-\DnE
+\A n b n c\ + \A n b n d\ + \A n c n d\ + \b n c n d\ -\AnBnCnD\-\AnBnCnE\-\AnCnDnE\-\BnCnDnE\
+\AnBnCnDnE\
atd., a tedy pro n množin lze formulovat
14
Obecný princip inkluze a exkluze:
|MiUM2U---UMn| = |Mi| + |Ař2| + --- + |Mn|
-|Ml n M2| - |Mi n M3|-----|Mi nM„|
-|M2 n M3|-----|M2 n Mn| - |M3 n M4|---|M„_i n Mn\
+\Mi n m2 n m3| + • • • |mn_2 n mn_i n m„| _... + ... + (-i)n|Afi n M2 n • ■ • n Mn\
Příklad 1.32 (Eratosthenovo síto) Kolik je prvočísel mezi čísly od 1 do 100.
Můžeme si představit, že budeme postupovat jako prý postupoval Era-toshenes ve starověkém Řecku: na voskovou tabulku napíšeme čísla od 1 do 100 a horkou jehlou „propichujeme" místa označená násobky prvočísel, tj. násobky 2: 4, 6, 8, 10, .. .atd., násobky 3: 6, 9, 12, .. .atd., násobky 5: 10, 15, 20, 25, ... atd. a násobky 7: 14, 21, ... atd.
Snadno nahlédneme, že některá čísla vypichujeme vícekrát, například 6, 10, 15, 30, ... atd. toho níže využijeme. Dále využijeme skutečnosti, že při zkoumání toho, zda je dané číslo n prvočíslo, stačí vyzkoušet dělitelnost prvočísly do hodnoty \pň (včetně). V našem případě hledáme prvočísla do 100, tedy stačí zkoumat děliletnost prvočísly 2, 3, 5 a 7.
Víme, že 1 není prvočíslo, tedy můžeme počítat s 99 čísly. Nejprve od 99 odečteme počet všech násobků 2, 3, 5 a 7 s výjimkou těchto prvočísel:
99 - 49 - 32 - 19 - 13 = 50 - 51 - 13 = -14
Výsledkem je záporné číslo, neboť např. číslo 6 jsme odečetli dvakrát: jednou jako násobek dvou, jednou jako násobek tří. Všechna tato nedopatření se pokusíme napravit naráz tím, že přičteme zpět násobky 6, 10, 14, 15, 21 a 35:
99 - 49 - 32 - 19 - 13 + 16 + 10 + 7 + 6 + 4 + 2 = 31
Teď již nemáme varování v podobě záporného výsledku, ale snadno nahlédneme, že jsme například 30 přičetli třikrát: v prvním kroku jsme 30 třikrát odečetli (jako násobek 2, 3 a 5) a nyní jsme je třikrát přičetli (jako násobek 6, 10 a 15). Číslo 30 ale není prvočíslo, je tedy třeba je (a jemu podobná čísla, např. 70) odečíst. Dalším pokusem o nápravu je tedy odečtení násobků trojic prvočísel, tj. 30, 42, 70 a 105:
99-49-32- 19- 13+ 16+ 10+ 7 + 6 + 4 + 2- 3- 2-1 = 25
Naši snahu by mohlo zhatit číslo, které by bylo dělitelné všemi čtyřmi prvočísly; nejmenší takové číslo však je 210, a tedy bychom přičetli 0 (tolik je mezi čísly od 1 do 100 násobků 210).
(Jen pro úplnost: v prvním kroku bychom je 4x odečetli, následně 6x přičetli a nakonec 4x odečetli; v součtu bychom je tedy odečetli 2x, přičemž jsme je chtěli odečíst pouze lx; to bychom napravili tím, že bychom je nyní ještě lx přičetli; nic takového však dělat nemusíme, protože číslo 210 vůbec
15
do hry nevstoupilo: počítali jsme stále pouze s čísly menšími nebo rovnými 100.)
Pro pořádek odpověď: mezi čísly 1 až 100 je 25 prvočísel.
Definujeme-li jednotlivé množiny pomocí vlastností, pak množina Mi obsahuje prvky s vlastností 1, množina Mn prvky s vlastností i, analogicky Mi n M j prvky s vlastnostmi i a současně j, atd. Pak lze např. odvodit, že prvků, které nemají žádnou z požadovaných vlastností (přičemž prvky, které nemají vlastnost i označíme M\ a množinu obsahující všechny uvažované prvky označíme M), je
|Aři/nAř2/n---nMn/| =
|Af|-|Mi|-|Ař2|-----\Mn\
+|Mi n M2| + |Mi n M3| + • • • + |Mi n Mn\ +\M2 n M3| + • • • + |M2 n Mn\ + |M3 n M4| + • + |Mn_i n Mn\
-\Mi n m2 n m3|----|Mn_2 n Mn_i n m„|
+-------+ (-i)n|M1nM2n---nMn|
příklady:
lednička, auto, chata znalost jazyků kroužky
1.8 Problém šatnářky (speciální princip inkluze a exkluze)
pro 4 osoby - 9 možností pro 5 osob - 44 možností
1.9 Další typy kombinatorických úloh
Kromě variací, permutací a kombinací známe další typické kombinatorické kategorie. Z nich si nyní představíme dva typy, a to počítání, kolika způsoby lze přirozené číslo zapsat ve tvaru sčítanců-přirozených čísel, a dále počítání, kolika způsoby můžeme věci (rozlišitelné nebo nerozlišitelné) rozdělit do přihrádek (rozlišitelných nebo nerozlišitelných)-
1.10 Kompozice a rozklady.
definice - kompozice
jak: analogie vzorce pro kombinace s opakováním definice - rozklady
16
1.11   Rozdělování do přihrádek.
rozlišitelné a nerozlišitelné věci
roz. a neroz. přihrádky
tabulka
převedení jednotlivých problémů na již známé kombinatorické kategorie
1.12   Závěrem ke kombinatorice.
Dosud představené kombinatorické úlohy jsou samozřejmě pouhou „ochutnávkou". Vůbec jsme se nedotkli problematiky magických ěi latinských čtverců, neformulovali jsme Kirkmanův problém 15 dívek, nedefinovali jsme Bellova či Stirlingova čísla. To je obsahem pokročilejších kurzů diskrétní matematiky. Zde probíraná látka představuje — kromě procvičení logického uvažování atp. — průpravu pro výukuteorii pravděpodobnosti.
17