DISKRÉTNÍ MATEMATIKA II

Fakulta pedagogická, Technická univerzita v Liberci

DISKRÉTNÍ MATEMATIKA II Doc. RNDr. Miroslav Koucký, CSc.

Liberec, 2004

Úvod Diskrétní matematika, resp. její základy, patří již tradičně mezi standardní témata přednášená na Technické univerzitě v Liberci, zejména na Fakultě mechatroniky (jednosemestrální přednáška Základy diskrétní matematiky – společná pro celý 1. ročník a Diskrétní matematika pro 3.ročník) a na Fakultě pedagogické (dvousemestrální přednáška Diskrétní matematika – pro 1. ročník obor informatika). Přes zřejmou poptávku ze stran studentů, nebyl na naší univerzitě doposud vydán žádný učební text, který by danou oblast odpovídajícím způsobem pokryl. Tato skripta jsou snahou autora tento zřejmý nedostatek napravit. Z hlediska obsahu jde o druhý díl skript Diskrétní matematika I (Koucký, Zelinka, TUL 2001) a obsahuje především základní partie teorie dělitelnosti, kombinatoriky včetně vytvořujících funkcí a rekurentních vztahů. Studium skript předpokládá pouze základní znalosti středoškolské matematiky a schopnost elementární logické úvahy. V omezené míře se používají některé pojmy (především relace, zobrazení, funkce) zavedené ve skriptu Diskrétní matematika I. Vhodným doplňkem obou skript je Sbírka úloh z diskrétní matematiky, která vychází současně, a která obsahuje řešené i neřešené příklady umožňující důkladné procvičení jednotlivých témat. Přes usilovnou snahu autora lze očekávat, že jako každá skripta i tato obsahují celou řadu nepřesností, resp. chyb. Autor bude vděčný za každou připomínku vedoucí ke zlepšení věcné i formální stránky následujícího textu.

Autor

Diskrétní matematika II

strana 1

Obsah

Kap 1.

Teorie dělitelnosti

…3

1.1

Definice a základní pojmy z teorie dělitelnosti

…3

1.2

Společný dělitel, společný násobek

…9

1.3

Prvočísla a prvočíselné rozklady

… 20

1.4

Základní aritmetické funkce

… 28

1.5

Řetězové zlomky

… 35

1.6

Kongruence

… 41

1.7

Řešení kongruencí 1. stupně a jejich soustav

… 52

Kap 2.

Kombinatorika

… 60

2.1

Základní pravidla kombinatoriky

… 61

2.2

Variace, permutace, kombinace

… 69

2.3

Základní kombinatorické identity a úlohy

… 84

2.4

Rekurentní vztahy a vytvořující funkce

… 97

2.5

Základní kombinatorické posloupnosti

… 102

Přílohy ♦

Použité značení

… 106

♦

Tabulka prvočísel

… 108

♦

Tabulka hodnot Eulerovy funkce

… 110

♦

Tabulka hodnot Möbiovy funkce

… 112

♦

Tabulka hodnot subfaktoriálů

… 114

♦

Tabulka hodnot Fibonacciho čísel

… 114

♦

Literatura a relevantní zdroje na internetu

… 115


strana 2

Kapitola 1.

Teorie dělitelnosti

C. F. Gauss: „Matematika je královnou všech věd a teorie čísel je královna matematiky.“ Základním číselným oborem, se kterým budeme v této kapitole pracovat, jsou celá čísla a pouze v některých jasně definovaných případech se omezíme na jejich podobory, nejčastěji N, resp. N+. Víme již, že celá čísla tvoří algebraickou strukturu (označovanou jako eukleidovský obor integrity), která je uzavřená vzhledem k operaci sčítání, odčítání a násobení, tj. součet, rozdíl i součin libovolných dvou celých čísel je opět celé číslo. Vzhledem k operaci dělení však celá čísla tuto vlastnost obecně nemají. Obsahem této kapitoly budou právě vlastnosti celých čísel vzhledem k operaci dělení a hlavní výsledky, které se dotýkající problematiky dělitelnosti, prvočísel a kongruencí, mají zásadní význam, např. v oblasti výpočetní techniky, moderní teorie kódování, stochastického modelování apod.

1.1

Definice a základní pojmy z teorie dělitelnosti

Definice 1.1.1 - dělitelnost Řekneme, že nenulové celé číslo b dělí a, píšeme b| a , jestliže existuje celé číslo q takové, že

a = b⋅q .

(1.1)

V opačném případě píšeme b /| a a říkáme, že b nedělí a. ¶ Pokud b dělí a, říkáme také, že a je dělitelné b. Číslo q nazýváme podílem, číslo a násobkem čísla b a číslo b dělitelem čísla a. Dělitele b nazveme vlastním dělitelem čísla a, jestliže b ≠ a ∧ b ≠ 1.

Věta 1.1.1 Relace dělitelnosti | má následující vlastnosti: a) ∀a ∈ Z platí 1| a , b) ∀a ∈ Z − {0} platí a | 0 ,


strana 3

c) ∀a ∈ Z − {0} platí a | a , d) ∀a, b ∈ Z platí (a | b ∧ b | a )  → (a = b ∨ a = −b ) , e) ∀a, b, c ∈ Z platí (a | b ∧ b | c )  → a | c , f) ∀a, b, c ∈ Z platí a | b  → a | b ⋅ c , g) ∀a, b, c, d ∈ Z platí

(a + b = c ∧ d | a ∧ d | c ) → d | b .

Důkaz. ad a, b, c) Snadné cvičení i pro čtenáře. ad d) Vzhledem k a | b ∧ b | a platí b = a ⋅ q1 ∧ a = b ⋅ q 2 , kde q1 , q 2 ∈ Z , tedy a = a ⋅ q1 ⋅ q 2 . Jelikož a, b ≠ 0 , dostáváme rovnici q1 ⋅ q 2 = 1 , která má v oboru celých čísel dvě řešení q1 = q 2 = 1 ∨ q1 = q 2 = −1 . Odtud a = b ∨ a = −b . ad e) Zřejmě platí b = a ⋅ q1 ∧ c = b ⋅ q 2 , kde q1 , q 2 ∈ Z . Odtud c = a ⋅ q1 ⋅ q 2 , tj. a| c . ad f)

Zřejmě platí b = a ⋅ q, q ∈ Z , tedy b ⋅ c = a ⋅ (q ⋅ c ) , tj. a | b ⋅ c .

ad g) Zřejmě a = d ⋅ q1 ∧ c = d ⋅ q 2 ∧ b = c − a , kde q1 , q 2 ∈ Z , tedy b = d ⋅ (q 2 − q1 ) , což je ekvivalentní dokazovanému tvrzení d | b . ¶

Poznámka 1.1.1 ♦

Připomeňme, že vlastnost a) se nazývá reflexivita a c) tranzitivita relace dělitelnosti. Pokud bychom ve větě 1.1.1 nahradili číselný obor Z oborem přirozených čísel N, dostali bychom místo b) následující vlastnost: b*) ∀a, b ∈ N platí (a | b ∧ b | a )  → a = b , která se označuje jako antisymetrie. Je tedy zřejmé, že v oboru přirozených čísel je relace dělitelnosti (částečným) uspořádáním, která však není lineární (libovolná dvojice přirozených čísel a, b nemusí být v relaci, tj. nemusí platit a | b ani b | a).

♦

Vlastnost g) předcházející věty lze zobecnit následujícím způsobem: g*) Je-li známo, že číslo d dělí všechny členy rovnosti

n

m

∑a = ∑b i =1

i

j =1

j

kromě jediného,

nutně dělí i zbývající člen. ♦

Jako zřejmý důsledek vlastnosti g*) dostáváme: Jestliže a | bi , i = 1,… , n , potom a | (b1 ⋅ x1 + … + bn ⋅ x n ) pro libovolná xi ∈ Z , i = 1,… , n .


strana 4

Příklad 1.1.1 Nalezněte všechna celočíselná řešení rovnice 21 x1 + 84 x 2 − 35 x3 = 113 . Řešení. Předpokládejme, že existují celá čísla x1 , x 2 , x3 , která jsou řešením uvedené rovnice. Vzhledem k tomu, že 7|21, 7|84 a 7|(-35), nutně musí platit (dle výše uvedené poznámky) 7|113. Spor, tedy rovnice nemá v oboru celých čísel řešení. ¶

Příklad 1.1.2 Nechť x0 , y 0 jsou libovolná celá čísla taková, že 11| (5 x 0 + 7 y 0 ) , potom 11| (8 x0 + 20 y 0 ) . Řešení. Snadno nahlédneme, že existuje alespoň jedna dvojice x0 , y 0 s vlastností 11| (5 x 0 + 7 y 0 ) , např. x0 = 20, y 0 = 3 . Dále zřejmě platí 11| (− 2 ) ⋅ (11 x0 + 11 y 0 ) a vzhledem k předpokladu 11| 6 ⋅ (5 x0 + 7 y 0 ) . Z poznámky 1.1.1 dostáváme 11| [(− 2) ⋅ (11 x 0 + 11 y 0 ) + 6 ⋅ (5 x0 + 7 y 0 )] a po snadné úpravě 11| (8 x0 + 20 y 0 ) . ¶

Pro další úvahy o dělitelnosti má zásadní význam následující tvrzení, označované jako věta o dělení se zbytkem.

Věta 1.1.2 – Dělení se zbytkem Pro každé a ∈ Z , b ∈ N + existují jediná q , r ∈ Z taková, že platí a = b ⋅ q + r , kde 0 ≤ r < b .

(1.2)

Důkaz. Definujme q jako největší celé číslo pro které platí b ⋅ q ≤ a a číslo r vztahem r = a − b ⋅ q . Snadno nahlédneme, že obě čísla vždy existují, vyhovují (1.2) a tedy zbývá dokázat jejich jednoznačnost.

Označme

a = b ⋅ q1 + r1 , 0 ≤ r1 < b

předpokládat, že

proto a

0 ≤ r2 ≤ r1 .

q1 , r1 , q 2 , r2

libovolná

celá

čísla,

pro

která

a = b ⋅ q 2 + r2 , 0 ≤ r2 < b . Bez újmy na obecnosti lze

Dále zřejmě platí

b ⋅ (q1 − q 2 ) + (r1 − r2 ) = 0 . Jelikož

b | b ⋅ (q1 − q 2 ) a b | 0 musí b | (r1 − r2 ) což vzhledem k vlastnosti 0 ≤ r1 − r2 < b vede k r1 = r2

a tedy i q1 = q 2 . ¶


strana 5

Poznamenejme, že pro čísla a, b, q, r z věty 1.1.2 se běžně používá následující terminologie: a … dělenec, b … dělitel, q … neúplný podíl, r … zbytek.

Příklad 1.1.3 Zřejmě platí: b = 23

128 = 23·5 + 13, tj. q = 5, r = 13,

a = -128 b = 23

-128 = 23·(-6) + , tj. q = -6, r = 10,

a = 128

a = 19

b = 54

19 = 54·0 + 19, tj. q = 0, r = 19,

a = -19

b = 54

-19 = 54·(-1) + 35, tj. q = 0, r = 35,

a = 108

b = 36

108 = 36·3 + 0, tj. q = 3, r = 0,

a=0

b = 29

0 = 29·0 + 0, tj. q = 0, r = 0.

¶

Jak dokumentuje následující příklad, nachází věta o dělení se zbytkem využití při převodech z desítkové soustavy do ostatních číselných soustav. Připomeňme, že v soustavě o základu b (b přirozené větší než jedna), vyjadřujeme přirozená čísla ve tvaru r0 + r1 ⋅ b + r2 ⋅ b 2 + … + rn ⋅ b n ,

(1.3)

kde ri ∈ {0,… , b − 1}, n ∈ N a používáme zkrácený zápis (rn … r1 r0 )b . V případě dvojkové (binární) soustavy, kde b = 2, nazýváme jednotlivé cifry ri bity ( r0 nejméně významný bit, rn nejvýznamnější bit) a řetězec osmi bitů bytem.

Příklad 1.1.4 Převeďte číslo 6862 do číselné soustavy o základu a) 2, b) 8, c) 16. Řešení. Hledané cifry r0 , r1 ,… , rk získáme jako zbytky při opakovaném dělení daného čísla a následně získaných podílů základem b. V jednotlivých případech tak dostáváme: ad a) Základ b = 2, tj. ri ∈ {0,1} . Postupným dělením číslem 2 tak dostáváme: 6862 = 2·3431 + 0 (r0 ) ,

3431 = 2·1715 + 1 (r1 ) ,

1715 = 2·857 + 1 (r2 ) ,

857 = 2·428 + 1 (r3 ) ,

428 = 2·214 + 0 (r4 ) ,

214 = 2·107 + 0 (r5 ) ,


strana 6

107 = 2·53 + 1 (r6 ) ,

53 = 2·26 + 1 (r7 ) ,

26 = 2·13 + 0 (r8 ) ,

13 = 2·6 + 1 (r9 ) ,

6 = 2·3 + 0 (r10 ) ,

3 = 2·1 + 1 (r11 ) ,

1 = 0·2 + 1 (r12 ) ,

tedy 6862 = (1101011001110)2 .

ad b) Základ b = 8, tj. ri ∈ {0,1,… , 7} . Postupným dělením číslem 8 tak dostáváme: 6862 = 8· 857 + 6 (r0 ) ,

857 = 8· 107 + 1 (r1 ) ,

107 = 8·13 + 3 (r2 ) ,

13 = 8·1 + 5 (r3 ) ,

1 = 8·0 + 1 (r4 ) ,

tedy 6862 = (15316 )8 .

ad c) Základ b = 16, tj. ri ∈ {0,1,… , 9, A, B, C , D, E , F } . Postupným dělením číslem 16 tak dostáváme: 6862 = 16· 428+ 14 (r0 ) ,

428= 16· 26+ 12 (r1 ) ,

1 = 16·0 + 1 (r3 ) ,

tedy 6862 = (1ACE )16 . ¶

26= 16·1+ 10 (r2 ) ,

Poznámka 1.1.2 – dvojková soustava ♦

K vyjádření čísel v oblasti výpočetní techniky se používají různé číselné formáty, jejichž velikost bývá násobkem bytů, tj. osmi bitů. Například pomocí osmi bitů lze ve dvojkové soustavě vyjádřit přirozená čísla 0,…, 255, pomocí 16 bitů čísla 0,…, 65 535 a 32 bitů 0,…, 4 294 967 295. Snadno zjistíme, že pomocí n bitů lze ve dvojkové soustavě vyjádřit 2 n přirozených čísel 0,… ,2 n − 1 , přičemž u čísel 0,… ,2 n −1 − 1 je nejvýznamnější bit nastaven na 0 a u zbývajících čísel, tj. 2 n −1 ,… ,2 n − 1 je nejvýznamnější bit nastaven na 1. Této skutečnosti se pak vhodným způsobem využívá k vyjádření záporných čísel − 1,… ,−2 n −1 ve tvaru dvojkových doplňků čísel 0,… ,2 n −1 − 1 a tedy u záporných čísel je

nejvýznamnější bit nastaven na 1. V tomto případě jsou pomocí n bitů vyjadřována celá čísla z množiny {− 2 n −1 ,… ,−1, 0,1,… , 2 n −1 − 1}. Například, využitím čtyř bitů lze zapsat čísla − 8,… ,−1, 0,1,… , 7 . Jejich vyjádření je uvedeno v následující tabulce:


strana 7

Nezáporné číslo

Vyjádření ve dvojkové soustavě

Vyjádření ve tvaru dvojkového doplňku

Záporné číslo

7

0111

…………

1000

-8

6

0110

…………

1001

-7

5

0101

…………

1010

-6

4

0100

…………

1011

-5

3

0011

…………

1100

-4

2

0010

…………

1101

-3

1

0001

…………

1110

-2

0

0000

…………

1111

-1

Formát záporného celého čísla k , kde − 2 n ≤ k ≤ −1 lze popsat následovně: 1) Vypočti přirozené číslo k = 2 n − k . 2) Přirozené číslo k vyjádři pomocí n bitů ve dvojkové soustavě, tj. k = (0 bn −1 … b1b0 )2 . (Jelikož 0 ≤ k ≤ 2 n − 1 je nejvýznamnější bit zřejmě nastaven na nulu, tj. bn = 0 ). 3) Hledané vyjádření záporného celého čísla k

pak dostáváme nastavením nej-

významnějšího bitu na jedničku, tj. k = (1bn −1 … b1b0 ) . ♦

V oblasti výpočetní techniky (sítě IADM, delta, gama, omega apod.) nachází široké uplatnění, především k popisu struktury množiny všech cest mezi vybranými uzly, i tzv. znaménková binární soustava. Tato číselná soustava používá základ 2 a cifry ri ∈ {− 1, 0,1} a lze snadno nahlédnout, že je pro tuto soustavu charakteristické obecně nejednoznačné vyjádření nenulových čísel. Například číslo 7 lze vyjádřit pomocí čtyř bitů ve tvaru 7 = 1 + 1 ⋅ 2 + 1 ⋅ 2 2 + 0 ⋅ 2 3 = (− 1) + 0 ⋅ 2 + 0 ⋅ 2 2 + 1 ⋅ 2 3 = 1 + 1 ⋅ 2 + (− 1) ⋅ 2 2 + 1 ⋅ 2 3 , tj. 7 = (0111)2 = (100 1 )2 = (1 1 11)2 , kde 1 označuje cifru –1 a symbol 2 znaménkovou binární soustavu.


strana 8

1.2

Společný dělitel, společný násobek

Definice 1.2.1 – společný dělitel, společný násobek ♦

Nenulové přirozené číslo d nazveme společným dělitelem celých čísel a, b, jestliže

d | a ∧ d | b , tj. d dělí obě čísla. ♦

Nenulové přirozené číslo D nazveme společným násobkem nenulových celých čísel a, b, jestliže a | D ∧ b | D , tj. D je dělitelné oběma čísly. ¶

Zdůrazněme skutečnost, že v souladu s výše uvedenou definicí 1.2.1 vyšetřujeme pouze kladné společné dělitele a kladné společné násobky.

Příklad 1.2.1 Jediní společní dělitelé čísel a = 420, b = 36 jsou 1, 2, 3, 4, 6, 12 a čísla 1260 ⋅ n , kde n ∈ N , jsou všechny jejich společné násobky. ¶

Pro libovolná a, b ∈ Z − {0}, označme Da ,b množinu všech společných dělitelů čísel a, b . Snadno zjistíme, že Da ,b je shora omezená, neboť žádný z dělitelů nemůže být větší než min ( a , b ) , a tedy množina Da ,b má vzhledem k přirozenému uspořádání jednoznačně určený

maximální prvek. Stejně snadno zjistíme, že množina N a ,b všech společných násobků nenulových čísel a, b je zdola omezená, neboť žádný společný násobek nemůže být menší než max( a , b ) , a tedy množina N a ,b má vzhledem k přirozenému uspořádání jednoznačně určený minimální prvek. Tyto skutečnosti nás opravňují k zavedení následujících pojmů.

Definice 1.2.2 – největší společný dělitel, nejmenší společný násobek, nesoudělnost ♦

Největším společným dělitelem celých čísel a, b , z nichž alespoň jedno je různé od nuly, nazveme takového jejich společného dělitele, který je ze všech společných dělitelů největší (existuje vždy a jediný).

♦

Nejmenším společným násobkem nenulových celých čísel a, b nazveme takový jejich společný násobek, který je ze všech společných násobků nejmenší (existuje vždy jediný).


strana 9

♦

Řekneme, že celá čísla a, b jsou nesoudělná, jestliže jejich největší společný dělitel je roven jedné. ¶

Pro největší společný dělitel čísel a, b se vžilo označení NSD(a, b ) , resp. (a, b ) a pro jejich nejmenší společný násobek NSN (a, b ) . Nesoudělnost čísel a, b vyjadřujeme obvykle zápisem NSD(a, b ) = 1 , resp. (a, b ) = 1 .

Nyní přirozeně vzniká otázka, jak největšího společného dělitele efektivně nalézt. Odpověď dává následující algoritmus, jehož základem je věta o dělení se zbytkem.

Eukleidův algoritmus – určení NSN (a, b ) Nechť a, b ∈ N + . Jestliže aplikujeme následující postupné dělení se zbytkem a = b ⋅ q 0 + r1 ,

0 < r1 < b ,

b = r1 ⋅ q1 + r2 ,

0 < r2 < r1 ,

r1 = r2 ⋅ q 2 + r3 ,

0 < r3 < r2 ,

ri = ri +1 ⋅ qi +1 + ri + 2 ,

0 < ri + 2 < ri +1 ,

rn − 2 = rn −1 ⋅ q n −1 + rn , 0 < rn < rn −1 , rn −1 = rn ⋅ q n ,

potom největší společný dělitel čísel a, b je roven poslednímu od nuly různému zbytku ve výše uvedeném postupu, tj. NSD(a, b ) = rn . Důkaz. Je třeba dokázat konečnost uvedeného postupu a tvrzení, že NSD(a, b ) = rn . Konečnost vyplývá ze skutečnosti, že zbytky r1 ,… , rn tvoří klesající posloupnost přirozených čísel (věta 1.1.2 – dělení se zbytkem) a tedy uvedený algoritmus skončí po provedení nejvýše b kroků (lze dokonce ukázat, že počet kroků je roven nejvýše pětinásobku počtu cifer menšího

z čísel a, b ). Z věty 1.1.1, část g) dále vyplývá, že NSD(a, b ) = NSD(b, r1 ) = NSD(r1 , r2 ) = … = NSD(rn − 2 , rn −1 ) = NSD(rn −1 , rn ) = rn . ¶


strana 10

Příklad 1.2.2 Určete: a) NSD(420, 36 ) , b) NSD(8 n + 3, 5 n + 2 ) , kde n ∈ N . Řešení. Aplikací Eukleidova algoritmu dostáváme: ad a) 420 = 36·11 + 24, ad b)

36 = 24·1 + 12,

tedy NSD(420, 36 ) = 12 .

24 = 12·2,

8 n + 3 = (5 n + 2 ) ⋅ 1 + (3 n + 1) ,

5 n + 2 = (3 n + 1) ⋅ 1 + (2 n + 1) ,

3 n + 1 = (2 n + 1) ⋅ 1 + n ,

2 n + 1 = n ⋅ 2 + 1,

n = 1⋅ n ,

tedy NSD(8 n + 3, 5 n + 2 ) = 1 a pro libovolné n ∈ N jsou uvažovaná čísla nesoudělná. ¶

V praxi se osvědčilo zapisovat Eukleidův algoritmus pomocí následujícího schématu, kde čísla psaná (pro rozlišení) kurzívou označují podíly qi a čísla psaná tučně zbytky ri . Výpočet z příkladu 1.2.2 tak probíhá následovně: ad a)

24 24 0

36 24 12 2 … r3

420 36 396 11 … q0 24 … r1 1 … q1 … r2 … q2

ad b)

n n 0


2n + 1 2n 1 n … r5

3n + 1 2n + 1 n 2 … r4 … q4

5n + 2 3n + 1 2n + 1 1 … r3 … q3

8n + 3 5n + 2 3n + 1 1 … r2 … q2

5n + 2 1 … r1 … q1

… q0

strana 11

Věta 1.2.1 – základní vlastnosti NSD Pro největší společný dělitel dvou čísel platí: a) NSD(a, b ) = NSD (b, a ) ,

(1.4)

b) NSD(k ⋅ a, k ⋅ b ) = k ⋅ NSD (a, b ) , kde k ∈ N + ,

(1.5)

 a b  NSD(a, b ) c) d | a ∧ d | b  → NSD ,  = , d d d

(1.6)

d) NSD(a, b ) = 1  → NSD(a ⋅ c, b ) = NSD(c, b ) .

(1.7)

Důkaz. ad a) Zřejmé (řádně zdůvodněte!). ad b) Bezprostřední důsledek Eukleidova algoritmu, neboť jednotlivé řádky algoritmu lze vynásobit nenulovým přirozeným číslem k. ad c) Vzhledem k předpokladu a již dokázané části b) dostáváme a b  a⋅d b⋅d  NSD(a, b ) = NSD ,  = d ⋅ NSD ,  , d  d d  d tedy  a b  NSD(a, b ) NSD ,  = . d d d (Uvědomte si, kde využíváme předpoklad, že d je společným dělitelem čísel a, b.) ad d) Stačí dokázat, že NSD(a ⋅ c, b )| NSD(c, b ) ∧ NSD (c, b )| NSD (a ⋅ c, b ) . Zřejmě NSD (a ⋅ c, b )| NSD (a ⋅ c, b ⋅ c ) , tj. NSD(a ⋅ c, b )| (c ⋅ NSD (a, b )) a s ohledem na NSD(a, b ) = 1 platí NSD (a ⋅ c, b )| c , tedy NSD(a ⋅ c, b )| NSD(c, b ) .

Naopak, NSD(c, b )| c , tedy NSD (c, b )| a ⋅ c . Odtud NSD(c, b )| NSD (a ⋅ c, b ) . ¶

Jako užitečné důsledky věty 1.2.1 dostáváme: ♦

d | a ∧ d |b ← → d | NSD(a, b ) ,

(1.8)

♦

NSD(a, b ) = 1 ∧ b | a ⋅ c  → b | c ,

(1.9)

  a b  = 1 , NSD ,  NSD(a, b ) NSD(a, b ) 

(1.10)

♦

a tedy každá dvě nenulová přirozená čísla a, b lze vyjádřit ve tvaru a = a1 ⋅ NSD (a, b ), b = b1 ⋅ NSD (a, b ) ,

(1.11)

kde NSD(a1 , b1 ) = 1 . Tuto skutečnost budeme často využívat.


strana 12

Kromě Eukleidova algoritmu existuje celá řada dalších způsobů výpočtu největšího společného dělitele. Např. z věty 1.2.1 lze snadno odvodit následující tzv. dvojkový NSD algoritmus (další způsob, který využívá prvočíselné rozklady je uveden v kapitole věnované problematice prvočísel). Dvojkový NSD algoritmus - určení NSN (a, b ) Největšího společného dělitele libovolných dvou nenulových celých čísel a, b lze nalézt opakovanou aplikací následujících pravidel (dokažte!): a b 1) Jsou-li a, b sudá, potom NSD(a, b ) = 2 ⋅ NSD ,  .  2 2 a  2) Je-li a sudé, b liché, potom NSD(a, b ) = NSD , b  . 2   a−b  , b  . 3) Jsou-li a, b lichá, potom NSD(a, b ) = NSD 2   4) NSD(a, b ) = NSD (b, a ) . Algoritmus ukončíme v situaci, kdy a = b (zdůvodněte, že skutečně nastane!) a využijeme NSD(a, a ) = a .

Příklad 1.2.3 Pomocí dvojkového NSD algoritmu určete NSD(258,1728) . Řešení. Postupnou aplikací pravidel dvojkového NSD algoritmu dostáváme (použité pravidlo je uvedeno nad rovnítkem): 1)

2)

3)

3)

NSD(258,1728) = 2 ⋅ NSD(129, 864 ) = 2 ⋅ NSD(129, 27 ) = 2 ⋅ NSD(51, 27 ) = 3)

2)

3), 4 )

2)

= 2 ⋅ NSD(12, 27 ) = 2 ⋅ NSD(3, 27 ) = 2 ⋅ NSD(12, 3) = 2 ⋅ NSD(3, 3) = 2 ⋅ 3 , tj. NSD(258,1728) = 6 . ¶

V celé řadě případů je velmi užitečná následující charakteristika největšího společného dělitele:


strana 13

Jsou-li a, b nenulová celá čísla, potom jejich největší společný dělitel je roven (dokažte!) nejmenšímu kladnému přirozenému číslu tvaru a ⋅ x1 + b ⋅ x 2 , kde x i ∈ Z .

(1.12)

Jak dokumentuje následující příklad, umožňuje Eukleidův algoritmus takové vyjádření efektivně nalézt.

Příklad 1.2.4 Vyjádřete největšího společného dělitele následujících čísel ve tvaru (1.12): a) 583 a 231, b) n 3 + n 2 − 2 a n 3 − 1 , kde n ∈ N . ad a) Nejprve aplikujeme Eukleidův algoritmus: 583 = 231 ⋅ 2 + 121 … r1 ,

231 = 121 ⋅ 1 + 110 … r2 ,

121 = 110 ⋅ 1 + 11 …… r3 ,

110 = 11 ⋅ 10 ,

tedy NSD(583, 231) = r3 = 11 . Nyní největšího společného dělitele r3 ve tvaru (1.12) získáme postupným vyjádřením zbytků r1 = 121 = 583 − 231 ⋅ 2 ,

r2 = 110 = 231 − 121 ⋅ 1 ,

r3 = 11 = 121 − 110 ⋅ 1 a jejich zpětným dosazováním dostáváme 11 = 121 − 110 ⋅ 1 = 121 − (231 − 121 ⋅ 1) ⋅ 1 = 121 ⋅ 2 − 231 = = (583 − 231 ⋅ 2 ) ⋅ 2 − 231 = 583 ⋅ 2 + 231 ⋅ (− 5) ,

tedy x1 = 2, x 2 = −5 a NSD(583, 231) = 583 ⋅ 2 + 231 ⋅ (− 5) = 11 . ad b) Aplikací Eukleidova algoritmu dostáváme:

(

)

(

)

n 3 + n 2 − 2 = n 3 − 1 ⋅ 1 + n 2 − 1 … r1 ,

(

)

n 3 − 1 = n 2 − 1 ⋅ n + (n − 1) … r2 ,

n 2 − 1 = (n − 1) ⋅ (n + 1) ,

(

)

tedy NSD n 3 + n 2 − 2, n 3 − 1 = r2 = n − 1 . Vyjádřením zbytků dostáváme

(

) (

)

r1 = n 2 − 1 = n 3 + n 2 − 2 − n 3 − 1 ⋅ 1 ,

(

) (

)

r2 = n − 1 = n 3 − 1 − n 2 − 1 ⋅ n .

Dosazením r1 do r2 získáme vyjádření největšího společného dělitele v hledaném

(

) (

)

(

)

tvaru NSD n 3 + n 2 − 2, n 3 − 1 = n 3 + n 2 − 2 ⋅ (− n ) + n 3 − 1 ⋅ (n + 1) = n − 1 ,


strana 14

tj. x1 = −n, x 2 = n + 1 . ¶

Přirozeným rozšířením pojmů společný dělitel a největší společný dělitel dvou čísel je následující definice.

Definice 1.2.3 – společný dělitel, největší společný dělitel a1 ,… , a n Společným dělitelem celých čísel a1 ,… , a n , kde n ≥ 2 , nazveme každé nenulové přirozené číslo d, které dělí beze zbytku všechna čísla a1 ,… , a n , tj. ∀i ∈ {1,… , n} d | ai . Největším společným dělitelem celých čísel a1 ,… , a n , z nichž alespoň jedno je různé od nuly, nazveme takového jejich společného dělitele, který je největší (existuje vždy a jediný). ¶

Poznámka 1.2.1 ♦

Úlohu na výpočet největšího společného dělitele více než dvou čísel a1 ,… , a n , převádíme na opakovaný výpočet největšího společného dělitele dvou čísel dle schématu: d 2 = NSD (a1 , a 2 ) ,

d 3 = NSD (d 2 , a3 ) , d 4 = NSD (d 3 , a 4 ) , d n = NSD (d n −1 , a n ) , kde NSD(a1 ,… , a n ) = d n . ♦

Největší společný dělitel nenulových celých čísel a1 ,… , a n , n ≥ 2 je roven nejmenšímu kladnému přirozenému číslu tvaru n

∑a i =1

♦

i

⋅ xi , kde x i ∈ Z .

(1.13)

V případě více než dvou čísel se dále zavádějí pojmy nesoudělnost (někdy označovaná jako sdružená nesoudělnost) a nesoudělnost po dvou. Řekneme, že čísla a1 ,… , a n jsou nesoudělná, jestliže NSD(a1 ,… , a n ) = 1 a řekneme, že jsou nesoudělná po dvou, jestliže jsou nesoudělné všechny dvojice, tj.

∀i ≠ j

NSD (ai , a j ) = 1 .

Je

zřejmé,

že

z nesoudělnosti po dvou vyplývá nesoudělnost a jak lze nahlédnout z následující ukázky, obrácené tvrzení neplatí. Diskrétní matematika II

strana 15

Například trojice čísel 14, 15, 121 je nesoudělná po dvou, neboť NSD(14, 15) = 1 , NSD(14, 121) = 1, NSD(15, 121) = 1 a tedy i nesoudělná, tj. NSD (14, 15, 121) = 1 .

Trojice čísel 12, 15, 35 je nesoudělná, tj. NSD(12, 15, 35) = 1 , ovšem není nesoudělná po dvou, neboť NSD(12, 15) = 3, NSD(12, 35) = 1, NSD (15, 35) = 5 .

Příklad 1.2.5 Nalezněte největšího společného dělitele čísel 1 694, 3146, 858, 231 . Řešení. Strukturu výpočtu lze znázornit následujícím schématem, jehož jednotlivé mezivýpočty jsou realizovány pomocí Eukliedova algoritmu: 1 694 d 2 = NSD (1 694, 3 146 ) …

3 146

858

231

242

d 3 = NSD (d 2 ,858) …

22

d 4 = NSD (d 3 ,231) …

11

Tedy NSD(1 694, 3146, 858, 231) = d 4 = 11 . Ke stejnému výsledku samozřejmě dospějeme i v případě následujícího postupu: 1 694

3 146

858

242

231 33

11 Analogickým postupem jako v příkladu 1.2.4 zjistíme hodnoty celočíselných koeficientů xi ze vztahu (1.13). Dostáváme x1 = 2, x 2 = −1, x3 = −21, x 4 = 77 , tedy NSD(1 694, 3146, 858, 231) = 1694 ⋅ 2 + 3146 ⋅ (− 1) + 858 ⋅ (− 21) + 231 ⋅ 77 = 11 . ¶


strana 16

Nyní se krátce zastavme u společných násobků dvou nenulových přirozených čísel. Označme D libovolný společný násobek čísel a, b . Lze tedy psát D = a ⋅ q , kde q ∈ N . Vzhledem

k tomu, že čísla a, b lze vyjádřit ve tvaru a = a1 ⋅ NSD (a, b ) , b = b1 ⋅ NSD(a, b ) , kde NSD(a1 , b1 ) = 1 , je číslo

Lze tak psát

D = a1 ⋅ q přirozené a navíc q je dělitelné (beze zbytku) b1 . NSD (a, b )

a1 ⋅ q = a1 ⋅ n , kde n ∈ N a tedy a1 ⋅ q = a1 ⋅ b1 ⋅ n . Několika snadnými úpravami b1

získáme obecné vyjádření všech společných násobků čísel a, b ve tvaru D=

a ⋅b ⋅n, NSD (a, b )

(1.14)

kde n ∈ N . Navíc je zřejmé, že pro nejmenší společný násobek dvou čísel platí NSN (a, b ) =

a ⋅b . NSD (a, b )

(1.15)

V případě, kdy čísla a, b jsou nesoudělná dostáváme NSN (a, b ) = a ⋅ b .

Příklad 1.2.6 Určete: a) nejmenší společný násobek čísel 420 a 36, b) nejmenší společný násobek D větší než 333 333. Řešení. ad a) Přímou aplikací vztahu 1.15 dostáváme NSN (420,36) =

420 ⋅ 36 . Z příkladu NSD(420,36)

1.2.2 část a) víme, že NSD(420, 36 ) = 12 , tedy NSN (420,36 ) = 1 260 . ad b) Ze vztahu (1.14) vyplývá, že všechny společné násobky jsou tvaru 1 260 ⋅ n, n ∈ N a hledanému společnému násobku tak odpovídá n, které je nejmenším řešením (v oboru  333 333  přirozených čísel) nerovnice 1 260 ⋅ n ≥ 333 333 . Odtud n =   = 265 , tedy  1260  D = 333 900 . ¶

Analogický, jako v případě společného dělitele a nejmenšího společného dělitele, lze rozšířit pojmy společný násobek a nejmenší společný násobek na případ více než dvou čísel.


strana 17

Definice 1.2.4 – společný násobek, nejmenší společný násobek a1 ,… , a n Společným násobkem nenulových celých čísel a1 ,… , a n , kde n ≥ 2 , nazveme nenulové přirozené číslo D, které je dělitelné každým z čísel a1 ,… , a n , tj. ∀i ∈ {1,… , n} ai | D . Nejmenším společným násobkem nenulových celých čísel a1 ,… , a n pak nazveme takový jejich společný násobek, který je nejmenší (existuje vždy a jediný). ¶

Poznámka 1.2.2 ♦

Úlohu na výpočet nejmenšího společného násobku více než dvou přirozených čísel a1 ,… , a n , převádíme na opakovaný výpočet nejmenšího společného násobku dvou čísel

dle schématu: D2 = NSN (a1 , a 2 ) ,

D3 = NSN (D2 , a3 ) , D4 = NSN (D3 , a 4 ) , Dn = NSN (Dn −1 , a n ) ,

kde NSN (a1 ,… , a n ) = Dn . POZOR! Nejmenší společný násobek více než dvou čísel nelze obecně počítat jako v případě dvou čísel, tj. jejich součin dělený jejich největším společným dělitelem. ♦

Jsou-li čísla a1 ,… , a n po dvou nesoudělná, potom NSN (a1 ,… , a n ) = a1 ⋅ … ⋅ a n . POZOR! Předpoklad nesoudělnosti po dvou nelze pro n > 2 nahradit předpokladem pouhé nesoudělnosti.

♦

Snadno zjistíme, že pro nejmenší společný násobek tří čísel platí NSN (a, b, c ) =

a ⋅ b ⋅ c ⋅ NSD(a, b, c ) . NSD (a, b ) ⋅ NSD (a, c ) ⋅ NSD (b, c )

(1.16)

¶

Příklad 1.2.7 Vypočtěte nejmenší společný násobek čísel a) 420, 36, b) 1 694, 3 146, 858 a 231. ad a) Aplikací vztahu (1.15) dostáváme NSN (420,36) =

420 ⋅ 36 . Z příkladu 1.2.2 NSD(420,36)

část a) víme, že NSD(420, 36 ) = 12 , tedy NSN (420,36 ) = 1 260 .


strana 18

ad b) Postup výpočtu nejmenšího společného násobku čtyř čísel lze znázornit následujícím schématem, jehož jednotlivé kroky spočívají ve výpočtu nejmenšího společného násobku dvou čísel a které realizujeme dle vztahu (1.15): 1 694 D2 = NSN (1 694, 3 146 )…

3 146

858

231

22 022

D3 = NSN (D2 ,858) …

66 066

D4 = NSN (D3 ,231) …

66 066

Tedy NSN (1 694, 3 146, 858, 231) = D4 = 66 066 . Ke stejnému výsledku samozřejmě dospějeme i v případě následujícího postupu: 1 694

3 146

22 022

858

231 6 006

66 066 ¶


strana 19

1.3

Prvočísla a prvočíselné rozklady

Zkoumáme-li počet dělitelů kladných přirozených čísel snadno zjistíme, že některá přirozená čísla větší než jedna mají pouze dva dělitele - nevlastní dělitelé (číslo jedna a sebe sama), kdežto ostatní mají i vlastní dělitele. Odtud následující definice pojmu prvočíslo.

Definice 1.3.1 – prvočíslo, složené číslo Přirozené číslo p > 1 nazveme prvočíslem, jestliže

(∀a ∈ N )(a | p → a = 1 ∨ a = p ), tj. číslo p má pouze nevlastní dělitele. Ostatní kladná přirozená čísla větší než jedna nazýváme čísla složená. ¶

Příklad 1.3.1 Čísla 2, 3, 5, 7 jsou prvočísla, neboť všechna mají pouze nevlastní dělitele. Naopak, čísla 4, 6, 189, 222 jsou čísla složená, neboť mají vlastní dělitele, např. 2 | 4, 3| 6, 7 |189, 37 | 222 . Ovšem mnohem obtížnější je zjistit, že např. číslo 162 259 276 829 213 363 391 578 010 288 127 je prvočíslo, kdežto 340 282 366 920 938 463 463 374 607 431 768 211 457 je číslo složené. ¶

Věta 1.3.1 – Eukleides Existuje nekonečně mnoho prvočísel. Důkaz. Sporem.

Předpokládejme,

že

existuje

konečně

prvočísel

p1 ,… , p n

a

položme

p = p1 ⋅ … ⋅ p n + 1 . Zřejmě p ≠ pi , i = 1,… , n , tudíž p je číslo složené a musí být proto

dělitelné některým z prvočísel p1 ,… , p n , předpokládejme p j . Jistě platí, že p j | p i p j | p1 ⋅… ⋅ p n . Z věty 1.1.1 část g) tak dostáváme p j |1 . Spor, existuje tedy nekonečně mnoho prvočísel. ¶


strana 20

Poznamenejme, že existuje celá řada dalších různě rafinovaných důkazu existence nekonečně mnoha prvočísel, které odkrývají mnohdy překvapivé souvislosti. Některé jednoduché jsou obsaženy ve Sbírce příkladů z diskrétní matematiky, TUL 2002.

Poznámka 1.3.1 ♦

Nejmenší od jedničky různý dělitel složeného čísla n je prvočíslo, které je nejvýše rovno

 n  . (Dokažte!) ♦

Je-li p prvočíslo takové, že p | a ⋅ b , potom p| a nebo p| b . (Dokažte!)

♦

Všechna prvočísla vyskytující se v množině

{2,… , n}

lze nalézt pomocí algoritmu

(nazývaného Eratosthenovo síto), který lze formulovat následovně: 1. Označ první nevyškrtnuté a ještě neoznačené číslo. Toto číslo p je prvočíslo. Je-li p≤

 n , jdi na krok 2., jinak ukonči algoritmus a nevyškrtnutá čísla jsou právě

všechna hledaná prvočísla. 2. Vyškrtni všechny násobky čísla p, počínaje p 2 . Po jejich vyškrtnutí jdi na krok 1. (Uvedené kroky algoritmu řádně zdůvodněte!) Výše popsaný algoritmus (Eratosthenes, 276 – 195 př. n. l.) je pravděpodobně historicky první metoda umožňující „generovat“ posloupnost prvočísel.

Příklad 1.3.2 Pomocí Eratosthenova síta nalezněte všechna prvočísla, která jsou menší nebo rovna 50. Řešení. V tabulce obsahující čísla 2,… , 50 aplikujeme výše popsaný algoritmus. Dostáváme tak následující tabulky, jejichž obsah postupně odpovídá jednotlivým krokům algoritmu: Vyškrtnutí násobků 2 (počínaje od 2 2 ) 2 9

3

5 11

17 23

13 19

25 31

37

7


47

17 29

23

35 41

7 13

19 25

29

31 43

49

5

3

11

21

33

45

2

15

27

39

Vyškrtnutí násobků 3 (počínaje od 3 2 )

35

37

41 47

43 49

strana 21

Vyškrtnutí násobků 5 (počínaje od 5 2 ) 2

3

7

5

11 17

Vyškrtnutí násobků 7 (počínaje od 7 2 ) 2

3

13

5

11

19

17

23

29

7

13 19

23

31

29 31

37

41 47

43 49

37

41

43

47

Všechna prvočísla v řadě 2,… , 50 jsou nalezena po vyškrtnutí násobků čísla 7 a jsou obsažena v poslední tabulce. ¶

V dalších úvahách hraje klíčovou roli následující věta, označovaná často jako Základní věta aritmetiky.

Věta 1.3.2 Každé přirozené číslo větší než jedna lze rozložit na součin prvočísel, a to jednoznačně, nepřihlížíme-li k pořadí prvočísel. Důkaz. Je třeba dokázat dvě skutečnosti - existenci prvočíselného rozkladu a jeho jednoznačnost. Označme a libovolné složené přirozené číslo větší než jedna (v případě, že a je prvočíslo, věta evidentně platí). Dle první části poznámky 1.3.1 existuje prvočíslo p1 , které je dělitelem a, tj. a = p1 ⋅ a1 , kde 1 < a1 < a . Pokud a1 je prvočíslo, dostali jsme již hledaný rozklad.

V opačném případě, kdy číslo a1 je složené, opět využijeme první část poznámky 1.3.1 a tedy existuje prvočíselný dělitel p 2 čísla a1 , tj. a1 = p 2 ⋅ a 2 , kde 1 ≤ a 2 < a1 . Je-li a 2 složené číslo větší než 1, postup opakujeme (jinak jsme nalezli požadovaný rozklad), dokud nenastane situace, kdy a k je prvočíslo, nebo a k = 1 . Vzhledem k tomu, že čísla ai tvoří klesající posloupnost přirozených čísel, musí tato situace skutečně nastat. Odtud již plyne existence prvočíselného rozkladu a = p1 ⋅ … ⋅ p k . Předpokládejme nyní, že a = p1 ⋅ … ⋅ p k = q1 ⋅ … ⋅ ql jsou dva prvočíselné rozklady čísla a. Zřejmě ∀i ∈ {1,… , k } pi | q1 ⋅ … ⋅ ql . Dle druhé části poznámky 1.3.1 musí existovat j takové, že pi = q j . Odtud k = l a po případném přečíslování dostáváme ∀i ∈ {1,… , k } pi = qi . ¶


strana 22

Jako zřejmý důsledek věty 1.3.2 dostáváme, že každé přirozené číslo a > 1 lze jednoznačně vyjádřit ve tvaru a = p1α1 ⋅ … ⋅ p kα k ,

(1.17)

pi , i = 1,… , k jsou všechna navzájem různá prvočísla (seřazená vzestupně), která se

kde

vyskytují v rozkladu čísla a, α i ∈ N + , i = 1,… , k (tzv. násobnost prvočísla pi v rozkladu a). Výraz (1.17) se nazývá kanonický rozklad přirozeného čísla a. (Často budeme používat kratší označení „rozklad“ místo „kanonický rozklad“.)

Věta 1.3.3 Nechť a = p1α1 ⋅ … ⋅ p kα k , b = q1β1 ⋅ … ⋅ qlβl jsou kanonické rozklady. Potom platí: a) Každý dělitel d čísla a má kanonický rozklad d = p1δ1 ⋅ … ⋅ p kδ k ,

(1.18)

kde δ i ∈ N , 0 ≤ δ i ≤ α i , i = 1,… , k . b) Největší společný dělitel čísel a, b má kanonický rozklad NSD(a, b ) = r1γ1 ⋅ … ⋅ rhγ h ,

(1.19)

kde r1 ,…, rh jsou prvočísla společná kanonickým rozkladům čísel a, b, γ i je minimum z exponentů, se kterým se prvočíslo ri vyskytuje v kanonických rozkladech čísel a, b. c) Nejmenší společný násobek čísel a, b má kanonický rozklad NSN (a, b ) = r1λ1 ⋅ … ⋅ rmλ m ,

(1.20)

kde r1 ,…, rm jsou prvočísla vyskytující se v alespoň jednom kanonickém rozkladu, λ i je maximum z exponentů, se kterým se prvočíslo ri vyskytuje v kanonických rozkladech čísel a, b. Důkaz. ad a) Jelikož d | a , mohou se v kanonickém rozkladu dělitele d vyskytovat pouze prvočísla z kanonického rozkladu a (viz druhá část poznámky 1.3.1), navíc s exponentem, který je nejvýše rovnen exponentu z rozkladu a. ad b) Jelikož NSD(a, b ) dělí a i b, musí jeho kanonický rozklad obsahovat pouze prvočísla,


strana 23

která se vyskytují současně v obou kanonických rozkladech, navíc s exponentem rovným právě menšímu z exponentů. ad c) Jelikož a i b dělí NSN (a, b ) , musí se každé prvočíslo z rozkladů a, b vyskytovat také v rozkladu NSN (a, b ) , navíc žádné jiné prvočíslo se v rozkladu NSN (a, b ) vyskytovat nemůže (jinak nejde o nejmenší společný násobek). Exponenty jednotlivých prvočísel v rozkladu

NSN (a, b )

jsou

zřejmě

rovny

jejich

maximálnímu

exponentu

vyskytujícímu se v rozkladech čísel a, b. ¶

Příklad 1.3.3 Pomocí kanonických rozkladů čísel a = 7 875, b = 3 900, c = 82 500 určete všechny dělitele čísla a, NSD(a, b, c ) , NSN (a, b, c ) . Řešení. Nejprve je třeba nalézt kanonické rozklady uvedených čísel. Tyto rozklady určíme tak, že uvedená čísla zkoušíme dělit prvočísly (dělení zvoleným prvočíslem opakujeme, dokud je zbytek nulový). Dostáváme tak a = 3 2 ⋅ 5 3 ⋅ 7, b = 2 2 ⋅ 3 ⋅ 5 2 ⋅ 13, c = 2 2 ⋅ 3 ⋅ 5 4 . Všechny dělitele čísla a jsou tvaru d = 3δ1 ⋅ 5 δ 2 ⋅ 7 δ3 , kde 0 ≤ δ1 ≤ 2, 0 ≤ δ 2 ≤ 3, 0 ≤ δ 3 ≤ 1 a jsou obsaženy v následující tabulce. 1 105

3 125

5 175

7 225

9 315

15 375

21 525

25 35 45 63 75 875 1125 1575 2625 7875

Z věty 1.3.3 víme, že kanonický rozklad NSD(a, b, c ) obsahuje pouze prvočísla společná oběma kanonickým rozkladům, tj. 3 a 5. Exponenty jsou rovny minimu z exponentů, se kterými se vyskytují v kanonických rozkladech čísel a, b, c. Odtud NSD(a, b, c ) = 3 ⋅ 5 2 = 75 . (Nalezněte všechny společné dělitele čísel a, b, c.) Dále víme (opět věta 1.3.3), že kanonický rozklad NSN (a, b, c ) obsahuje všechna prvočísla, která se vyskytují v kanonickém rozkladu alespoň jednoho z čísel a, b, c, tj. 2, 3, 5, 7, 11 a 13. V tomto případě se exponenty rovnají maximu z exponentů. Odtud NSN (a, b, c ) = 2 2 ⋅ 3 2 ⋅ 5 4 ⋅ 7 ⋅ 11 ⋅ 13 = 22 522 500 . ¶


strana 24

Poznámka 1.3.2 Jedním z fundamentálních problémů teorie čísel je otázka rozložení prvočísel v množině všech přirozených čísel. Některé základní výsledky lze formulovat následovně (tabulka v příloze obsahuje prvních 840 prvočísel): ♦

Existuje nekonečně mnoho libovolně dlouhých posloupností po sobě jdoucích složených čísel, tj. neobsahující žádné prvočíslo (dokažte!).

♦

Pro libovolná nesoudělná přirozená čísla a, m existuje nekonečně mnoho prvočísel p, která při dělení číslem m dávají zbytek a, tedy jsou tvaru p = m ⋅ q + a , kde q ∈ N (C. F. Gauss).

♦

Označíme-li π(n ) počet prvočísel menších nebo rovných přirozenému číslu n, platí π(n ) ≅

n , ln n

(1.21)

kde symbol ≅ chápeme jako přibližnou rovnost (přesněji, limita podílu obou stran je pro n → ∞ rovna 1). Hodnoty obou stran vztahu (1.21) jsou pro vybraná n obsaženy

v následujících tabulkách: n

π(n )

10 20 30 40 50 60 70 80 90 100

4 8 10 12 15 17 19 22 24 25

n

ln n 4 7 9 11 13 15 16 18 20 22

n

π(n )

100 000 200 000 300 000 400 000 500 000 600 000 700 000 800 000 900 000 1 000 000

9 592 17 984 25 997 33 860 41 538 49 098 56 543 63 951 71 274 78 498

n

ln n 8 686 16 385 23 788 31 010 38 103 45 097 52 010 58 857 65 645 72 382

Příklad 1.3.4 Dokažte speciální variantu obecného Gaussova tvrzení (poznámka 1.3.2), že existuje nekonečně mnoho prvočísel tvaru 4q + 3 . Řešení. Důkaz provedeme analogicky k důkazu věty 1.3.1, tj. sporem.


strana 25

Nejprve si uvědomme, že každé prvočíslo větší než 2 dává při dělení číslem 4 zbytek 1, nebo 3. Nyní předpokládejme, že existuje pouze konečně prvočísel p1 ,… , p n uvažovaného tvaru 4q + 3 (určitě taková existují, např. 3, 7, 11, 19, 23 apod.) a položme p = 4 p1 ⋅ … ⋅ p n − 1 . Je zřejmé, že číslo p dává při dělení 4 zbytek 3, navíc není dělitelné žádným z prvočísel p1 ,… , p n (jinak by dané prvočíslo muselo dělit 1). Vzhledem k tomu, že součin čísel tvaru 4q + 1 je opět číslo téhož tvaru (dokažte!), musí být číslo p dělitelné prvočíslem tvaru 4q + 3 různým od p1 ,… , p n . Spor, existuje tedy nekonečně mnoho prvočísel tvaru 4q + 3 . ¶

Velmi významnou roli v teorii čísel a v celé řadě aplikací, např. moderní teorie kódování, testy superpočítačů apod. (podrobnosti přesahují rámec těchto skript, relevantní internetovské odkazy viz příloha), hraje problematika kanonických rozkladů velkých čísel, resp. testy jejich prvočíselnosti. V tomto kontextu se nejčastěji vyskytují čísla speciálních tvarů, např. Fermatova, Mersennova a Cunninghamova čísla.

Definice 1.3.2 - Fermatova a Mersennova čísla n

Fermatovými čísly nazýváme čísla Fn = 2 2 + 1 , kde n ∈ N a Mersennovými čísly nazýváme čísla M n = 2 n − 1 , kde n ∈ N . ¶

Poznámka 1.3.3 - Fermatova a Mersennova prvočísla ♦

Fermatova čísla

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65 537

jsou prvočísla (tzv.

Fermatova prvočísla). Tato skutečnost vedla vynikajícího francouzského matematika Pierre de Fermat (1601-1695) k vyslovení hypotézy, že všechna Fermatova čísla jsou prvočísla. Teprve později byla tato hypotéza vyvrácena Leonardem Eulerem, který ukázal, že číslo F 5= 4 294 967 297 je složené. Nyní panuje obecné přesvědčení, že všechna Fermatova čísla Fn , n ≥ 5 jsou čísla složená. Ovšem ani v dnešní době výpočetní techniky není snadné prokázat, že pro některou konkrétní hodnotu n je Fn číslo složené (proč?). Například doposud nebylo zjištěno, zda F24 je skutečně číslo složené a u F12 (o kterém je prokázáno, že je složené) nebyl nalezen jeho kanonický rozklad (pro studenty informatiky rozhodně zajímavá výzva).


strana 26

♦

Historicky neméně zajímavá a z hlediska aplikací velmi významná jsou tzv. Mersennova prvočísla (Marin Mersenne, 1588-1648), tj. prvočísla tvaru 2 p − 1 , kde p je prvočíslo (jde tedy o speciální Mersennova čísla). Lze ukázat, že pokud p není prvočíslo, nemůže být ani 2 p − 1 prvočíslo. Obrácené tvrzení ovšem neplatí (je-li p prvočíslo, potom 2 p − 1 být prvočíslem může, ale nemusí). V současné době se předpokládá (není ovšem dokázáno), že mezi všemi čísly tvaru 2 p − 1 , kde p je prvočíslo, existuje nekonečně mnoho Mersennových

prvočísel,

ale

M 2 , M 3 , M 5 , M 7 , M 13 , M 17 , M 19 , M 31

i

čísel jsou

složených. Mersennova

Například prvočísla,

čísla kdežto

M 11 , M 67 , M 257 jsou čísla složená. Největší v současné době (rok 2001) známé Mersennovo prvočíslo je M 6 972 593 = 2 6 972 593 − 1 (to ovšem neznamená, že o všech číslech M p , kde p je prvočíslo menší než 6 972 593 je známo zda jsou prvočíslem). Vzhledem k tomu, že pro Mersennova čísla existují efektivní testy jejich prvočíselnosti (např. LucasLehmerův test), může jít opět o zajímavý námět pro studenty (viz internetovské odkazy v příloze). Pro zajímavost uveďme, že prvočíselnost M 1 257 787 byla prokázána na superpočítači Cray T-94, ovšem prvočíselnost M 6 972 593 již na pouhém PC Pentium 350MHz. ¶


strana 27

1.4

Základní aritmetické funkce

V teorii čísel a v jejich aplikacích hrají významnou roli funkce, jejichž definiční obory tvoří kladná přirozená čísla N + . Pro takové funkce se vžilo označení aritmetické funkce.

Definice 1.4.1 – multiplikativní funkce Řekneme, že aritmetická funkce f je multiplikativní, jestliže: ♦

∃n ∈ N + takové, že f (n ) ≠ 0 ,

♦

∀m, n ∈ N + platí NSD(m, n ) = 1  → f (m ⋅ n ) = f (m ) ⋅ f (n ) . ¶

(1.22)

Základní vlastnosti multiplikativních funkcí popisuje následující věta.

Věta 1.4.1 a) Je-li f multiplikativní funkce, potom f (1) = 1 . b) Součin multiplikativních funkcí je multiplikativní funkce. c) Je-li f multiplikativní, n = p1α1 ⋅ … ⋅ pkα k kanonický rozklad, potom

∑ f (d ) = (1 + f ( p ) + f ( p ) + … + f ( p ))⋅ … ⋅ (1 + f ( p ) + f ( p ) + … + f ( p )) . 1

2 1

α1 1

k

2 k

αk k

(1.23)

d |n

(Součet na levé straně se provádí přes všechny dělitele d čísla n.) Důkaz. ad a) Z multiplikativnosti plyne existence n ∈ N + takového, že f (n ) ≠ 0 , navíc zřejmě NSD(n, 1) = 1 . Ze vztahu (1.22) vyplývá f (n ) = f (n ⋅ 1) = f (n ) ⋅ f (1) a po vydělení

nenulovou hodnotou f (n ) dostáváme dokazovaný vztah. ad b) Označme f = f1 ⋅ f 2 , kde f1 , f 2 jsou multiplikativní funkce. Zřejmě f (1) = f1 (1) ⋅ f 2 (1) = 1 a tedy zbývá dokázat platnost (1.22). Předpokládejme proto, že NSD(m, n ) = 1 . Dostáváme (aplikací vztahu (1.22) na funkce f1 , f 2 ) f (m ⋅ n ) = f1 (m ⋅ n ) ⋅ f 2 (m ⋅ n ) = f1 (m ) ⋅ f1 (n ) ⋅ f 2 (m ) ⋅ f 2 (n ) = = f1 (m ) ⋅ f 2 (m ) ⋅ f1 (n ) ⋅ f 2 (n ) = f (m ) ⋅ f (n ) ,

což bylo třeba dokázati.


strana 28

(

δ

)

ad c) Jelikož NSD piδi , p j j = 1 , pro i ≠ j , je po roznásobení pravá strana dokazovaného vztahu zřejmě rovna (využijeme multiplikativnost)

∑ f) ( p )⋅… ⋅ f ( p ) =

(δ1 ,…,δ n

∑ f) ( p

δn n

δ1 1

0≤ δ1 ≤ α1 , , 0≤ δ n ≤ α n

(δ1 ,…,δ n

δ1 1

)

⋅ … ⋅ p nδ n .

0 ≤ δ1 ≤ α1 , , 0 ≤ δ n ≤ α n

Jelikož dělitelé d čísla n jsou dle věty 1.3.3 právě tvaru d = p1δ1 ⋅ … ⋅ p kδ k , kde

0 ≤ δ i ≤ α i , i = 1,… , n je vztah (1.23) dokázán. ¶

Poznámka 1.4.1 – počet dělitelů, součet dělitelů Aritmetická funkce f

∑d

r

r

(n ) = n r , n ∈ N +

je multiplikativní (dokažte!) a dle vztahu (1.23) platí

(

(

)

)

= 1 + p1r + p12 r + … + p1α1r ⋅ … ⋅ 1 + p kr + p k2 r + … + p kα k r .

d |n

Odtud volbou r = 0 dostáváme vztah pro počet dělitelů čísla n τ(n ) = ∑1 = (1 + … + 1) ⋅ … ⋅ (1 + … + 1) , d |n

α1 +1

α k +1

tj. τ(n ) = (α 1 + 1) ⋅ … ⋅ (α k + 1) .

(1.24)

Volbou r = 1 dostáváme vztah pro součet dělitelů čísla n

(

)

(

)

S (n ) = ∑ d = 1 + p1 + p12 + … + p1α1 ⋅ … ⋅ 1 + p k + p k2 + … + p kα k , d |n

tj.  p α k +1 − 1  − 1   ⋅… ⋅  k   p −1  . − p 1  1   k  

α1 +1

p S (n ) =  1

(1.25)

Příklad 1.4.1 Určete počet a součet všech dělitelů čísla 15 120. Řešení. Snadno zjistíme, že kanonický rozklad daného čísla je 15 120 = 2 4 ⋅ 33 ⋅ 5 ⋅ 7 . Pro počet dělitelů tak dostáváme τ(15 120 ) = (4 + 1) ⋅ (3 + 1) ⋅ (1 + 1) ⋅ (1 + 1) = 80

a součet dělitelů  2 4+1 − 1   33+1 − 1   51+1 − 1   71+1 − 1   = 59 520 . ¶  ⋅   ⋅   ⋅  S (15 120 ) =   2 −1   3 −1   5 −1   7 −1  Diskrétní matematika II

strana 29

Definice 1.4.2 - Möbiova funkce Aritmetickou funkci µ(n ) definovanou vztahy ♦

µ(1) = 1 ,

♦

µ(n ) =

0 , pokud existuje přirozené číslo d > 1 takové, že d 2 | n ,

(− 1)k , v ostatních případech, kde k je počet prvočísel vyskytujících se v kanonickém rozkladu n, nazýváme Möbiovou funkcí. ¶

Z definice je patrné, že hodnoty µ(n ) snadno určíme z kanonického rozkladu čísla n = p1α1 ⋅ … ⋅ pkα k . Jsou-li totiž všechna α i = 1 , potom µ(n ) = (− 1) a pokud alespoň jedno k

α i ≥ 2 je µ(n ) = 0 .

Věta 1.4.2 Möbiova funkce je multiplikativní a pro n > 1 platí

∑ µ(d ) = 0 . d |n

Důkaz. K důkazu první části tvrzení (multiplikativita) stačí ukázat platnost vztahu (1.22). Jsou-li m, n nesoudělná, potom je počet prvočísel v kanonickém rozkladu součinu m ⋅ n roven součtu počtu prvočísel v rozkladu m plus počet prvočísel v rozkladu n, navíc jejich exponenty se nemění. V druhé části (s ohledem na již dokázanou multiplikativitu) stačí využít vztah (1.23). Pro n > 1 tak zřejmě dostáváme

∑ µ(d ) = (1 + (− 1) + 0 + … + 0) ⋅ … ⋅ (1 + (− 1) + 0 + … + 0) = 0 . ¶ d |n

Definice 1.4.3 - Eulerova funkce Aritmetickou funkci ϕ(n ) definovanou vztahy ♦

ϕ(1) = 1 ,

♦

ϕ(n ) = k , kde k je počet čísel v řadě 1,… , n , která jsou nesoudělná s n,

nazýváme Eulerovou funkcí. ¶


strana 30

Z definice snadno zjistíme, že pro libovolné prvočíslo p platí ϕ( p ) = p − 1 (zdůvodněte!). V případě složených čísel je výpočet hodnoty Eulerovy funkce obtížnější.

Věta 1.4.3 a) Je-li n = p1α1 ⋅ … ⋅ pkα k kanonický rozklad, potom

(

(

)

)

ϕ(n ) = p1α1 − p1α1 −1 ⋅ … ⋅ p kα k − p kα k −1 .

(1.26)

b) Eulerova funkce je multiplikativní. c) Platí

∑ ϕ(d ) = n .

(1.27)

d |n

Důkaz. ad a) Onačme P ( A) pravděpodobnost, že náhodně zvolené číslo z množiny {1,… , n} je nesoudělné s n. S ohledem na definici Eulerovy funkce a klasickou definici pravděpodobnosti platí P ( A) =

ϕ(n ) . n

(∗)

Nesoudělnost s n je zřejmě ekvivalentní s nedělitelností žádným z prvočísel p1 ,… , p k vyskytujících se v kanonickém rozkladu n a tedy

( )

( )

P( A) = P A p1 ⋅ … ⋅ P A pk ,

(∗∗)

( ) je pravděpodobnost, že náhodně zvolené číslo z množiny {1,…, n} není dělitelné prvočíslem p . Nyní pravděpodobnost P(A ) vyjádříme pomocí doplňku, tj. kde P A pi

i

pi

( )

( )

P A pi = 1 − P A pi ,

( )

kde P A pi

je pravděpodobnost, že náhodně zvolené číslo z množiny {1,… , n} je

dělitelné prvočíslem pi . Z klasické definice snadno dostáváme (každé pi - té číslo v řadě 1,… , n je dělitelné pi )

( )

P A pi

n   p  1 i = = , n pi

tedy

( )

P A pi = 1 −


1 . pi

(∗∗∗)

strana 31

Dosazením (∗) a (∗∗∗) do (∗∗) dostáváme  ϕ(n )  1  1  , = 1 −  ⋅ … ⋅ 1 − n p1  p k   

a odtud je platnost dokazovaného vztahu evidentní. ad b) Jsou-li m, n nesoudělná, potom se prvočísla a jejich exponenty v kanonickém rozkladu součinu m ⋅ n shodují s prvočísly a jejich exponenty v kanonickém rozkladu čísla m, resp. n. Zbytek důkazu je zřejmým důsledkem vztahu (1.26). ad c) Využitím vztahů (1.23), (1.26) a již dokázané multiplikativity dostáváme   ϕ(d ) = 1 + ( p1 − 1) + p12 − p1 + … + p1α1 − p1α1 −1 ∑ d |n  ϕ ( p1 ) ϕ ( p12 ) ϕ ( p1α1 )  p1α1

(

(

)

   ⋅…  

)

  … ⋅ 1 + ( pk − 1) + pk2 − pk + … + pkα k − pkα k −1  α ϕ( p k ) ϕ ( p k2 ) ϕ( pk k )  pkαk

(

)

(

  =  

)

a tedy

∑ ϕ(d ) = p

α1 1

⋅ … ⋅ p kα k = n . ¶

d |n

Příklad 1.4.2 Určete hodnotu Möbiovy a Eulerovy funkce v bodech 13 799 247 a 24 538 437. Řešení. Prvním krokem je určení kanonických rozkladů. Platí 13 799 247 = 3 ⋅ 7 ⋅ 11 ⋅ 31 ⋅ 41 ⋅ 47 ,

24 538 437 = 33 ⋅ 7 ⋅ 112 ⋅ 29 ⋅ 37 .

Přímo z definice Möbiovy funkce dostáváme µ(13 799 247 ) = (− 1) = 1 , 6

neboť v kanonickém rozkladu se vyskytuje 6 prvočísel a každé s exponentem 1, dále µ(24 538 437 ) = 0 ,

neboť v kanonickém rozkladu se vyskytuje alespoň jedno prvočíslo s exponentem větším než 1 (prvočísla 3 a 11). Hodnotu Eulerovy funkce určíme ze vztahu (1.26). Dostáváme tak ϕ(13 799 247 ) = (3 − 1) ⋅ (7 − 1) ⋅ (11 − 1) ⋅ (31 − 1) ⋅ (41 − 1) ⋅ (47 − 1) = 6 624 000


strana 32

a

(

)

(

)

ϕ(24 538 437 ) = 33 − 3 2 ⋅ (7 − 1) ⋅ 112 − 11 ⋅ (29 − 1) ⋅ (37 − 1) = 11 975 040 . ¶

Poznamenejme, že v příloze lze nalézt tabulky s hodnotami Möbiovy a Eulerovy funkce pro hodnoty n ≤ 830 , které lze spolu s multiplikativitou vhodně využít k výpočtům. Například ϕ(35 100 ) = ϕ(351) ⋅ ϕ(100 ) ,

neboť NSD(351,100 ) = 1 . V tabulkách snadno nalezneme ϕ(351) = 216 a ϕ(100 ) = 40 , tedy ϕ(35 100) = 8 640 .

Kromě aritmetických funkcí hrají v diskrétní matematice významnou roli také funkce nazývané dolní celá část, horní celá část a lomená část. Jsou definovány následovně: ♦

Funkce dolní celá část x, kde x ∈ R , je definována jako největší celé číslo menší nebo rovné x. Tuto funkci budeme označovat symbolem x  (někdy se používá i kratší název celá část x) a lze ji definovat následujícími vlastnostmi:

♦

-

∀x ∈ R x  ∈ Z ,

-

∀x ∈ R

x  ≤ x < x  + 1 .

Funkce horní celá část x, kde x ∈ R , je definována jako nejmenší celé číslo větší nebo rovné x. Tuto funkci budeme označovat symbolem x  a lze ji definovat vlastnostmi:

♦

-

∀x ∈ R x  ∈ Z ,

-

∀x ∈ R x  − 1 < x ≤ x  .

Funkci lomená část x, kde x ∈ R , budeme označovat symbolem {x}. Tato funkce je definována vztahem {x} = x − x  .

Příklad 1.4.3

5 = 5

5 = 5

− 5 = −5

− 5 = −5

4,75 = 4

4,75 = 5

− 4,75 = −5

− 4,75 = −4

6,01 = 6

6,01 = 7

− 6,01 = −7

− 6,01 = −6

5,2 + 3,1 = 8 = 5,2 + 3,1

5,2 + 3,1 = 9 < 5,2 + 3,1 = 10

4,8 + 3,4 = 8 > 4,8 + 3,4 = 7

4,8 + 3,4 = 9 = 4,8 + 3,4 . ¶


strana 33

Poznámka 1.4.2 ♦

Některé často využívané vlastnosti funkcí dolní a horní celá část jsou (dokažte!): x − 1 < x  ≤ x ≤ x  < x + 1 ,

− x  = − x  ,

− x  = − x  ,

x + n = x  + n, n ∈ N ,

x + n = x  + n, n ∈ N ,

 n  n  ∑ x i  ≥ ∑ x i  ,  i =1  i =1

 n  n  ∑ x i  ≤ ∑ x i  .  i =1  i =1

Pro názornost následují grafy funkcí dolní celá část, horní celá část a lomená část.

-3

-2

-1

x 3 

3

2

2

1

1

0

1

2 x 3

-3

-1

0 -1

-2

-2

-3

-3

2

-2

-1

x 

1

2 x 3

{x}

1 -3

-2

-1

0

1

2 x 3

-1 -2


strana 34

1.5

Řetězové zlomky

Je všeobecně známé, že při numerických výpočtech vždy pracujeme s racionálními čísly, resp. s jejich jistou podmnožinou. V tomto kontextu hraje důležitou roli problematika tzv. diofantické aproximace, která, zjednodušeně řečeno, zkoumá, jak přesně lze dané číslo (nejčastěji iracionální) aproximovat pomocí racionálních čísel určitých vlastností. K této problematice má úzký vztah i tato podkapitola týkající se řetězových zlomků. Snadno totiž zjistíme, že každé číslo α ∈ R − Z (v případě celých čísel je situace triviální), lze vyjádřit jediným způsobem ve tvaru

α = q0 +

1 , α1

kde q 0 = α  ∈ Z (největší celé číslo menší nebo rovné α ) a 1 < α 1 . Pokud α 1 není přirozené číslo, lze postupovat analogicky i v tomto případě, tj. psát α 1 = q1 +

1 , α2

kde q1 = α 1  a 1 < α 2 . Odtud α = q0 +

1 1 q1 + α2

.

Naznačený postup lze samozřejmě opakovat, dokud v některém kroku (např. i v prvním) nedostaneme α n ∈ N + (jak uvidíme později, tato situace nemusí nastat). Tím se již dostáváme k pojmu rozvoj čísla α v řetězový zlomek.

Definice 1.5.1 Řetězovým zlomkem nazveme (konečný nebo nekonečný) výraz tvaru q0 +

1 q1 +

,

1

(1.28)

q2 + +

1 qn +

1

kde q 0 ∈ Z , qi ∈ N + . ¶


strana 35

Čísla qi se nazývají členy rozvoje (v řetězový zlomek) a výrazy δ 0 = q 0 , δ1 = q 0 +

1 , … , δ n = q0 + q1

1 q1 +

,…

1

(1.29)

q2 + +

1 qn

se nazývají přibližnými zlomky. Pro zjednodušení budeme častěji využívá zápis ve tvaru δ 0 = [q 0 ] , δ1 = [q 0 , q1 ] , … , δ n = [q 0 , q1 ,… , q n ] , …

Dále řekneme, že číslo α má konečný (ukončený) rozvoj v řetězový zlomek, jestliže existuje n takové, že při postupu popsaném v úvodu je α n celé číslo (tj. α n +i = 0 pro ∀ i ∈ N + ). V tomto případě zřejmě platí α = [q 0 , q1 ,… , q n ] , tj. α = q 0 +

1 q1 +

.

1 q2 + +

1 qn

Věta 1.5.1 Reálné číslo α má konečný rozvoj v řetězový zlomek právě tehdy, je-li racionální. Důkaz. Z následující poznámky 1.5.1 a z konečnosti Eukleidova algoritmu vyplývá, že každé racionální číslo má konečný rozvoj v řetězový zlomek. Zbývá tak dokázat platnost obráceného tvrzení, tj. z konečnosti rozvoje v řetězový zlomek plyne racionalita. Postupujme sporem a předpokládejme, že číslo s konečným rozvojem v řetězový zlomek není racionální. Spor, neboť bychom nalezli vyjádření iracionálního čísla ve tvaru zlomku. ¶

Obecný postup, jak sestrojovat řetězové zlomky je popsán v úvodu. Následující poznámka ukazuje na souvislost s již dobře známým Eukleidovým algoritmem.


strana 36

Poznámka 1.5.1 – Řetězové zlomky a Eukleidův algoritmus Je-li

a racionální číslo, potom užitím Eukleidova algoritmu dostáváme následující: b

1. krok

a = b ⋅ q 0 + r1 , 0 < r1 < b ,

tj.

a 1 , kde α1 = b > 1 . = q0 + r1 b α1

2. krok

b = r1 ⋅ q1 + r2 , 0 < r2 < r1 ,

tj.

r b 1 , kde α 2 = 1 > 1 , = q1 + r1 r2 α2

tj.

r1 r 1 = q2 + , kde α 3 = 2 > 1 , r2 α3 r3

tedy

3. krok

a = q0 + b

1 1 q1 + α2

.

r1 = r2 ⋅ q 2 + r3 , 0 < r3 < r2 , tedy

a = q0 + b

1 q1 +

.

1 q2 +

1 α3

Vzhledem k tomu, že zbytky tvoří klesající posloupnost přirozených čísel, je zaručena konečnost uvedeného postupu a musí nastat situace, kdy jisté rn je poslední nenulový zbytek

n. krok

rn − 2 = rn −1 ⋅ q n −1 + rn , 0 < rn < rn −1 , tedy

a = q0 + b

tj.

1

q1 +

.

1

q2 + 1

+

q n −1 +

(n + 1). krok

rn −1 = rn ⋅ q n ,

rn − 2 r 1 = q n −1 + , kde α n = n −1 > 1 , rn −1 αn rn

rn −1 = qn , rn

tj.

1 αn

a = q0 + b

1

q1 +

.

1

q2 + +

Vidíme tedy, že jednotlivé členy rozvoje racionálního čísla

1 qn

a v řetězový zlomek tvoří právě b

neúplné podíly z Eukleidova algoritmu.


strana 37

Věta 1.5.2 – základní vlastnosti přibližných zlomků a) Mezi čitateli P i a jmenovateli Qi přibližných zlomků platí

Pi = qi ⋅ Pi −1 + Pi − 2 , kde P−1 = 1, P0 = q1 ,

(1.30)

Qi = qi ⋅ Qi −1 + Qi − 2 , kde Q−1 = 0, Q0 = 1 .

(1.31)

b) Pro libovolné dva sousední přibližné zlomky δ i , δ i −1 platí

δ i − δ i −1 =

(− 1)i +1 Qi ⋅ Qi −1

.

(1.32)

c) Přibližné zlomky jsou v základním tvaru, tj. NSD(Pi , Qi ) = 1 . Důkaz. ad a) Z tvaru přibližných zlomků (1.29) snadno zjistíme zákonitost přechodu mezi čitateli a jmenovateli sousedních přibližných zlomků. Je evidentní, že δ i dostaneme z δ i −1 pouhou substitucí výrazu qi −1 +

1 za qi −1 . Označíme-li tedy Pi čitatele a Qi qi

jmenovatele i-tého přibližného zlomku, tj. δ i = δ0 =

q 0 P0 , = 1 Q0

q0 + δ1 =

Pi , lze psát: Qi

1 q1

1

=

q1 ⋅ q 0 + 1 q1 ⋅ P0 + P−1 P = 1 , kde definujeme P −1 = 1, Q−1 = 0 , = q1 ⋅ 1 + 0 q1 ⋅ Q0 + Q−1 Q1

 1   q1 +  ⋅ P0 + P−1 q2  q ⋅ (q ⋅ P + P−1 ) + P0 q ⋅ P + P0 P δ2 =  = 2 1 0 = 2 1 = 2 q 2 ⋅ (q1 ⋅ Q0 + Q−1 ) + Q0 q 2 ⋅ Q1 + Q0 Q2  1   q1 +  ⋅ Q0 + Q−1 q2  

a

odtud

dostáváme matematickou indukcí dokazované vztahy (1.30) a (1.31). ad b) Zřejmě platí δ i − δ i −1 =

Pi Pi −1 Pi ⋅ Qi −1 − Pi −1 ⋅ Qi − = , Qi Qi −1 Qi ⋅ Qi −1

proto vyšetřujme vztah mezi hodnotou čitatele a indexem i. Označme f (i ) = Pi ⋅ Qi −1 − Pi −1 ⋅ Qi a využijme vztahy (1.30) a (1.31). Dostáváme tak f (i ) = (qi ⋅ Pi −1 + Pi − 2 ) ⋅ Qi −1 − Pi −1 ⋅ (qi ⋅ Qi −1 + Qi − 2 ) =


strana 38

= (− 1) ⋅ (Pi −1 ⋅ Qi − 2 − Pi − 2 ⋅ Qi −1 ) = (− 1) ⋅ f (i − 1) ,

tedy f (i ) = (− 1) ⋅ f (0 ) i

a vzhledem k tomu, že f (0) = P0 ⋅ Q−1 − P−1 ⋅ Q0 = −1 , platí Pi ⋅ Qi −1 − Pi −1 ⋅ Qi = (− 1)

i +1

(1.33)

čímž je vztah (1.32) dokázán. ad c) Snadný důsledek vztahů (1.33) a (1.12). ¶

Je zřejmé, že neúplné podíly qi , i = 0,1,… , n a rekurentní vztahy (1.30), (1.31) s počátečními podmínkami umožňují efektivní výpočet přibližných zlomků. Tento výpočet se často realizuje pomocí tzv. tabulky přibližných zlomků, jejíž schéma následuje: i

-1

0

1

2

…

n

qi

---

q0

q1

q2

…

qn

Pi

1

q0

P1

P2

…

Pn

Qi

0

1

Q1

Q2

…

Qn

Příklad 1.5.1 Číslo

781 rozviňte v řetězový zlomek a sestavte tabulku přibližných zlomků. 654

Řešení. Pomocí Eukleidova algoritmu zjistíme potřebné neúplné podíly: 781 = 654 ⋅ 1(q 0 ) + 127 ,

654 = 127 ⋅ 5(q1 ) + 19 ,

127 = 19 ⋅ 6(q 2 ) + 13 ,

19 = 13 ⋅ 1(q3 ) + 6 ,

13 = 6 ⋅ 2(q 4 ) + 1 ,

6 = 1 ⋅ 6(q5 ) ,

Odtud hledaný rozvoj v řetězový zlomek 781 = 1+ 654

1 1

5+

1

6+ 1+

1 2+

1 6

a tabulka přibližných zlomků (připomeňme, že čitatelé a jmenovatelé jsou počítány rekurentně dle vztahů (1.30) a (1.31) z věty 1.5.2): Diskrétní matematika II

strana 39

i

-1

0

1

2

3

4

5

qi

---

1

5

6

1

2

6

Pi

1

1

6

37

43

123

781

Qi

0

1

5

31

36

103

654

Nyní lze snadno ověřit, základní vlastnosti přibližných zlomků uvedené ve větě 1.5.2. ¶

Poznámka 1.5.2 ♦

Lze ukázat (dokažte), že mezi všemi racionálními čísly, jejichž jmenovatel je nejvýše roven Qi , je právě přibližný zlomek δ i nejlepší aproximací rozvíjeného čísla. Přesněji, platí: Je-li δ i =

Pi a přibližný zlomek rozvoje reálného čísla α v řetězový zlomek, β = Qi b

libovolné racionální číslo takové, že 0 < b ≤ Qi , δ i ≠ β , potom α − δ i < α − β . ♦

Pro zajímavost jsou v následující tabulce uvedeny (nekonečné) řetězové zlomky některých vybraných iracionálních čísel. Číslo

Řetězový zlomek

e

[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10, …]

π

[3,7,15,1,292,1,1,1,2,1,3,1,14, …]

2

[1,2,2,2, …]

5

[2,4,4,4, …]

10

[3,6,6,6, …]

17

[4,8,8,8, …]

26

[5,10,10,10, …]

Jako důsledek tak dostáváme, že následující racionální čísla nejlépe aproximují (ve smyslu první odrážky této poznámky) číslo π .

Pi

3

22

333

355

103 993

Qi

1

7

106

113

33 102

∆i

1,42E-01

1,26E-03

8,32E-05

2,67E-07

5,78E-10

Poslední řádek obsahuje horní mez „chyby“ aproximace, tj. π −


Pi ≤ ∆i . Qi

strana 40

1.6 Kongruence

Z věty o dělení se zbytkem víme, že celá čísla dávají při dělení přirozeným číslem m ≥ 2 zbytky pouze z množiny {0,1,… , m − 1} a tedy z pohledu dělitelnosti, lze čísla dávající

stejný zbytek považovat za „totožná“. Odtud následující definice.

Definice 1.6.1 Řekneme, že celá čísla a, b jsou kongruentní modulo m, kde m ∈ N − {0,1}, jestliže obě čísla

mají při dělení číslem m stejný zbytek. ¶

Skutečnost, že čísla a, b jsou kongruentní modulo m vyjadřujeme některým z následujících zápisů a ≡ b (mod m ) , a ≡ b (m ) , resp. a ≡ m b . V opačném případě (a, b nemají při dělení číslem m stejný zbytek), píšeme a ≡/ b (mod m ) a říkáme, že uvedená čísla jsou modulo m nekongruentní.

Poznámka 1.6.1 Přes svou jednoduchost nachází výše zavedený pojem kongruence velmi široké využití v celé řadě oblastí. Vzhledem k rozsahu skript se stručně zmíníme pouze o generování náhodných (přesněji řečeno pseudonáhodných) čísel a některých způsobech kódování. ♦

Efektivní metodou generování posloupnosti pseudonáhodných čísel x1 , x 2 ,… jsou lineární kongruence. Jednotlivé členy jsou počítány rekurentně ze vztahu x n +1 ≡ m (a ⋅ x n + c ) ,

(1.34)

kde m, a, c, x0 jsou vhodná přirozená čísla taková, že 2 ≤ a < m, 0 ≤ c < m, 0 ≤ x 0 < m (m … modul, a … multiplikační koeficient, c … inkrement, x0 … počáteční hodnota). Většina standardních počítačů dnes využívá pro generování pseudonáhodných čísel modul m = 2 31 − 1 , multiplikační koeficient a = 7 5 a navíc speciální variantu vztahu (1.34), tzv.

ryze multiplikativní generátor, kde c = 0 . (V případě, kdy požadujeme pseudonáhodná čísla z intervalu posloupnost

xi

m


0,1) , použijeme

, i = 1, 2,… )

strana 41

♦

Jedním z nejstarších způsobů kódování je tzv. Caesarovo kódování, které spočívalo v „cyklickém posunutí“ celé abecedy o tři znaky vpřed

( A → D, B → E , … , Z → C ) .

Z pohledu kongruencí lze toto kódování popsat vztahem y ≡ 26 ( x + 3) ,

(1.35)

kde x je pořadové číslo kódovaného znaku (v rámci anglické abecedy), y je pořadové číslo zakódovaného znaku, 3 je posunutí a 26 je počet znaků abecedy. Dekódování se pak provádí „zpětným“ posunutím, tj. dle vztahu x ≡ 26 ( y − 3) ,

(1.36)

kde x je původní znak a y zakódovaný znak. Poznamenejme, že výše popsaný způsob kódování není příliš bezpečný, proto se dnes používají sofistikovanější metody (viz poznámka 1.7.3).

Věta 1.6.1 Následující tvrzení jsou ekvivalentní: a) a ≡ b (mod m ) , b) m | (a − b ) , c) a = b + m ⋅ t , kde t ∈ Z . Důkaz (stačí dokázat a)  → b)  → c)  → a)) ad a)  → b) Jelikož a ≡ b (mod m ) , dostáváme z věty o dělení se zbytkem a = a1 ⋅ m + r , b = b1 ⋅ m + r , kde 0 ≤ r < m .

Odtud a − b = (a1 − b1 ) ⋅ m , tedy m | (a − b ) .

ad b)  → c) Přímo z definice dělitelnosti dostáváme a − b = m ⋅ t , kde t ∈ Z , tedy a = b + m ⋅ t . ad c)  → a) Z věty o dělení se zbytkem dostáváme b = m⋅q + r , 0 ≤ r < m

a dosazením do c) a = m ⋅ (q + t ) + r , kde 0 ≤ r < m

a tedy obě čísla dávají při dělení m stejný zbytek. ¶


strana 42

Příklad 1.6.1 Zřejmě platí 760 ≡ −23 (mod 3)

… obě čísla dávají při dělení číslem 3 zbytek 1, tedy ekvivalentně platí 3 | 760 − (− 23) , 760 = (− 23) + 3 ⋅ 261 .

760 ≡/ −23 (mod 7 )

… při dělení číslem 7 dává 760 zbytek 4 a –23 zbytek 5, tedy ekvivalentně 7 /| 760 − (− 23) , 760 ≠ (− 23) + 7 ⋅ t pro každé t ∈ Z .

31 ≡ 435 (mod 101)

… obě čísla dávají při dělení číslem 101 zbytek 31, tedy ekvivalentně platí 101| 31 − 435 , 31 = 435 + 101 ⋅ (− 4 ) . ¶

Jak dokládá následující věta, jsou početní pravidla pro kongruence mající stejný modul podobná početním pravidlům pro rovnice.

Věta 1.6.2 – stejný modul Jestliže a1 ≡ b1 (mod m ) , a 2 ≡ b2 (mod m ) , potom platí: a) a1 + a 2 ≡ b1 + b2 (mod m ) .

(1.37)

b) a1 ⋅ a 2 ≡ b1 ⋅ b2 (mod m ) .

(1.38)

c) Jestliže d | a1 , d | b1 , NSD (d , m ) = 1 , potom

a1 b1 ≡ (mod m ) . d d

(1.39)

Důkaz. Zřejmě a1 = b1 + mt1 , a 2 = b2 + mt 2 . ad a) a1 + a 2 = (b1 + mt1 ) + (b2 + mt 2 ) = (b1 + b2 ) + m ⋅ (t1 + t 2 ) a dle věty 1.6.1 platí (1.37). ad b) a1 ⋅ a 2 = (b1 + mt1 ) ⋅ (b2 + mt 2 ) = b1 ⋅ b2 + m ⋅ (b1 ⋅ t 2 + t1 ⋅ b2 + m ⋅ t1 ⋅ t 2 ) a dle věty 1.6.1 platí (1.38). ad c) Jelikož d | a1 , d | b1 a platí a1 = b1 + m ⋅ t1 , musí d | m ⋅ t1 . Vzhledem k podmínce NSD(d , m ) = 1 a poznámce1.3.1 platí (1.39). ¶

Jako snadný důsledek pak dostáváme: ♦

K oběma stranám kongruence lze přičíst, resp. od nich odečíst libovolné celé číslo.

♦

Členy z jedné strany kongruence lze převést na druhou, pokud u nich změníme znaménko.

♦

Obě strany kongruence lze umocnit na n-tou, kde n ∈ N .


strana 43

Jak dokládá následující ukázka, je ve větě 1.6.2 část c) předpoklad NSD(d , m ) = 1 podstatný, neboť 144 ≡ 78 (mod 33) , ovšem

144 78 (mod 33) . ≡/ 6 6

Věta 1.6.3 – změna modulu a) Jestliže a ≡ b (mod m ) , potom a ⋅ k ≡ b ⋅ k (mod m ⋅ k ) , kde k ∈ N + . m  b) Jestliže a ≡ b (mod m ), d | m , potom a ≡ b  mod  . d  c) Jestliže a ≡ b (mod m ), d | NSD (a, b, m ) , potom

a b m ≡  mod  . d d  d

d) Jestliže a ≡ b (mod m1 ), a ≡ b (mod m2 ) , potom a ≡ b (mod NSN (m1 , m2 )) . Důkaz. ad a) Dle věty 1.6.1 část c) platí a = b + m ⋅ t , tedy a ⋅ k = b ⋅ k + (m ⋅ k ) ⋅ t , což je dle stejné věty ekvivalentní dokazovanému vztahu. ad b) Označme m1 =

m . Dle věty 1.6.1 část b) platí m | (a − b ) a jelikož d | m platí i d

m1 | (a − b ) , což je ekvivalentní dokazovanému vztahu.

ad c) Jelikož a = b + m ⋅ t a d | NSD (a, b, m ) platí

a b m = + ⋅ t , což je ekvivalentní d d d

dokazovanému vztahu. ad d) Jelikož m1 | (a − b ) a m2 | (a − b ) zřejmě i NSN (m1 , m2 )| (a − b ) . ¶

Příklad 1.6.2 Pro určení dne v týdnu (pondělí – neděle), který připadne na dané datum, lze využít tzv. Zellerovy kongruence s r  x ≡ d + 2,6m − 0,2 + r +   − 2s +   4 4

(mod 7 ) ,

(1.40)

kde x … je identifikace dne v týdnu dle tabulky 0 NE

1 PO

2 ÚT

3 ST

4 ČT

5 PÁ

6 SO

d … je den v měsíci,


strana 44

m … je identifikace měsíce dle tabulky 1 březen 7 září

2 duben 8 říjen

3 4 5 květen červen červenec 9 10 11 listopad prosinec leden

6 srpen 12 únor

s … je století příslušné N, kde N je pro leden a únor předcházející rok zjišťovaného datumu a v ostatních případech jde o aktuální rok,

r … jsou jednotky a desítky let (bez století) příslušné N. Snadno tak například zjistíme, že dne: 1.11.1111 byla středa (N = 1111, d = 1, m = 9, r = 11, s = 11, x ≡ 7 3) , 2.2. 2222 bude sobota (N = 2221, d = 2, m = 12, r = 21, s = 22, x ≡ 7 6) . ¶

Pro další úvahy je důležité si uvědomit, že vztah „býti kongruentní modulo m“ tvoří binární relaci na Z s vlastnostmi a ≡ a (mod m ) ,

♦

∀a ∈ Z

♦

∀a, b ∈ Z

♦

∀a, b, c ∈ Z

(reflexivita)

a ≡ b (mod m )  → b ≡ a (mod m ) ,

(symetrie)

a ≡ b (mod m ) ∧ b ≡ c (mod m )  → a ≡ c (mod m ) . (tranzitivita)

Jde tedy o relaci ekvivalence, která indukuje rozklad Z mající m následujících tříd ekvivalence

[0] = {… , − 2m, − m, 0, m, 2m,…} = {k ⋅ m

k ∈ Z },

[1] = {… ,1 − 2m,1 − m,1,1 + m,1 + 2m,…} = {1 + k ⋅ m

k ∈ Z },

[2] = {… ,2 − 2m,2 − m, 2, 2 + m,2 + 2m,…} = {2 + k ⋅ m

k ∈ Z },

[m − 1] = {… , − m − 1,−1, m − 1, 2m − 1, 3m − 1,…} = {(m − 1) + k ⋅ m

k ∈ Z },

nazývané zbytkové třídy modulo m, resp. třídy zbytků modulo m. Každá třída zbytků obsahuje právě všechny navzájem modulo m kongruentní celá čísla (tj. čísla mající při dělení

m stejný zbytek). Pro množinu všech takto vzniklých zbytkových tříd modulo m se vžilo označení Z m , tj. Z m = {[0], [1],… , [m − 1] } . Poznamenejme, že v dalších částech skript, kde by již nemělo dojít k nedorozumění, budeme běžně používat zjednodušený zápis a místo [a ] a

Z m = {0,1,… , m − 1}.


strana 45

Nyní na množině Z m definujme operaci sčítání

[a] + [b] = [a + b] a násobení

[a] ⋅ [b] = [a ⋅ b] . (Dokažte, že obě operace jsou definovány korektně, tj. pokud [a1 ] = [a 2 ], [b1 ] = [b2 ], potom

[a1 ] + [b1 ] = [a 2 ] + [b2 ] a [a1 ] ⋅ [b1 ] = [a 2 ] ⋅ [b2 ] .) Kromě obvyklých vlastností obou operací (asociativita, komutativita, distributivita, existence nulového, opačného a jednotkového prvku) platí: ♦

V Z m lze dělit právě tehdy, je-li m prvočíslo, tj. ∀[a ] ∈ Z m − {[0]} ∃ [b] ∈ Z m

[a] ⋅ [b] = [1] právě tehdy, je-li m prvočíslo.

(V tomto případě používáme označení [a ] místo [b ] a mluvíme o inverzním prvku.) −1

♦

V Z m existují vlastní dělitele nuly právě tehdy, je-li m je číslo složené, tj. ∃[a ], [b] ∈ Z m − {[0]} [a ] ⋅ [b ] = [0] právě tehdy, je-li m číslo složené.

Příklad 1.6.3 Algebraická struktura Z 5 obsahuje následujících pět zbytkových tříd (ověřte, že skutečně tvoří rozklad, tj. Z = [0] ∪ [1] ∪ [2] ∪ [3] ∪ [4] a ∀i, j ∈ {0,1,… ,4}, i ≠ j platí [i ] ∩ [ j ] = ∅ ):

[0] = {… , − 10, − 5, 0, 5,10,…} = {5k

k ∈ Z } … čísla dělitelná pěti, tj. dávající zbytek 0,

[1] = {… , − 9, − 4,1, 6,11,…} = {5k + 1 k ∈ Z } … čísla dávající při dělení pěti zbytek 1, [2] = {… , − 8, − 3, 2, 7,12,…} = {5k + 2

k ∈ Z } … čísla dávající při dělení pěti zbytek 2,

[3] = {… , − 7, − 2, 3, 8,13,…} = {5k + 3

k ∈ Z } … čísla dávající při dělení pěti zbytek 3,

[4] = {… , − 6, − 1, 4, 9,14,…} = {5k + 4 k ∈ Z } … čísla dávající při dělení pěti zbytek 4, kde operace sčítání a násobení jsou definovány následujícími tabulkami: +

[0]

[1]

[2]

[3]

[4]

·

[0]

[1]

[2]

[3]

[4]

[0] [1] [2] [3] [4]

[0] [1] [2] [3] [4]

[1] [2] [3] [4] [0]

[2] [3] [4] [0] [1]

[3] [4] [0] [1] [2]

[4] [0] [1] [2] [3]

[0] [1] [2] [3] [4]

[0] [0] [0] [0] [0]

[0] [1] [2] [3] [4]

[0] [2] [4] [1] [3]

[0] [3] [1] [4] [2]

[0] [4] [3] [2] [1]


strana 46

Nyní snadno ověříme, že v Z 5 je možné provádět „stejné“ výpočty jako v Q, resp. R. Speciálně lze dělit, neboť

[1]−1 = [1], [2]−1 = [3], [3]−1 = [2], [4]−1 = [4] , navíc platí

Například, pokud

[a] ⋅ [b] = [0] → ([a] = 0) ∨ ([b] = 0) . máme určit zbytkovou třídu [x ] takovou,

aby

[2] ⋅ [x] ⋅ [4] = [1] ,

lze

postupovat následovně: … využíváme [2] = [3]

[3] ⋅ [2] ⋅ [x] ⋅ [4] = [3] ⋅ [1],

−1

Odtud

[x] ⋅ [4] = [3] . Dále

[x] ⋅ [4] ⋅ [4] = [3] ⋅ [4] , tedy

… využíváme [4] = [4] −1

[x] = [2] .

Algebraická struktura Z 6 obsahuje následujících šest zbytkových tříd:

[0] = {… , − 12, − 6, 0, 6,12,…} = {6k

k ∈ Z } … čísla dělitelná šesti, tj. dávající zbytek 0,

[1] = {… , − 11, − 5,1, 7,13,…} = {6k + 1 k ∈ Z } … čísla dávající při dělení šesti zbytek 1,

[2] = {… , − 10, − 4, 2, 8,14,…} = {6k + 2 [3] = {… , − 9, − 3, 3, 9,15,…} = {6k + 3

k ∈ Z } … čísla dávající při dělení šesti zbytek 2,

k ∈ Z } … čísla dávající při dělení šesti zbytek 3,

[4] = {… , − 8, − 2, 4,10,16,…} = {6k + 4 k ∈ Z } … čísla dávající při dělení šesti zbytek 4, [5] = {… , − 7, − 1, 5,11,17,…} = {6k + 5 k ∈ Z } … čísla dávající při dělení šesti zbytek 5, kde operace sčítání a násobení jsou definovány následujícími tabulkami: +

[0]

[1]

[2]

[3]

[4]

[5]

·

[0]

[1]

[2]

[3]

[4]

[5]

[0] [1] [2] [3] [4]

[0] [1] [2] [3] [4]

[1] [2] [3] [4] [5]

[2] [3] [4] [5] [0]

[3] [4] [5] [0] [1]

[4] [5] [0] [1] [2]

[5] [0] [1] [2] [3]

[0] [1] [2] [3] [4]

[0] [0] [0] [0] [0]

[0] [1] [2] [3] [4]

[0] [2] [4] [0] [2]

[0] [3] [0] [3] [0]

[0] [4] [2] [0] [4]

[0] [5] [4] [3] [2]

[5]

[5]

[0]

[1]

[2]

[3]

[4]

[5]

[0]

[5]

[4]

[3]

[2]

[1]


strana 47

V Z 6 již nelze provádět výpočty tak, jako v Q, resp. R, neboť neexistuje [2] , [3] , [4] −1

−1

−1

(tj.

nelze obecně dělit) a navíc může platit [a ] ⋅ [b ] = [0] přesto, že [a ] ≠ 0 i [b ] ≠ 0 (např.

[2] ⋅ [3] = [3] ⋅ [4] = [0]). ¶ Odtud již motivace pro následující definici úplné a redukované soustavy zbytků.

Definice 1.6.2 – úplná a redukované soustava zbytků ♦

Úplnou soustavou zbytků modulo m nazveme každou množinu obsahující m modulo m nekongruentních celých čísel.

♦

Redukovanou soustavou zbytků modulo m nazveme takovou podmnožinu úplné soustavy zbytků modulo m, která obsahuje právě všechny zbytky nesoudělné s modulem m. ¶

Poznámka 1.6.2 ♦

Z definice Eulerovy funkce vyplývá, že počet prvků redukované soustavy zbytků modulo m je roven ϕ(m ) .

♦

Pro daný modul m ≥ 2 existuje nekonečně mnoho úplných (i redukovaných) soustav zbytků, neboť každá zbytková třída je v úplné soustavě zastoupena libovolným svým prvkem (tzv. reprezentant zbytkové třídy). Nejpoužívanější je však úplná soustava nejmenších nezáporných zbytků modulo m, tj.:

{0,1,… , m − 1} , resp. úplná soustava absolutně nejmenších zbytků modulo m tj.: m − 1 1 − m ,… ,−1, 0,1,… ,  pro m liché,  2   2 m m − 2  m 2 − m ,… ,−1, 0,1,… ,  pro m sudé.  , resp.  − ,… ,−1, 0,1,… , 2  2  2  2

Příklad 1.6.4 Příklady úplných a redukovaných soustav zbytků modulo 5:

{0, 1, 2, 3, 4}

… úplná soustava nejmenších nezáporných zbytků modulo 5,

{− 2, − 1, 0, 1, 2}

… úplná soustava absolutně nejmenších zbytků modulo 5,


strana 48

{7, 8, 9, 10, 11}  {− 21,−20,−19,−18,−17}  {4, 10, 16, 22, 28}  {− 51, − 23, − 10,16, 38} 

… další příklady úplných soustav zbytků modulo 5.

Jelikož ϕ(5) = 4 , má každá redukovaná soustava zbytků modulo 5 právě 4 prvky.

{1, 2, 3, 4}  {− 2, − 1, 1, 2}  {4, 16, 22, 28}  {− 51, − 23, 16, 38}

… příklady redukovaných soustav zbytků modulo 5.

Příklady úplných a redukovaných soustav zbytků modulo 6:

{0, 1, 2, 3, 4, 5}

… úplná soustava nejmenších nezáporných zbytků modulo 6,

{− 3, − 2, − 1, 0, 1, 2} {− 2, − 1, 0, 1, 2, 3} 

… úplné soustava absolutně nejmenších zbytků modulo 6,

{11, 12,13,14,15,16}   {− 10,−9,−8,−7,−6,−5}   {7, 14, 21, 28, 35, 42}  {− 73, − 62, − 28, − 12,19, 45}

… další příklady úplných soustav zbytků modulo 6.

Jelikož ϕ(6 ) = 2 , má každá redukovaná soustava zbytků modulo 6 právě 2 prvky.

{1, 5}  {− 1, 1}  {11, 13}  {19, − 73}

… příklady redukovaných soustav zbytků modulo 6.

¶

Věta 1.6.4 Nechť a, b, m ∈ Z , kde m ≥ 2, NSD(a, m ) = 1 . Potom platí: a) Je-li {x1 ,… , x m } úplná soustava zbytků modulo m, potom {a ⋅ x1 + b,… , a ⋅ x m + b} tvoří také úplnou soustavu zbytků modulo m. b) Je-li {x1 ,… , xϕ(m ) } redukovaná soustava zbytků modulo m, potom {a ⋅ x1 ,… , a ⋅ xϕ(m ) } tvoří také redukovanou soustavu zbytku modulo m. Důkaz. ad a) Zřejmě stačí dokázat, že čísla {a ⋅ xi + b i = 1,… , m} jsou nekongruentní modulo m. Diskrétní matematika II

strana 49

Pokračujme sporem a předpokládejme, že existuje i, j takové, že a ⋅ xi + b ≡ a ⋅ x j + b (mod m ) , NSD(a, m ) = 1

{x

i

nutně

platí

m | a ⋅ (xi − x j ) .

tj.

m | (xi − x j ) ,

tedy

Vzhledem

xi ≡ x j (mod m ) .

i ≠ j a platí k předpokladu Spor,

neboť

i = 1,… , m} tvoří úplnou soustavu zbytků modulo m.

ad b) Vzhledem k již dokázané části a) je třeba ukázat, že čísla {a ⋅ xi i = 1,… , ϕ(m )} jsou nesoudělná s modulem m. Jelikož {xi i = 1,… , ϕ(m )} je redukovaná soustava zbytků modulo m, platí NSD( xi , m ) = 1, i = 1,… , ϕ(m ) , navíc dle předpokladu NSD(a, m ) = 1 . Odtud dle (1.17) NSD(a ⋅ xi , m ) = 1, i = 1,… , ϕ(m ) . ¶

Věta 1.6.5 - Eulerova věta Pro libovolné a, m ∈ Z , m ≥ 2 , kde NSD(a, m ) = 1 platí a ϕ(m ) ≡ 1 (mod m ) .

(1.41)

Důkaz. Označme {x1 ,… , xϕ(m ) } redukovanou soustavu zbytků modulo m. Z věty1.6.4 část b) vyplývá, že i {a ⋅ x1 ,… , a ⋅ xϕ(m ) } tvoří redukovanou soustavu zbytků modulo m (obecně v jiném pořadí) a tedy x1 ≡ a ⋅ xi (mod m ), x2 ≡ a ⋅ xi 1

2

(mod m ),…, xϕ(m ) ≡ a ⋅ xiϕ(m ) (mod m ) .

Po vynásobení všech výše uvedených kongruencí dostáváme a ϕ(m ) ⋅ x1 ⋅ … ⋅ xϕ(m ) ≡ x1 ⋅ … ⋅ xϕ(m ) (mod m )

a po vydělení obou stran čísly xi , i = 1,… , ϕ(m ) , která jsou nesoudělná s modulem, dostáváme dokazované tvrzení. ¶

Jako snadný důsledek Eulerovy věty dostáváme následující tzv. malou Fermatovu větu.

Věta 1.6.6 – Malá Fermatova věta Je-li p prvočíslo, a přirozené číslo takové, že p /| a , potom platí a p −1 ≡ 1 (mod p ) .

(1.42)

¶


strana 50

Jako cvičení zdůvodněte, že pro libovolné prvočíslo p a libovolné přirozené číslo a platí a p ≡ a (mod p ) .

Příklad 1.6.5 Určete zbytek při dělení čísla 3 2882 číslem 97. Řešení. Pro hledaný zbytek, který označíme x0 , platí x0 ≡ 3 2882 (mod 97 ) . Z Eulerovy věty (NSD (3, 97 ) = 1, ϕ(97 ) = 96 ) víme, že 396 ≡ 1 (mod 97 ) a jelikož 2882 = 30 ⋅ 96 + 2 dává číslo 3 2882 při dělení 97 stejný zbytek jako 3 2 . Odtud hledaný zbytek x0 = 9 . ¶

Poznámka 1.6.3 Staří čínští matematici se chybně domnívali, že číslo p je prvočíslo právě tehdy, jestliže platí 2 p −1 ≡ 1 (mod p ) .

(∗)

Z malé Fermatovy věty vyplývá, že pro všechna prvočísla větší než dvě vztah (∗) skutečně platí a jelikož jim nebylo známé žádné složené číslo, které by mělo stejnou vlastnost, učinili již zmíněný chybný závěr (ostatně obdobného omylu se dopustil i Fermat v případě tzv. Fermatových čísel). V dnešní době výpočetní techniky lze snadno zjistit, že nejmenší složené číslo pro které platí (∗) je 341 = 11 ⋅ 31 , tj. 2 340 ≡ 1 (mod 341) . Lze dokonce ukázat, že takových složených čísel (nazývaných pseudoprvočísla) existuje nekonečně mnoho. Na druhé straně lze ukázat, že jejich výskyt je v porovnání s prvočísly řídký, tzn. je relativně velká pravděpodobnost, že číslo s vlastností (∗) bude opravdu prvočíslo. Této skutečnosti využívají tzv. pravděpodobnostní testy prvočíselnosti a číslo, které tímto testem úspěšně projde je s vysokou pravděpodobností (tj. nikoliv nutně) prvočíslo.


strana 51

1.7 Řešení kongruencí 1. stupně a jejich soustav

V tomto odstavci se budeme zabývat úlohou, která má v oblasti diskrétní matematiky široké využití, totiž řešením kongruencí. Pro tyto účely budeme pod pojmem kongruence rozumět výraz f ( x ) ≡ 0 (mod m ) ,

kde

(1.43)

m ∈ Z , m ≥ 2 je modul a f ( x ) = a n x n + … + a1 x + a0 je nenulový polynom s celočíselnými koeficienty, pro který m /| a n (číslo n nazýváme stupněm kongruence).

Hlavním cílem bude nalézt všechna celá čísla, pro která platí (1.43). V tomto kontextu je důležité si uvědomit (dokažte!), že platí f ( x0 ) ≡ 0 (mod m )  → ∀t ∈ Z f (x 0 + m ⋅ t ) ≡ 0 (mod m )

(1.44)

a tedy pokud kongruenci (1.43) vyhovuje jisté číslo x0 , vyhovují ji také všechna celá čísla, která jsou s x0 kongruentní modulo m, tj. x ≡ x 0 (mod m ) . Z těchto důvodů je rozumné (a dále tak činíme), považovat za jedno řešení celou zbytkovou třídu [x0 ] = {x 0 + m ⋅ t t ∈ Z }. Zřejmým důsledkem pak je skutečnost, že kongruence (1.43) má nejvýše m řešení (řádně zdůvodněte!), která lze nalézt metodou „hrubé síly“, tj. postupným dosazováním čísel 0,1,… , m − 1 . Na druhé straně je celá řada relevantních důvodů, pro které je vhodné nalézt efektivnější způsoby řešení (1.43). Vzhledem k rozsahu skript se dále omezíme na metody řešení kongruencí 1. stupně, tj. a ⋅ x ≡ b (mod m )

(1.45)

a jejich speciálních soustav.

Věta 1.7.1 Nechť NSD(m, a ) = 1, m ≥ 2 . Potom kongruence (1.45) má pro libovolné b ∈ Z právě jedno řešení. Toto řešení je tvaru x ≡ (− 1) ⋅ Pn −1 ⋅ b (mod m ) , n

kde Pn −1 je čitatel předposledního přibližného zlomku rozvoje


(1.46) m v řetězový zlomek. a

strana 52

Důkaz. Z věty 1.6.4 část a) vyplývá, že za daných předpokladů má kongruence (1.45) pro libovolné b právě jedno řešení a tedy stačí nalézt jakékoliv celé číslo, které ji vyhovuje (řešením je pak Pn −1 P m a δn = n = poslední dva přibližné zlomky Qn −1 Qn a

celá zbytková třída). Označme δ n −1 = rozvoje

m v řetězový zlomek. Dle (1.33) platí mezi jejich čitateli a jmenovateli vztah a Pn ⋅ Qn −1 − Pn −1 ⋅ Qn = (− 1)

n +1

,

tj. m ⋅ Qn −1 − Pn −1 ⋅ a = (− 1)

n +1

.

Odtud dostáváme − a ⋅ Pn −1 ≡ (− 1)

Po vynásobení obou stran číslem (− 1)

n +1

[

n +1

(mod m ) .

⋅ b a několika zřejmých úpravách lze psát

]

a ⋅ (− 1) ⋅ Pn −1 ⋅ b ≡ b (mod m ) . n

x

¶

Příklad 1.7.1 Nalezněte řešení kongruence 269 x ≡ 11 (mod 379 ) . Řešení. Jelikož NSD (m, a ) = NSD (379, 269 ) = 1 , má uvedená kongruence právě jedno řešení, které určíme ze vztahu (1.46). Aplikací Eukleidova algoritmu dostáváme (hodnoty qi jsou neúplné podíly v Eukleidově algoritmu a Pi počítáme rekurentně dle vztahu (1.30)). i qi Pi

-1 --1

0 1 1

1 2 3

2 2 7

3 4 31

4 12 379

Odtud n = 4, Pn −1 = P3 = 31, b = 11 a hledané řešení je x ≡ 341 (mod 379 ) . ¶

Jak vyplyne z následující poznámky, má věta 1.7.1 základní význam i pro řešení obecných kongruencí 1. stupně, kde NSD(m, a ) ≠ 1 .


strana 53

Poznámka 1.7.1 – řešení obecných kongruencí 1. stupně Uvažujme nyní obecnou kongruenci (1.45) a označme d = NSD (m, a ) . V situaci, kdy d = 1 postupujeme dle věty (1.71), proto předpokládejme, že d ≥ 2 . V tomto případě platí: a) Jestliže d /| b , potom kongruence (1.45) nemá řešení (řádně zdůvodněte!). b) Jestliže d | b , potom kongruence (1.45) má právě d následujících řešení x ≡ x 0 ; x0 + m1 ; … ; x0 + (d − 1) ⋅ m1

(mod m ) ,

kde x0 je jediné řešení kongruence a1 ⋅ x ≡ b1 (mod m1 ) , a1 =

(1.47)

a b m , b1 = , m1 = . d d d

(Zdůvodněte! Využijte pravidlo, že obě strany kongruence i modul lze vydělit jejich společným dělitelem, čímž dostaneme kongruenci a1 ⋅ x ≡ b1 (mod m1 ) ,

kde NSD(m1 , a1 ) = 1 . Dle věty 1.7.1 má tato kongruence řešení x ≡ x 0 (mod m1 ) , které vyjádříme pomocí zbytků modulo m.)

Příklad 1.7.2 Nalezněte všechna řešení kongruence: a) 210 x ≡ 57 (mod 385) , b) 116 x ≡ 60 (mod 148) . Řešení. ad a) Pomocí Eukleidova algoritmu zjistíme, že NSD(m, a ) = NSD (385, 210 ) = 35 . Jelikož 35 /| 57 , nemá dle poznámky 1.7.1 část a) uvedená kongruence řešení. ad b) Aplikací Eukleidova algoritmu zjistíme, že NSD (m, a ) = NSD (148,116 ) = 4 a jelikož 4 | 60 , má dle poznámky 1.7.1 část b) uvedená kongruence právě čtyři řešení tvaru (1.47). Nyní převedeme řešení původní kongruence na řešení ekvivalentní kongruence, kterou dostaneme vydělením obou stran i modulu čtyřmi. Dostáváme tak 29 x ≡ 15 (mod 37 ) ,

(∗)

kde NSD(37, 29 ) = 1 a kterou řešíme dle věty 1.7.1. i qi Pi

-1 --1

0 1 1

1 3 4

2 1 5

3 1 9

4 1 14

5 2 37

Jako řešení kongruence (∗) tak dostáváme x0 ≡ 12 (mod 37 ) a konečně ze vztahu (1.47) pak dostáváme hledaná čtyři řešení původní kongruence x ≡ 12; 49; 86; 123


(mod 148) . ¶ strana 54

Na závěr tohoto odstavce se ještě zmíníme o řešení soustavy kongruencí x ≡ b1 (mod m1 ), … , x ≡ bn (mod mn ) ,

(1.48)

kde NSD (mi , m j ) = 1 pro všechna i ≠ j . Tyto soustavy nachází využití například při provádění rychlých výpočtů s velkými čísly (viz následující poznámka 1.7.2) nebo při jednom z nejbezpečnějších způsobů kódování tzv. RSA metodě (viz poznámka 1.7.3).

Věta 1.7.2 Soustava (1.48) má pro libovolné hodnoty b1 ,… , bn jediné řešení. Toto řešení je tvaru x ≡ x0

(mod M ) ,

x0 = M 1 ⋅ x1 ⋅ b1 + … + M n ⋅ x n ⋅ bn

kde

(1.49)

M = m1 ⋅ … ⋅ mn , Mi =

M , i = 1,… , n a mi

xi je (libovolné) číslo vyhovující kongruenci M i ⋅ xi ≡ 1 (mod mi ) . Důkaz. Vzhledem k definicím čísel M , M i , xi je snadné ukázat, že všechna čísla x tvaru x ≡ x0

(mod M )

vyhovují (1.48). Zbývá proto ukázat, že je to jediné řešení. Označme y 0

libovolné celé číslo, které vyhovuje (1.48), tj. ∀i ∈ {1,….n} y 0 ≡ bi (mod mi ) . Z věty 1.7.1 víme, že každá z kongruencí x ≡ bi (mod mi ), i = 1,… , n má právě jedno řešení, tedy ∀i ∈ {1,… , n} y 0 ≡ x0 (mod mi ) . Z věty 1.6.3 část d) pak dostáváme, že y 0 ≡ x 0 (mod M ) , což bylo třeba dokázati. ¶

Příklad 1.7.3 Nalezněte řešení soustavy x ≡ 2 (mod 5), x ≡ 3 (mod 8), x ≡ 6 (mod 11), x ≡ 4 (mod 9 ) .

Řešení. Dle věty 1.7.2 vypočteme M = 3960, M 1 = 792, M 2 = 495, M 3 = 360, M 4 = 440 . Čísla xi , i = 1,… ,4 určíme z následujících kongruencí 792 x1 ≡ 1 (mod 5) , tedy x1 = 3 ,


495 x 2 ≡ 1 (mod 8) , tedy x 2 = 7 ,

strana 55

360 x3 ≡ 1 (mod 11) , tedy x3 = 7 ,

440 x 4 ≡ 1 (mod 9 ) , tedy x 4 = 8 .

Ze vztahu (1.49) dostáváme x0 = 792 ⋅ 3 ⋅ 2 + 495 ⋅ 7 ⋅ 3 + 360 ⋅ 7 ⋅ 6 + 440 ⋅ 8 ⋅ 4 = 44 348 a odtud hledané řešení (v soustavě nejmenších nezáporných zbytků) x ≡ 787 (mod 3 960 ) . ¶

Poznámka 1.7.2 – aritmetika velkých čísel Procesory jsou schopny provádět „rychlé“ aritmetické operace s čísly, které lze uložit do paměti určité velikosti (např. 64 bitů). Výpočty s velkými čísly se proto realizují pomocí tzv. modulární aritmetiky, která je založena na větě 1.7.2. Z této věty vyplývá, že pokud máme k

dány moduly m1 ,… , mn (po dvou nesoudělné, pochopitelně nejčastěji tvaru 2 i − 1 ), lze každé číslo a z množiny {0,1,… , M − 1}, kde M = m1 ⋅ … ⋅ mn , jednoznačně reprezentovat n-ticí

(a1 ,… , a n ) , kde

ai je nejmenší nezáporný zbytek modulo mi , tj. ai ∈ {0,1,… , mi − 1}. Tuto n-

tici nazýváme modulární reprezentací čísla a. Nyní lze provádět výpočty v modulární reprezentaci a to po složkách (vzhledem k jejich velikosti velmi rychle) následovně: Označme (a1 ,… , a n ) modulární reprezentaci čísla a, (b1 ,… , bn ) modulární reprezentaci čísla b, potom modulární reprezentace a + b je rovna

((a1 + b1 ) mod m1 ,… , (a n + bn ) mod mn ) a modulární reprezentace a ⋅ b je rovna

(a1 ⋅ b1 mod m1 ,… , a n ⋅ bn

mod mn ) .

Na závěr poznamenejme, že převody mezi „standardní“ a modulární reprezentací se provádí pouze na začátku a konci výpočtu, navíc převody ze „standardní“ do modulární reprezentace jsou vzhledem k obvyklé volbě modulů rychlé.

Příklad 1.7.4 Pomocí modulární aritmetiky využívající moduly m1 = 211 − 1 = 2 047, m2 = 213 − 1 = 8 191 a m3 = 215 − 1 = 32 767 , vypočtěte (3b − 2d )(c − a ) , kde a = 454 545, b = 313 131, c = 888 888, d = 171 717 . Řešení. Nejprve nalezneme odpovídající modulární reprezentace čísel, s kterými budeme provádět výpočty. Dostáváme a = (a mod m1 , a mod m2 , a mod m3 ) = (111, 4040, 28574) ,


strana 56

b = (b mod m1 , b mod m2 , b mod m3 ) = (1987, 1873, 18228) , c = (c mod m1 , c mod m2 , c mod m3 ) = (624, 2350, 26845) , d = (d mod m1 , d mod m2 , d mod m3 ) = (1816, 7897, 7882 ) . Nyní snadno provedeme po složkách příslušné modulární výpočty. První složka:

(3 ⋅ 1987 − 2 ⋅ 1816) ⋅ (624 − 111) ≡ 1376 (mod 2047 ) .

Druhá složka:

(3 ⋅ 1873 − 2 ⋅ 7897 ) ⋅ (2350 − 4040) ≡ 2841 (mod 8191) .

Třetí složka:

(3 ⋅ 18228 − 2 ⋅ 7882) ⋅ (26845 − 28574) ≡ 10738 (mod 32767 ) .

Jako modulární reprezentaci výsledku tak dostáváme

(3b − 2d )(c − a ) = (1376, 2841, 10738) . Posledním krokem je převedení výsledku z jeho modulární reprezentace do „standardní“. Tu nalezneme jako řešení soustavy x ≡ 1376 (mod 2047 ), x ≡ 2841 (mod 8191), x ≡ 10738 (mod 32767 ) .

Aplikací věty 1.7.2 tak dostáváme výsledek

(3b − 2d )(c − a ) = 252 830 838 078 . ¶ Poznámka 1.7.3 – RSA metoda kódování s veřejným klíčem Metoda RSA kódování s veřejným klíčem (Rivest, Shamir, Adleman – jména autorů metody) je moderní a velmi bezpečný způsob kódování, který je vyvíjen od poloviny sedmdesátých let 20. století. Na rozdíl od klasického kódování, kde odesilatel i příjemce je schopen zprávy jak kódovat, tak i dekódovat, je v případě RSA metody situace zásadně odlišná. Každý zájemce má k dispozici tzv. veřejný klíč, tj. dvojici čísel (n, e ) , která mu umožňuje zprávy jednoduše kódovat, nikoliv však dekódovat. K dekódování je totiž potřeba znát kanonický rozklad čísla n, které je záměrně konstruováno jako součin dvou velkých prvočísel majících obvykle stovky dekadických míst. Velmi vysoká bezpečnost tohoto způsobu kódovaní je pak založena na skutečnosti, že doposud není znám žádný dostatečně efektivní algoritmus umožňující nalézt kanonický rozklad extrémně velkých čísel (viz poznámka 1.3.3 týkající se Fermatových a Mersennových prvočísel) a prakticky jediná možnost jak rozklad čísla n nalézt, je postupně testovat jeho dělitelnost přirozenými čísly ≤

 n . Snadno se přesvědčíme (číslo n mívá

kolem 400 dekadických míst), že tento postup je mimo možnosti jakékoliv současné výpočetní techniky. Nyní podrobněji k RSA metodě.


strana 57

♦

RSA kódování. Pro kódovaní máme k dispozici již zmíněný veřejný klíč, tj. dvojici čísel (n, e ) . Nejprve kódovanou právu převedeme do podoby čísla B (např. každému znaku přiřadíme jeho pořadí v rámci abecedy), které pak rozdělíme na bloky B1 ,… , Bl (blok je například tvořen čtyřmi ciframi). Nyní jednotlivé bloky zakódujeme dle vztahu K i ≡ Bie (mod n ), i = 1,… , l .

(1.50)

Původní zprávě pak odpovídá kód skládající se z bloků K 1 ,… , K l . ♦

RSA dekódování. Pro dekódování máme k dispozici trojici čísel

( p, q, e ) ,

kde NSD(e, ( p − 1) ⋅ (q − 1)) = 1 ,

n = p ⋅ q a samozřejmě zprávu K 1 ,… , K l zakódovanou dle (1.50). K dekódování použijeme vztah

Bi ≡ K id (mod n ), i = 1,… , l ,

(1.51)

kde d je nejmenší nezáporný zbytek vyhovující kongruenci d ⋅ e ≡ 1 (mod ( p − 1) ⋅ (q − 1)) .

(1.52)

Z podmínky NSD(e, ( p − 1) ⋅ (q − 1)) = 1 vyplývá (viz věta 1.7.1), že číslo d existuje a je určeno jednoznačně. Odtud dostáváme

( )

K id = Bie

d

= Bi1+t ⋅( p −1)⋅(q −1) .

(Připomeňme, že 1.52 lze přepsat na de = 1 + t ⋅ ( p − 1) ⋅ (q − 1) pro jisté t ∈ Z .) Z malé Fermatovy věty dostáváme (vzhledem k volbě prvočísel p a q)

Bip −1 ≡ 1 (mod p ) , Biq −1 ≡ 1 (mod q ) , tedy

(

K id ≡ Bi ⋅ Bip −1

)(

t ⋅ q −1)

(

≡ Bi (mod p ) , K id ≡ Bi ⋅ Biq −1

)(

t ⋅ p −1)

≡ Bi (mod q ) .

Z věty 1.6.3 část d) vyplývá, že K id ≡ Bi (mod p ⋅ q ) a tedy uvedený postup skutečně vede k dekódování.

Příklad 1.7.5 Pomocí RSA metody: a) zakódujte slovo KRALOVKA, použijte veřejný klíč (n, e ) = (3337, 9) , b) dekódujte slovo 3149


2883 2177 , máte-li klíč ( p, q, e ) = (67, 83, 13) .

strana 58

Řešení. Poznamenejme, že jde pouze o prezentaci principu RSA metody, proto je hodnota veřejného klíče n (tedy i prvočísel p, q) malá. Skutečně používané hodnoty mívají stovky cifer. ad a) Nejprve slovo KRALOVKA převedeme do posloupnosti čísel, které vyjadřují pořadí jednotlivých znaků v rámci (anglické) abecedy. Dostáváme tak 11, 18, 01, 12, 15, 22, 11, 01 . Tato čísla seskupíme do bloků (například po dvou číslech) 1118 0112 1522 1101 a tyto bloky nyní zakódujeme (vyjádříme v soustavě nejmenších nezáporných zbytků modulo n) dle vztahu (1.50), tj. K i ≡ Bi9 (mod 3337 ) . Dostáváme tak 2550 ≡ 1118 9 (mod 3337 ) , 2508 ≡ 0112 9 (mod 3337 ) , 0816 ≡ 1522 9 (mod 3337 ) , 2504 ≡ 11019 (mod 3337 ) . Slovu KRALOVKA proto odpovídá kód 2550 2508 0816 2504 . ad b) Nejprve z klíče ( p, q, e ) = (67, 83, 13) vypočteme dekódovací klíč d. Poznamenejme, že čísla p, q zná pouze příjemce zprávy a tedy pouze on je schopen určit dekódovací klíč (odesilatelé znají veřejný klíč, tj. hodnotu součinu n = p ⋅ q a číslo e, což jim umožňuje

zprávy kódovat, nikoliv dekódovat). V souladu s poznámkou 1.7.3 určíme dekódovací klíč d jako řešení (nejmenší nezáporný zbytek) nám již dobře známého typu kongruence d ⋅ e ≡ 1 (mod ( p − 1) ⋅ (q − 1)) , tj. 13d ≡ 1 (mod 5412 ) . Aplikací věty 1.7.1 dostáváme d = 1249 .

Nyní

provedeme

vlastní

dekódování

dle

vztahu

(1.51),

tj.

Bi ≡ K i1249 (mod 5561) .

Dostáváme tak 1005 ≡ 31491249 (mod 5561) , 1920 ≡ 28831249 (mod 5561) , 0504 ≡ 21771249 (mod 5561) a tedy pořadová čísla jednotlivých znaků původní zprávy jsou 10, 05, 19, 20, 05, 04 . Nyní již snadno zjistíme, že zakódováno slovo bylo JESTED. ¶


strana 59

Kapitola 2. Kombinatorika

Systematický rozvoj kombinatoriky lze datovat do 17. století a je spojen se jmény Blaise Pascal, Pierre Fermat, Christian Huygens a Jacob Bernoulli. Hlavní pozornost se soustředila především na řešení různých otázek spojených s problematikou hazardních her, loterií apod. V tomto kontextu lze nejjednodušší úlohu kombinatoriky formulovat následovně - kolika různými způsoby je možné z n objektů vybrat k-tici (tj. k objektů). V závislosti na podmínkách, které definují „různé způsoby výběru“, se dostáváme k následujícím základním kombinatorickým pojmům - variace, permutace a kombinace. První představu o obsahu těchto pojmů si lze udělat z následujícího schématu:

Základní kombinatorické pojmy

Variace

Permutace

Kombinace

záleží na pořadí prvků v k-tici

vybíráme všechny prvky

nezáleží na pořadí prvků v k-tici

I v současné době se kombinatorika dále rozvíjí a s jejími aplikacemi se lze setkat v celé řadě velmi různých oblastí. Například fyzika elementárních částic, pojišťovnictví a bankovnictví, kódování, teorie složitosti, výpočetní technika apod.


strana 60

2.1

Základní pravidla kombinatoriky

Při řešení kombinatorických úloh velmi rychle zjistíme, že většina z nich má tu nepříjemnou vlastnost, že nemůže být řešena „metodou hrubé síly“, kdy hledáme řešení výčtem, resp. vyzkoušením všech možností. Ukazuje se, že tento přístup k řešení kombinatorických úloh je i mimo možnosti současné výpočetní techniky. Z těchto důvodů jsou potřebná základní kombinatorická pravidla a metody, jejichž vhodnou aplikací lze vyřešit většinu běžných, někdy i netriviálních, kombinatorických úloh. Jde především o pravidlo součtu, pravidlo součinu, Dirichletův princip a princip inkluze a exkluze.

Pravidlo součtu Nechť množina A = {a1 ,… , am } obsahuje m různých prvků a množina B = {b1 ,… , bn } n různých prvků, navíc A ∩ B = ∅ . Potom jeden prvek z množiny A ∪ B lze vybrat m + n různými způsoby. Důkaz. Vzhledem k předpokladu disjunktnosti množin A, B je pravidlo součtu ekvivalentní se zřejmým tvrzením A ∪ B = A + B . ¶

Příklad 2.1.1 Určete hodnotu, kterou nabude proměnná r po vykonání následujícího kódu:

r := 0; for i1 := 1 to n1 do r := r + 1; for i2 := 1 to n 2 do r := r + 1; for ik := 1 to nk do r := r + 1; Řešení. Je zřejmé, že počet iterací j-tého cyklu „for“ je nezávislý na hodnotách ostatních čítačů a tedy proběhne právě n j − krát . Aplikací pravidla součtu tak pro hodnotu proměnné r dostáváme

r = n1 + … + nk . ¶


strana 61

Pravidlo součinu Nechť množina A = {a1 ,… , am } obsahuje m různých prvků (tj.

A = m ) a množina

B = {b1 ,… , bn } n různých prvků (tj. B = n ). Potom uspořádanou dvojici prvků (ai , b j ), kde

ai ∈ A, b j ∈ B lze vybrat m ⋅ n různými způsoby. Důkaz. Pravidlo součinu je ekvivalentní se zřejmým tvrzením

A × B = A ⋅ B , kde symbol ×

označuje kartézský součin. Schématicky lze toto pravidlo znázornit maticí  ( a1 , b1 )  (a , b ) A× B =  2 1  ( am , b1 ) 

( a1 , b2 ) ( a2 , b2 ) ( am , b2 )

( a1 , bn )  ( a2 , bn ) 

,  ( am , bn )

která obsahuje (právě jednou) všechny uspořádané dvojice (ai , b j ), i = 1,… m, j = 1,… , n . ¶

Příklad 2.1.2 Určete hodnotu, kterou nabude proměnná r po vykonání následujícího kódu: r := 0; for i1 := 1 to n1 do for i2 := 1 to n 2 do for ik := 1 to nk do r := r + 1; Řešení. Cykly „for“ jsou do sebe vnořené, tedy při každé změně čítače jsou opakovaně provedeny všechny vnitřní cykly. Aplikací pravidla součinu tak pro hodnotu proměnné r dostáváme r = n1 ⋅… ⋅ nk . ¶

Poznámka 2.1.1 ♦

Pravidlo součtu lze snadno zobecnit na případ více množin. Jsou-li A1 ,… , An po dvou disjunktní množiny (tj. ∀i ≠ j platí Ai ∩ A j = ∅ ), dostáváme A1 ∪ A2 ∪ … ∪ Ak = A1 + A2 + … + Ak .


strana 62

V případě, kdy není podmínka disjunktnosti (každé dvojice množin) splněna, pravidlo součtu neplatí a je třeba použít princip inkluze a exkluze (viz dále poznámka 2.1.2). ♦

Pravidlo součinu lze také snadno zobecnit na případ více množin. Dostáváme tak A1 × A2 ×… × Ak = A1 ⋅ A2 ⋅… ⋅ Ak .

Příklad 2.1.3 Kolik různých automobilových značek lze vytvořit při dodržení těchto pravidel – značka začíná libovolnou skupinou dvou nebo tří písmen a následuje libovolná skupina čtyř cifer. Řešení. Značky rozdělíme podle počtu písmen do dvou disjunktních skupin: A - značky začínající 2 písmeny a B – začínající 3 písmeny. Využitím pravidla součinu zjistíme počty značek v každé skupině (k dispozici máme 26 písmen a 10 cifer). Skupina A:

písmeno 26

písmeno 26

cifra 10

cifra 10

cifra 10

cifra 10

Skupina A obsahuje nA = 262 ⋅104 = 6 760 000 různých značek. Skupina B:

písmeno 26

písmeno 26

písmeno 26

cifra 10

cifra 10

cifra 10

cifra 10

Skupina B obsahuje nB = 263 ⋅104 = 175 760 000 různých značek. Podle pravidla součtu tak pro celkový počet dostáváme nA + nB = 182 520 000 různých poznávacích značek. ¶

Princip inkluze a exkluze

(

Označme N celkový počet objektů, a1 ,… , an jejich možné vlastnosti a N ai1 ,… , aik

)

počet

všech objektů, které mají vlastnosti uvedené v závorce, tj. ai1 ,… , aik (a to bez ohledu na to, zda mají některé další vlastnosti). Potom pro počet N ( a1 ,… , an ) objektů nemající žádnou z uvedených vlastností a1 ,… , an dostáváme N ( a1 ,… , an ) = N − N ( a1 ) − … − N ( an ) + + N ( a1 , a2 ) + N ( a1 , a3 ) + … + N ( an −1 , an ) +


strana 63

−  N ( a1 , a2 , a3 ) + N ( a1 , a2 , a4 ) + … + N ( an − 2 , an −1 , an )  +

[

]

+ (− 1) ⋅ N (a1 ,… , a j −1 , a j ) + N (a1 ,… , a j −1 , a j +1 ) + … + N (a n − j +1 ,… , a n −1 , a n ) + j

+ ( −1) ⋅ N ( a1 ,… , an ) . n

Důkaz. Matematickou indukcí dle n, tj. dle počtu vlastností. Pro n = 1 má princip inkluze a exkluze zřejmě platný tvar N ( a1 ) = N − N ( a1 ) . Předpokládejme nyní jeho platnost pro libovolnou skupinu předmětů a n − 1 vlastností, tj. N ( a1 ,… , an −1 ) = N − N ( a1 ) − … − N ( an −1 ) + + N ( a1 , a2 ) + N ( a1 , a3 ) + … + N ( an − 2 , an −1 ) +

−  N ( a1 , a2 , a3 ) + N ( a1 , a2 , a4 ) + … + N ( an −3 , an − 2 , an −1 )  +

+ ( −1)

n −1

⋅ N ( a1 ,… , an −1 ) .

Aplikací tohoto předpokladu na skupinu předmětů majících vlastnost an dostáváme N ( a1 ,… , an −1 , an ) = N ( an ) − N ( a1 , an ) − … − N ( an −1 , an ) + + N ( a1 , a2 , an ) + N ( a1 , a3 , an ) + … + N ( an − 2 , an −1 , an ) +

−  N ( a1 , a2 , a3 , an ) + N ( a1 , a2 , a4 , an ) + … + N ( an −3 , an − 2 , an −1 , an )  +

+ ( −1)

n −1

⋅ N ( a1 ,… , an ) .

Dále zřejmě platí N ( a1 , a2 ,… , an ) = N ( a1 , a2 ,… , an −1 ) − N ( a1 , a2 ,… , an −1 , an ) a po dosazení výše uvedených vztahů a elementární úpravě dostáváme dokazované tvrzení. ¶


strana 64

Poznámka 2.1.2 ♦

Množinově bývá princip inkluze a exkluze zapisován ve tvaru n

n

∪A =∑ A i

i =1

♦

i =1

i

−

∑

1≤i1
Ai1 ∩ Ai2 +

∑

1≤i1 < i2 < i3 ≤ n

Ai1 ∩ Ai2 ∩ Ai3 − … + ( −1) A1 ∩ A2 ∩ … ∩ An . n

Speciálně v případě n = 2 dostáváme N ( a1 , a2 ) = N − N ( a1 ) − N ( a2 ) + N ( a1 , a2 ) ,

resp. A1 ∪ A2 = A1 + A2 − A1 ∩ A2 .

V případě n = 3 dostáváme N (a1 , a 2 , a3 ) = N − N (a1 ) − N (a 2 ) − N (a3 ) + + N (a1 , a 2 ) + N (a1 , a3 ) + N (a 2 , a3 ) − N (a1 , a 2 , a3 ) , resp. A1 ∪ A2 ∪ A3 = A1 + A2 + A3 − A1 ∩ A2 − A1 ∩ A2 − A2 ∩ A3 + A1 ∩ A2 ∩ A3 .

Oba případy lze přehledně znázornit následujícími Vennovými diagramy N ( a1 , a2 )

N ( a1 )

N ( a2 ) N ( a1 , a2 )

N ( a1 , a2 )

N ( a1 )

N ( a2 )

N ( a1 , a3 )

N ( a1 , a2 , a3 ) N ( a2 , a3 )

N ( a3 ) N ( a1 , a2 , a3 )

♦

V symbolické a poněkud přehlednější formě lze princip inkluze a exkluze zapsat ve tvaru N ( a1 , a2 ,… , an ) = N (1 − a1 )(1 − a2 )… (1 − an ) .

Po formálním roznásobení pravé strany dostaneme formuli, která odpovídá principu inkluze a exkluze.


strana 65

Příklad 2.1.4 V posloupnosti 1,2, …, 999 999 určete počet čísel, která nejsou dělitelná (beze zbytku) žádným z čísel 3, 5, 7. Řešení. Označme

N ( i ) počet čísel dané posloupnosti, která jsou dělitelná číslem i, N ( i, j ) počet čísel dané posloupnosti, která jsou dělitelná současně i a j, N ( i, j , k ) počet čísel dané posloupnosti, která jsou dělitelná současně i, j, k.

Zřejmě

 999 999  N ( 3) =   = 333 333 , 3 

 999 999  N ( 5) =   = 199 999 , 5 

 999 999  N (7) =   = 142 857 , 7 

 999 999  N ( 3, 5 ) =  = 66 666 ,  3 ⋅ 5 

 999 999  N (3, 7 ) =   = 47 619 ,  3⋅7 

 999 999  N ( 5, 7 ) =  = 28 571 ,  5 ⋅ 7 

 999 999  N (3, 5, 7 ) =   = 9 523 ,  3⋅5⋅7 

N = 999 999 .

Aplikací principu inkluze a exkluze dostáváme hledaný výsledek N ( 3, 5, 7 ) = N − N ( 3) − N ( 5 ) − N ( 7 ) + N ( 3, 5 ) + N ( 3, 7 ) + N ( 5, 7 ) − N ( 3, 5, 7 ) = = 999 999 − 333 333 − 199 999 − 142 857 + 66 666 + 47 619 + 28 571 − 9 523 = 457 143. ¶

Dirichletův princip (P. G. L. Dirichlet, 1805 – 1859) Při libovolném rozmístění n objektů do k přihrádek, musí alespoň jedna z nich obsahovat n nejméně   objektů. k 

Důkaz. n Sporem – každá z přihrádek obsahuje nejvýše   − 1 objektů. Pro n tak zřejmě dostáváme k  n  n n horní odhad n ≤ k ⋅    − 1 . Z poznámky 1.4.2 víme, že   < + 1 , tudíž musí platit k  k k   n   n   n ≤ k ⋅    − 1 < k ⋅   + 1 − 1 = n . Spor - alespoň jedna přihrádka obsahuje nejméně k    k  

n  k 

objektů. ¶ Diskrétní matematika II

strana 66

Příklad 2.1.5 Určete minimální počet obyvatel města, víte-li, že alespoň 15 lidí má ve stejný den a měsíc narozeniny (k roku nepřihlížíme a předpokládáme 365 dní v roce). Řešení. Dny v roce reprezentují „přihrádky“, tj. k = 365, kde v alespoň jedné má být 15 objektů (lidí mající narozeniny ve stejné datum). Z Dirichletova principu vyplývá, že hledáme nejmenší  n  přirozené n takové, aby  ≥ 15 . Odtud n = 14 ⋅ 365 + 1 = 5 111 . ¶  365 

Jako zajímavý důsledek Dirichletova principu dostáváme následující větu.

Věta 2.1.1 (P. Erdös, G. Szekeres, 1935) Každá posloupnost n 2 + 1 různých reálných čísel obsahuje buď rostoucí, nebo klesající podposloupnost délky alespoň n + 1 . Důkaz. Označme x1 ,… , x n 2 +1 uvažovanou posloupnost různých reálných čísel. Dále pokračujme sporem, tj. předpokládejme, že každá rostoucí, resp. klesající posloupnost vybraná z x1 ,… , x n 2 +1 obsahuje nejvýše n členů. Nyní každému členu xk dané posloupnosti přiřadíme

uspořádanou dvojici (ik , j k ), 1 ≤ k ≤ n 2 + 1 , kde ik je maximální délka klesající posloupnosti, kterou lze vybrat z prvních k členů x1 ,… , x k , tj.

{

ik = max i ∃1 ≤ k1 <… < ki ≤ k : : ak1 > ak 2 >… > ak i

}

a j k je maximální délka rostoucí posloupnosti, kterou lze vybrat z členů x1 ,… , x k , tj.

{

}

jk = max j ∃1 ≤ k1 <… < k j ≤ k : : ak1 < ak 2 <… < ak j .

Vzhledem k předpokladu (existence rostoucí, resp. klesající posloupnosti délky nejvýše n) a definici čísel ik a jk zřejmě platí 1 ≤ ik , jk ≤ n a dle pravidla součinu existuje nejvýše n 2 různých dvojic. Z Dirichletova principu tak vyplývá, že v dané posloupnosti délky n 2 + 1 existují alespoň dva různé členy xr, xs, kde r < s , takové, že ir = is a jr = js. Zřejmě platí – buď xr < xs , nebo xr > xs . Je-li x r < x s , potom mezi členy x1 ,… , x r ,… , x s existuje rostoucí

posloupnost délky alespoň j r + 1 , což vede ke sporu a tedy v posloupnosti x1 ,… , x n 2 +1 existuje rostoucí posloupnost délky alespoň n + 1 .


strana 67

Analogicky vede ke sporu i situace, kdy x r > x s , neboť v tomto případě existuje mezi členy x1 ,… , x r ,… , x s klesající posloupnost délky nejméně ir + 1 a tedy v posloupnosti x1 ,… , x n 2 +1

musí existovat klesající posloupnost délky alespoň n + 1 . ¶

Na závěr tohoto odstavce uveďme, že různé matematické zákonitosti lze využít k zábavě i poučení. Například se lze vsadit, že z libovolné řady šestnácti různě vysokých žáků je možné vybrat alespoň pět, kteří budou seřazeni dle velikosti (vzestupně, resp. sestupně).

Příklad 2.1.6 Z věty 2.1.1 víme, že každá posloupnost n 2 + 1 různých reálných čísel obsahuje buď rostoucí, nebo klesající podposloupnost délky alespoň n + 1 . Z důkazu je pak zřejmé, že počet členů n 2 + 1 je nejmenší možný. Nalezněte posloupnost obsahující n 2 různých čísel, která uvedenou

vlastnost nemá, tj. neobsahuje rostoucí ani klesající podposloupnost délky n + 1 . Řešení. Uspořádejme čísla 1, 2,… , n 2 do následující čtvercové matice řádu n.  n 2n 3n   n − 1 2n − 1 3n − 1  n 2 2n 2 3n 2 − −  −   n + 1 2n + 1  1

(n − 1) ⋅ n (n − 1) ⋅ n − 1 (n − 1) ⋅ n − 2

  … n −1   … n2 − 2    … (n − 2 ) ⋅ n + 1 (n − 1) ⋅ n + 1 …

n2

2

Pro další úvahu je podstatné, že prvky každého řádku tvoří rostoucí posloupnost n čísel a naopak, prvky každého sloupce tvoří klesající posloupnost n čísel. Pokud nyní z uvedené matice vybereme n + 1 čísel, musíme vybrat prvky z alespoň dvou řádků, resp. sloupců a tedy uvedených n + 1 čísel nemůže tvořit rostoucí ani klesající posloupnost. Nyní je zřejmé, že hledanou posloupnost vytvoříme z jednotlivých řádků matice uspořádaných od prvního k ntému. ¶ Pro potřeby dalších odstavců připomeňme, že pro m ∈ N označujeme součin 1 ⋅ 2 ⋅ … ⋅ m symbolem m ! (čteme m faktoriál) a definujeme 0!= 1 .


strana 68

2.2

Variace, permutace, kombinace

Nyní je vhodné se vrátit k exaktnějšímu vymezení základních kombinatorických pojmů variace, permutace a kombinace.

Definice 2.2.1 – Variace bez opakování Označme M množinu obsahující m různých prvků. Variací k-té třídy z m prvků (resp. na mprvkové množině M) nazýváme každou uspořádanou k-tici navzájem různých prvků z množiny M. Počet všech variací k-té třídy z m prvků označíme Amk . ¶

Stručně lze variace bez opakování charakterizovat jako uspořádané k-tice (tj. záleží na pořadí prvků ve vybrané k-tici), ve které se jednotlivé prvky nesmí opakovat. Dvě variace (bez opakování) považujeme tedy za různé, pokud obsahují různé prvky nebo se liší v pořadí některých prvků.

Věta 2.2.1 Pro libovolné přirozené k a m, kde 1 ≤ k ≤ m platí Amk = m ⋅ ( m − 1) ⋅… ⋅ ( m − k + 1) =

m ! (m − k ) !

(2.1)

Důkaz. Počty prvků, které jsou na „výběr“ při obsazování jednotlivých pozic ve variaci (bez opakování), jsou zřejmě dány následující tabulkou: 1. pozice

m

2. pozice m-1

… …

k-tá pozice m–k+1

Dle pravidla součinu tak dostáváme platnost tvrzení. ¶

Definice 2.2.2 – Variace s opakováním Označme M množinu obsahující m různých druhů prvků (v „neomezeném“ množství). Variací

k-té třídy z m prvků s opakováním (resp. s opakováním na m-prvkové množině M) nazýváme


strana 69

každou uspořádanou k-tici prvků vytvořenou z libovolných druhů prvků množiny M. Počet všech variací k-té třídy z m prvků s opakováním označíme Amk . ¶

Stručně lze variace s opakováním charakterizovat jako uspořádané k-tice (tj. záleží na pořadí prvků ve vybrané k-tici), ve které se jednotlivé druhy prvků mohou vícekrát opakovat. Dvě variace s opakováním považujeme za různé, pokud se liší v pořadí některých prvků nebo v počtu prvků některého druhu.

Věta 2.2.2 Pro libovolné přirozené k a m platí

Amk = m k .

(2.2)

Důkaz. Počty prvků, kterými lze obsadit jednotlivé pozice ve variaci s opakováním, jsou zřejmě dány následující tabulkou (druhy se mohou opakovat!): 1. pozice

2. pozice

m

m

…

k-tá pozice m

Dle pravidla součinu tak dostáváme platnost tvrzení. ¶

Poznámka 2.2.1 Variace k-té třídy z m prvků lze definovat pomocí pojmu zobrazení. Označme K = {1, 2,… , k } a M = {a1 ,… , a m } množinu obsahující m různých prvků. ♦

Variace k-té třídy z m prvků bez opakování

(1 ≤ k ≤ m )

odpovídají všem prostým

zobrazením K do M. (Řádně zdůvodněte!) ♦

Variace k-té třídy z m prvků s opakováním odpovídají všem zobrazením K do M . (Řádně zdůvodněte!)

Příklad 2.2.1 – Variace 2 třídy na 3 prvkové množině M = {a, b, c} Pro počet všech variací 2 třídy ze 3 prvků dostáváme:


strana 70

3 ! =6, (3 − 2) !

♦

v případě variací bez opakování A32 =

♦

v případě variací s opakováním A32 = 32 = 9 .

Pro ilustraci obsahuje následující tabulka přehled všech uvažovaných variací. Variace 2 třídy ze 3 prvků bez opakování s opakováním (a, b) (b, a) (a, b) (b, a) (a, a) (a, c) (c, a) (a, c) (c, a) (b, b) (b, c) (c, b) (b, c) (c, b) (c, c) ¶

Příklad 2.2.2 Určete počet všech podmnožin libovolné n prvkové množiny A. Řešení. Označme A = {a1 , a2 ,… , an } . Každé podmnožině B ⊆ A lze přiřadit uspořádanou n-tici

( x1 , x2 ,… , xn ) , nazývaný charakteristický vektor podmnožiny B, kde xi =

1, jestliže ai ∈ B , 0, jestliže ai ∉ B .

Podmnožiny jsou tedy jednoznačně definovány výše uvedenou variací n-té třídy ze dvou prvků

{0, 1}

s opakováním. Naopak, každá taková variace jednoznačně definuje jistou

podmnožinu množiny A a tudíž počet všech podmnožin n-prvkové množiny je roven počtu variací n-té třídy ze dvou prvků s opakováním, tj. A2n = 2n . ¶

Systém všech podmnožin množiny A se běžně označuje některým z následujících symbolů: P ( A ) , B ( A ) , 2 A a nazývá se potenční množina množiny A, resp. boolean množiny A a jak

vyplývá z výše uvedeného příkladu platí P ( A) = 2 . A

(2.3)

Připomeňme, že P ( ∅ ) = ∅ , P ({∅}) = {∅, {∅}} ,

P ({a, b, c}) = {∅, {a} , {b} , {c} , {a, b} , {a, c} , {b, c} , {a, b, c}} . Diskrétní matematika II

strana 71

Definice 2.2.3 – Permutace bez opakování Označme M množinu obsahující m různých prvků. Permutací řádu m (resp. na množině M) nazveme jejich libovolné uspořádání. Počet všech permutací řádu m označíme P ( m ) . ¶

Poznámka 2.2.2 a) Permutace řádu m jsou speciálním případem variací bez opakování, totiž variace m-té třídy z m prvků. Odtud je zřejmé, že dvě permutace (téhož řádu) považujeme za různé, jestliže se liší pořadím prvků. b) Permutace na množině M jednoznačně korespondují se všemi prostými zobrazeními množiny M na sebe (tzv. bijektivní zobrazení na M). (Řádně zdůvodněte!) c) Pro počet permutací na m prvkové množině platí rekurentní vztah P ( m ) = m ⋅ P ( m − 1) ,

(2.4)

kde definujeme P ( 0 ) = 1 . Se vztahem (2.4) se ještě setkáme v celé řadě souvislostí. Pro tuto chvíli uveďme jeho kombinatorickou interpretaci. Množinu všech permutací na množině

{a1 ,… , a m }

rozložíme do m tříd A1 ,… , Am , kde třída Ai obsahuje právě všechny permutace, které mají na i-té pozici prvek a n . Snadno zjistíme, že takto definované třídy tvoří skutečný rozklad (jsou po dvou disjunktní a jejich sjednocení „pokrývá“ všechny uvažované permutace)

a

∀i, j ∈ {1,… , m}

navíc

z důvodu

„symetrie“

mají

stejný

počet

prvků,

tj.

Ai = A j . Z definice jednotlivých tříd pak vyplývá, že Ai = P(m − 1) ,

m

tedy P(m ) = ∑ Ai = m ⋅ P(m − 1) . i =1

Věta 2.2.3 Pro libovolné přirozené m platí P(m ) = m !

(2.5)

kde definujeme 0! = 1. Důkaz. Počet možností jak obsadit jednotlivé pozice v permutaci jsou zřejmě dány tabulkou: 1. pozice m Diskrétní matematika II

2. pozice m-1

… …

m-tá pozice 1 strana 72

Podle pravidla součinu dostáváme P(m ) = m ! . Jiný snadný způsob důkazu vychází z poznámky 2.2.2 a) a věty 2.2.1, odkud vyplývá, že P(m ) = Amm .¶

Příklad 2.2.3 – Permutace bez opakování. Položme M = {a, b, c}. Pro počet všech permutací na množině M platí P(3) = 3!= 6 . Pro ilustraci obsahuje následující tabulka přehled všech uvažovaných permutací. Permutace řádu 3 (a, b, c) (b, a, c) (c, a, b) (a, c, b) (b, c, a) (c, b, a) ¶

Definice 2.2.4 – Permutace s opakováním Nechť množina M obsahuje m1 nerozlišitelných prvků 1. druhu, m2 nerozlišitelných prvků 2. druhu až mk nerozlišitelných prvků k-tého druhu, kde 1 ≤ k, mi . Potom každé uspořádání této množiny nazveme permutací s opakováním řádu

(m1 ,… , mk ) .

Počet všech permutací s

opakováním řádu (m1 ,… , mk ) označíme P(m1 ,… , mk ) . ¶

Věta 2.3.3 Pro libovolná přirozená čísla m1 ,… , mk platí P(m1 ,… , mk ) =

(m1 + … + mk )! m1 !⋅ … ⋅ mk !

.

(2.6)

Důkaz.   Označme M =  a,… , a , b,… , b ,… , r ,… , r  , kde m = m1 + … + mk množinu prvků, ze kterých  m1  m2 mk budou vytvářeny permutace. Každá permutace s opakováním na množině M je zřejmě invariantní vzhledem k permutacím prvků jednotlivých druhů, tj. výsledná permutace se nemění při záměně prvků stejného druhu. Prvky i-tého druhu lze permutovat mi ! způsoby a tedy podle pravidla součinu dostáváme P(m1 + … + mk ) = P(m1 ,… , mk ) ⋅ m1 !⋅ … ⋅ mk !, odkud je platnost (2.6) zřejmá. ¶


strana 73

Příklad 2.2.4 – Permutace s opakováním. Určete všechny permutace na množině M = {a, a, b, c} . Řešení. Zřejmě jde o permutace s opakováním řádu ( 2, 1, 1) . Ze vztahu (2.6) tak pro jejich počet dostáváme P(2,1,1) =

(2 + 1 + 1)! = 12 . 2!⋅ 1!⋅ 1!

Pro ilustraci obsahuje následující tabulka přehled všech uvažovaných permutací. Permutace s opakováním řádu (2,1,1) (a, a, b, c) (a, a, c, b) (b, a, a, c) (c, a, a, b) (a, b, a, c) (a, c, a, b) (b, a, c, a) (c, a, b, a) (a, b, c, a) (a, c, b, a) (b, c, a, a) (c, b, a, a) ¶

Příklad 2.2.5 Kolik různých slov (bez ohledu na to, zda dávají nějaký smysl) lze sestavit při využití všech písmen slova POPOKATEPETL. Řešení. Evidentně jde o permutace s opakováním na množině M = { A, E , E , K , L, O, O, P, P, P, T , T } , tedy hledaný počet slov je roven P(1, 2,1,1, 2, 3, 2) =

12! = 9 979 200 . ¶ 1!⋅ 2!⋅ 1!⋅ 1!⋅ 2!⋅ 3!⋅ 2!

Poznámka 2.2.3 V dřívějších dobách se k utajení a následnému prokázání prvenství, např. vědeckých objevů, používaly anagramy. Ty spočívaly v seřazení všech písmen utajované zprávy v abecedním pořadí a následném uveřejnění. Při možných sporech o prvenství pak stačilo takovou zprávu opět sestavit do původní podoby. Uvědomme si, že teoretická šance na rozluštění takové zprávy byla mizivá (zdůvodněte!).

Definice 2.2.5 – Kombinace bez opakování Označme M množinu obsahující m různých prvků. Kombinací k-té třídy z m prvků (resp. na m-prvkové množině M) nazýváme každou k-tici navzájem různých prvků z množiny M. Počet kombinací k-té třídy z m prvků (bez opakování) budeme značit Cmk . ¶ Diskrétní matematika II

strana 74

Stručně lze kombinace k-té třídy (bez opakování) charakterizovat jako neuspořádané k-tice, ve které se prvky nesmí opakovat. Dvě kombinace považujeme za různé, jestliže se liší v zastoupení některého prvku (bez ohledu na pozici jejich výskytu).

Poznámka 2.2.4 Číslo Cmk se v závislosti na kontextu nazývá kombinační číslo, resp. binomický koeficient a  m označuje se také symbolem   , který čteme „m nad k“. k

Věta 2.2.4 Pro libovolná přirozená m, k , kde 0 ≤ k ≤ m platí

C mk =

m! . (m − k )!⋅ k !

(2.7)

Důkaz. Vzhledem k rozdílu mezi kombinacemi („nezáleží na pořadí“) a variacemi („záleží na pořadí“) je zřejmé, že z každé kombinace k-té třídy dostaneme k ! různých variací, které se liší pouze pořadím prvků. Odtud C mk =

Amk m! = .¶ k ! (m − k )!⋅ k !

Poznámka 2.2.5 – figurální čísla Zkoumáme-li počty uzlů „pravidelných“ grafů (trojúhelník, pětiúhelník, šestiúhelník atd. i jejich prostorových variant) a grafů z nich odvozených podle určitých pravidel, dostaneme se k pojmu figurální čísla. Například trojúhelníková čísla Tm , m = 0,1,… vyjadřují počty vrcholů následující posloupnosti grafů:

T0 = 1

T1 = 3

T2 = 6

T3 = 10

Velmi snadno zjistíme (dokažte!), že pro trojúhelníková čísla platí:


strana 75

♦

T0 = 1 a Tm = Tm −1 + m + 1, m = 1,… ,

♦

Tm = C m2 + 2 , m = 0,1,…

Prostorovou variantou výše uvedených grafů jsou následující grafy, které vedou k tzv. pyramidálním číslům Pm , m = 0,1,…

P0 = 1

P1 = 4

P2 = 10

Velmi snadno zjistíme (dokažte!), že pro pyramidální čísla platí: ♦

P0 = 1 a Pm = Pm −1 + Tm , m = 1,… ,

♦

Pm = C m3 +3 , m = 0,1,…

Věta 2.2.5 – základní vlastnosti kombinací Platí: a) Cmk = Cmm − k ,

(2.8)

b) Cmk = Cmk −−11 + Cmk −1 , (Pascalova identita)

(2.9)

c) C mk = P(k , m − k ) ,

(2.10)

d) Cm0 + Cm1 + … + Cmm = 2m .

(2.11)

Důkaz. Všechny výše uvedené vztahy lze snadno dokázat přímo, tj. porovnáním pravých a levých stran (samostatné cvičení) nebo následujícími kombinatorickými úvahami. Označme M = {a1 , a2 ,… , am } .

ad a) Každá kombinace k-té třídy z m prvků jednoznačně definuje doplňkovou kombinaci

( m − k ) − té

třídy (zbylé prvky) a tedy jejich počty musí být stejné, tj. Cmk = Cmm − k .

ad b) Množinu všech kombinací k-té třídy na M rozložíme na dvě disjunktní množiny A1 , A2 . Do A1 zařadíme všechny kombinace, které obsahují prvek a1 , do A2 všechny zbývající. Zřejmě Cmk = A1 + A2 . Pro počet kombinací v množině A1 zřejmě platí A1 = Cmk −−11 (kombinace musí obsahovat prvek a1 , ostatních k − 1 prvků vybíráme


strana 76

libovolně z m − 1 zbývajících). Pro počet kombinací v A2 dostáváme A2 = Cmk −1 (vybíráme k prvků z m − 1 , neboť nesmíme použít a1 ). ad c) Každé kombinaci k-té třídy z m prvků přiřadíme uspořádanou m-tici ( x1 ,… , xm ) , kde xi =

1, jestliže prvek ai , je obsažen v dané kombinaci, 0, jestliže prvek ai , není obsažen v dané kombinaci.

Vztah mezi kombinacemi a výše definovanými uspořádanými m-ticemi, je vzájemně jednoznačný a proto jsou jejich počty stejné. Uvažované m-tice tvoří permutace s opakováním z k prvků prvního druhu (1) a ( m − k ) prvků druhého druhu (0) a tudíž Cmk = P ( k , m − k ) .

ad d) Pravá strana rovnosti vyjadřuje počet variací m-té třídy ze dvou prvků, např. {0, 1} . Množinu všech těchto variací rozložíme na m + 1 tříd A0 , A1 ,… , Am , kde Ai definujeme jako množinu obsahující všechny variace tvořené právě i jedničkami a m − i nulami. Zřejmě platí Ai = P ( i, m − i ) = Cmi a vzhledem k tomu, že množiny Ai jsou po dvou disjunktní (každá variace padne do právě jedné z uvedených množin), dostáváme 2m = A0 + A1 + … + Am , což bylo třeba dokázati. ¶

Uspořádejme nyní kombinační čísla do tzv. Pascalova trojúhelníku (schéma z obr. 2.2.1), jehož m-tý řádek obsahuje právě všechna kombinační čísla Cmk , k = 0, 1, … , m .

C00 C1k , k = 0,1

1

C 2k , k = 0,… , 2

1

C 3k , k = 0,… , 3

1

C 4k , k = 0,… , 4

1

C 5k , k = 0,… , 5

1

C 6k , k = 0,… , 6

1

C 7k , k = 0,… , 7

1

m


20

1

3

5 6

7

2

4

21

3

10

10

24

1 5

15 35

23

1 4

20 35

22

1

6

15

21

1

6 21

25

1

26

1 7

1

27

Obr. 2.2.1

strana 77

Nyní lze velmi snadno nahlédnout platnost vztahů a), b), d) z věty 2.2.5. Vztah a) lze interpretovat jako symetrii jednotlivých řádků (tj. k-té číslo zleva se rovná k-tému číslu zprava). Vztah b) vyjadřuje, že každé číslo ve schématu (které není „krajní“) je součtem dvou „sousedních“ čísel z předcházejícího řádku a vztah c) udává, že součet m-tého řádku je roven 2m . Kromě již uvedených základních vlastnosti (věta 2.2.5) lze snadno odhalit i kombinatoricky jinak méně evidentní zákonitosti. Například číslo z k-té pozice v m-tém řádku (které není „krajní“) je rovno součtu čísel na diagonále [m − k − 1, 0]  →[m − 1, k ] (první číslo v dvojici určuje řádek a druhé pozici v řádku). Platí tedy

C mk = C m0 − k −1 + C m1 − k + … + C mk −1 .

(2.12)

Pro další úvahy transformujme (otočme o 45° proti směru hodinových ručiček) Pascalův trojúhelník do poněkud výhodnějšího tvaru a doplňme „prázdné“ pozice odpovídající hodnotám Cmk pro k > m a k < 0 v souladu s vlastností b). Dostáváme tak schéma z obr. 2.2.2. Poznamenejme, že po této transformaci je každý prvek (od druhého řádku) součtem dvou čísel z předchozího řádku, z nichž jedno leží ve stejném sloupci a druhé vlevo vlastnost b).

k≤0

0≤k

C 0k

…

0

0

1

0

0

0

0

0

0

0

C1k

…

0

0

1

1

0

0

0

0

0

0

C 2k

…

0

0

1

2

1

0

0

0

0

0

C 3k

…

0

0

1

3

3

1

0

0

0

0

C 4k

…

0

0

1

4

6

4

1

0

0

0

C 5k

…

0

0

1

5

10

10

5

1

0

0

C 6k

…

0

0

1

6

15

20

15

6

1

0

C 7k

…

0

0

1

7

21

35

35

21

7

1

m ≥0 Obr. 2.2.2 Analogickým postupem, tj. využitím vlastnosti b), lze nyní výše uvedené schéma doplnit i o hodnoty odpovídající záporným m a přirozeným způsobem tak dodefinovat kombinační čísla

Cmk pro libovolné hodnoty k a m (v tomto případě se obvykle používá označení rozšířený,


strana 78

resp. zobecněný binomický koeficient). Situace je zachycena na obr. 2.2.3. Toto schéma se nazývá rozšířený aritmetický trojúhelník.

C −k7

…

0

0

1

-7

28

-84

210

-462

924

-1716

C

k −6

…

0

0

1

-6

21

-56

126

-252

462

-792

C

k −5

…

0

0

1

-5

15

-35

70

-126

210

-330

C

k −4

…

0

0

1

-4

10

-20

35

-56

84

-120

C

k −3

…

0

0

1

-3

6

-10

15

-21

28

-36

C

k −2

…

0

0

1

-2

3

-4

5

-6

7

-8

C

k −1

…

0

0

1

-1

1

-1

1

-1

1

-1

C 0k

…

0

0

1

0

0

0

0

0

0

0

k 1

…

0

0

1

1

0

0

0

0

0

0

C

k 2

…

0

0

1

2

1

0

0

0

0

0

C

k 3

…

0

0

1

3

3

1

0

0

0

0

C

k 4

…

0

0

1

4

6

4

1

0

0

0

C

k 5

…

0

0

1

5

10

10

5

1

0

0

C

k 6

…

0

0

1

6

15

20

15

6

1

0

C

k 7

…

0

0

1

7

21

35

35

21

7

1

C

m Obr. 2.2.3

Definice 2.2.6 Pro libovolná přirozená čísla k a m definujeme hodnoty rozšířených binomických koeficientů (kombinačních čísel) následovně:

m! , (m − k )!⋅ k !

♦

C mk =

♦

Cmk = 0 ,

♦

♦

pro 0 ≤ k ≤ m , pro 0 ≤ m < k ,

(2.13)

C−km = ( −1) ⋅ Cmk + k −1 ,

pro 0 ≤ k , 0 < m ,

(2.14)

Cm− k = 0 ,

pro 0 < k a m libovolné.

(2.15)

k

¶

Jak uvidíme později, odpovídá tato definice vlastnostem binomických koeficientů (kombinačních čísel) v kontextu jejich širšího využití. Diskrétní matematika II

strana 79

k

Příklad 2.2.6 V Brailleově systému jsou jednotlivé znaky abecedy, interpunkce apod. vyjádřeny pomocí zvýraznění různých kombinací různého počtu „výstupku“ na šestibodové matrici znázorněné na prvním obrázku (následující obrázky jsou ukázkou některých znaků a písmen).

;

m

t

Určete: a) Kolik různých znaků lze vyjádřit v Brailleově šestibodovém systému? b) Kolik znaků lze vyjádřit pomocí lichého počtu zvýrazněných bodů? Řešení. Nejprve očíslujme jednotlivé výstupky zleva dolů a následně zprava dolů čísly 1,… , 6 . ad a) Všechny potenciálně možné znaky rozdělíme podle počtu „výstupků“ do tříd

C0 , C1 , … , C6 , kde Ck obsahuje právě všechny možné symboly s k „výstupky“. Vzhledem k tomu, že záleží pouze na tom, které „výstupky“ byly zvoleny, např. středníku odpovídá dvojice 2, 3 (totéž jako 3, 2) a nikoliv na jejich pořadí, jde o kombinacemi bez opakování a tedy pro počty prvků jednotlivých tříd platí C k = C 6k , k = 0,1,… , 6 . 6

Odtud dostáváme pro celkový počet znaků

∑C k =0

k 6

= 26 = 64 .

ad b) V tomto případě, analogicky k části a), zřejmě dostáváme

C61 + C63 + C65 = 6 + 20 + 6 = 32 , tedy jinými slovy, je počet všech potenciálně možných znaků s lichým počtem „výstupků“ stejný jako se sudým. K tomuto výsledku lze dospět i bez výpočtu následující jednoduchou úvahou. U všech znaků, ve kterých se vyskytuje první „výstupek“ tento „výstupek“ zrušíme a naopak, kde se nevyskytuje ho zavedeme. Je zřejmé, že takto dostaneme opět všechny potenciálně možné znaky, navíc touto operací přejdou znaky s lichým počtem „výstupků“ na znaky se sudým počtem „výstupků“ a


strana 80

naopak. Počet znaků s lichým počtem „výstupků“ tak musí být stejný jako počet znaků se sudým počtem „výstupků“. ¶

Definice 2.2.7 – Kombinace s opakování Mějme k dispozici m různých druhů prvků (v „neomezeném“ množství). Kombinací k-té třídy z m prvků s opakováním (1 ≤ k , m ) nazveme libovolnou k-tici sestavenou z prvků uvedených

m druhů. Počet kombinací k-té třídy z m prvků s opakováním budeme značit Cmk . ¶

Stručně lze kombinace k-té třídy s opakováním charakterizovat jako neuspořádané k-tice, ve kterých se jednotlivé druhy prvků mohou opakovat. Dvě kombinace s opakováním považujeme za různé, jestliže se liší v počtu zastoupení prvků některého druhu (bez ohledu na pozici jejich výskytu).

Věta 2.2.5 Pro libovolná m ∈ N + , k ∈ N platí

Cmk = Cmk + k −1 .

(2.16)

Důkaz.

{a1 ,… , am } s opakováním

Každou kombinaci k-té třídy z m prvků

lze zakódovat do

uspořádané ( m + k − 1) – tice skládající se z k jedniček a ( m − 1) nul následovně. Nejprve rozmístíme ( m − 1) nul tak, aby mezi nimi vznikly mezery. Tím dostaneme m „přihrádek“ (viz následující schéma), do kterých rozmístíme k jedniček tak, aby zastupovaly druhy a počty prvků vyskytující se v kódované kombinaci. 1.

… 1.

0

( m −1) .

2.

…

0

2.

…

…

3.

( m −1).

0

… m.

m + k −1

Tedy do i-té „přihrádky“ umístíme tolik jedniček, kolikrát se v dané kombinaci vyskytuje prvek ai. Pokud se prvek v kombinaci nevyskytuje, necháme příslušnou „přihrádku“ prázdnou. Uvažme například kombinace 5-té třídy z 8 prvků {a1 ,… , a8 } . Dle výše uvedených pravidel tak kombinaci

( a1 , a3 , a3 , a6 , a8 )

zakódujeme do permutace 100110001001 ,

kombinaci ( a3 , a4 , a5 , a6 , a7 ) do permutace 001010101010 . Snadno tak nahlédneme, že všem


strana 81

kombinacím k-té třídy z m prvků s opakováním odpovídají právě všechny permutace s opakováním skládající se z k jedniček a m − 1 nul, tj. Cmk = P ( k , m − 1) = Cmk + k −1 . ¶

Příklad 2.2.5 – Kombinace 2 třídy na 3 prvkové množině M = {a, b, c} . Pro počet všech kombinací 2 třídy ze 3 prvků dostáváme: 3! = 3, 2! ⋅ ( 3 − 2 ) !

♦

v případě kombinací bez opakování C32 =

♦

v případě kombinací s opakováním C32 = C32+ 2−1 =

4! = 6. 2! ⋅ 2!

Pro ilustraci obsahuje následující tabulka přehled všech uvažovaných kombinací. Kombinace 2 třídy ze 3 prvků bez opakování s opakováním (a, b) (a, b) (a, a) (a, c) (a, c) (b, b) (b, c) (b, c) ( c, c) ¶

Příklad 2.2.6 Určete kolik existuje různých trojúhelníků, jejichž délky stran jsou přirozená čísla z množiny

{10, 11, 12, 13, 14, 15, 16, 17, 18, 19} . Řešení. Každý trojúhelník je jednoznačně určen délkami svých stran, tedy třemi čísly, které musí vyhovovat trojúhelníkové nerovnosti. Vzhledem k tomu, že libovolná tři čísla dané množiny vyhovují trojúhelníkové nerovnosti, je počet všech trojúhelníků roven počtu kombinací 3 třídy z 10 prvků s opakováním (strany mohou mít stejnou délku), tj. C103 = C123 = 220 . ¶

Poznámka 2.2.6 Po definici pojmů variace, kombinace a permutace lze přistoupit k některým ukázkám jejich využití, např. ve statistické fyzice. Základní úlohou statistické fyziky je určit, jak se vzhledem ke svým vlastnostem rozdělují fyzikální částice. Předpokládejme, že zkoumaný systém obsahuje k částic a existuje m různých fázových stavů, ve kterých se tyto částice mohou vyskytovat. V závislosti na jejich vlastnostech dostáváme následující modely. Diskrétní matematika II

strana 82

a) Maxwell-Boltzmannův model. Tento model nachází uplatnění v klasické fyzice (např. kinetická teorie plynů) a předpokládá, že částice jsou vzájemně rozlišitelné a každá z nich se může se stejnou pravděpodobností vyskytovat v libovolném fázovém stavu. Pro počet všech možných rozdělení částic tak dostáváme Amk = m k . b) Bose-Einsteinův model. Tento model nachází uplatnění např. ve kvantové fyzice a předpokládá, že částice (nazývané bosony) jsou vzájemně nerozlišitelné. Rozhodující je pouze počet částic v jednotlivých fázových stavech, proto počet všech možných rozdělení uvažovaných částic je Cmk . c) Fermi-Diracův model. Tento model nachází uplatnění v atomové fyzice a lze ho považovat za Bose-Einsteinův model omezený Pauliovým vylučovacím principem. Předpokládá, že každý fázový stav může obsahovat nejvýše jednu částici (nazývanou fermion). Pro počet všech možných rozdělení částic tak dostáváme Cmk , ( k ≤ m ) . ¶

Na závěr tohoto odstavce uvedeme přehledovou tabulku: Typ

Pořadí

Opakování

Kombinace

ne

ne

Cmk =

ne

ano

Cmk = Cmk + k −1 =

ano

ne

Amk =

ano

ano

Amk = m k

ano

ne

P ( m) = m !

ano

ano

P ( m1 ,… , mk ) =

Variace

Permutace


Označení m ! ( m − k ) ! ⋅k !

( m + k − 1) ! ( m − 1) ! ⋅ k

!

m ! (m − k ) !

( m1 + … + mk )

!

m1 ! ⋅…⋅ mk !

strana 83

2.3

Základní kombinatorické identity a úlohy

Kombinatorické úlohy lze řešit (resp. provést důkazy kombinatorických identit) v zásadě třemi následujícími způsoby: ♦

Přímá metoda – spočívá ve vhodné úpravě výrazů a využití různých obecně platných vztahů. Bývá technicky velmi náročná a je rozumně využitelná pouze v jednoduchých případech.

♦

Kombinatorická metoda – založena na kombinatorických úvahách. Technicky velmi jednoduchá a prakticky využitelná i ve složitějších případech. Této metodě se budeme věnovat především v tomto odstavci.

♦

Metody vytvořujících funkcí a rekurentních vztahů – obecné a velmi účinné metody. Jednoduše využitelné i ve složitých příkladech a důkazech. Těmto metodám se budeme věnovat v následujícím odstavci o rekurentních vztazích a o vytvořujících funkcích.

Věta 2.3.1 Platí m

ad a)

∑ (− 1) ⋅ C i

i =0

ad b) C

m +1 m+ k

i m

= 0.

(2.17)

k −1

= ∑ C mm+ i .

(2.18)

i =0 k

ad c) C mk + n = ∑ C mi ⋅ C nk −i , k ≤ min (m, n ) (Vandermondeova identita).

(2.19)

i =0

Důkaz. ad a) Uvedený vztah je zřejmě ekvivalentní s tvrzením, že počet všech kombinací sudého řádů z m prvků {a1 ,… , am } je roven počtu kombinací lichého řádu. Zvolme libovolně jeden prvek, např. a1 , a následně proveďme proceduru, při které ze všech kombinací obsahujících prvek a1 tento prvek odebereme a naopak do kombinací, které ho původně neobsahovaly, tento prvek přidáme. Z postupu je zřejmé, že opět dostaneme všechny kombinace z m prvků, navíc všechny kombinace lichého řádu přejdou na kombinace sudého řádu (ve všech kombinacích změníme počet prvků o jeden).


strana 84

ad b) Množinu všech kombinací (k − 1). třídy z (m + 2 ) prvků {a1 ,… , a m + 2 } s opakováním rozložíme do k tříd A0 , A1 ,… , Ak −1 , kde Ai je třída obsahující všechny kombinace

(k − 1).

třídy s opakováním, ve kterých se vyskytuje prvek a1 právě i-krát. Zřejmě tak

platí

C mk+−12 = C mk+−11 + C mk+−12 + … + C m1 +1 + C m0+1 . Využitím vztahu (2.16) pak dostáváme dokazovaný vztah. ad c) Množinu všech kombinací k-té třídy z m + n prvků {a1 ,… , am } ∪ {b1 ,… , bn } rozložíme podle počtu prvků z množiny {a1 ,… , am } do (k + 1) tříd A0 , A1 ,… , Ak , kde Ai je třída obsahující všechny kombinace, ve kterých je právě i prvků z množiny {a1 ,… , am } a k

(k − i ) prvků z množiny {b1 ,… , bn } . Zřejmě platí C mk + n = ∑ Ai i =0

, kde Ai = C mi ⋅ C nk −i . ¶

Výše uvedené identity nachází využití při řešení celé řady různých úloh. Jako příklad uvedeme vztahy pro výpočet součtů mocnin přirozených čísel. ♦

Ve vztahu (2.18) položme m = 1 . Dostáváme tak

C11 + C 21 + … + C k1 = C k2+1 . Odtud

1+…+ k =

k ⋅ (k + 1) . 2

(2.20)

(V tomto případě lze součet stanovit mnohem jednodušší úvahou, kterou použil desetiletý C.F. Gauss. Návod – sčítejte vhodné dvojice čísel.) ♦

Pro výpočet součtu druhých mocnin využijeme opět vztah (2.18), kde položíme m = 2 . Dostáváme tak C 22 + C 32 + … + C k2+1 = C k3+ 2 a po rozepsání

(

)

1 ⋅ 2 + 2 ⋅ 3 + … + k ⋅ (k + 1) = (1 + 2 + … + k ) + 12 + 2 2 + … + k 2 =

k ⋅ (k + 1) ⋅ (k + 2 ) . 3

Využitím (2.20) pak pro součet druhých mocnin dostáváme 12 + … + k 2 =

k ⋅ (k + 1) ⋅ (2k + 1) . 6

(2.21)

Analogicky lze pokračovat i v případě výpočtu součtu vyšších mocnin (volíme m = 3,… ).


strana 85

Věta 2.3.2 Platí a) P ( m ) = ( m − 1) ⋅  P ( m − 1) + P ( m − 2 )  .

(2.22)

b) P(k1 , k 2 ,… , k r ) = C nk1 ⋅ C nk−2 k1 ⋅ … ⋅ C nk−r −k11 −…− k r − 2 .

(2.23)

c)

∑

k1 +…kr = m

P ( k1 , k2 … , kr ) = r m .

(2.24)

kde se sčítá přes všechny uspořádané r-tice (k1 ,… , k r ) přirozených čísel, jejichž součet je roven m (tj. přes všechny rozklady čísla m na r sčítanců, na jejichž pořadí záleží). Důkaz. ad a) Důkaz je přenechán jako samostatné cvičení. Použijte kombinatorickou úvahu (návod – všechny permutace řádu m rozložte do (m − 1) vhodných tříd). ad b) Všechny permutace s opakováním z k1 prvků 1. druhu, k 2 prvků 2. druhu, …, k r prvků r-tého druhu, lze sestavit následovně. Nejprve vybereme k1 míst pro prvky 1. druhu, což lze provést C nk1 různými způsoby (všechny pozice jsou zatím volné). Následně vybereme k 2 míst pro prvky 2. druhu. Tato místa již vybíráme z n − k1 volných pozic, tj. Cnk−2 k1 způsoby. Analogicky postupujeme i v případě prvků ostatních druhů. Aplikací pravidla součinu pak dostáváme dokazovaný vztah. ad c) Pravá strana výrazu (2.24) je zřejmě rovna počtu všech variací m-té s opakováním na r prvkové množině {a1 ,… , a r } . Všechny takové variace lze rozložit podle počtu prvků jednotlivých druhů do tříd. Počet tříd je zřejmě roven počtu uspořádaných r-tic přirozených čísel P(k1 ,

(k1 ,… , k r ) ,

kde k1 + … + k r = m a v každé takové třídě je

, k r ) variací.

Jako velmi jednoduché cvičení dokažte platnost vztahů (2.22) a (2.23) přímo, tj. využitím vztahů (2.5), (2.6) a (2.7). ¶

Další velmi důležitou „kombinatorickou identitou“ je známá binomická a multinomická věta.

Věta 2.3.3 (Binomická a multinomická věta) a) Binomická věta - pro libovolná reálná x, y a přirozené m platí

( x + y)

m

m

= ∑ Cmi ⋅ x i ⋅ y m −i .

(2.25)

i =0


strana 86

b) Multinomická věta - pro libovolná reálná x1 , x2 ,… , xr a přirozené m platí

( x1 + x2 + … + xr )

m

=

∑

k1 + k2 +…+ kr = m

P ( k1 , k2 ,… , kr ) ⋅ x1k1 ⋅ x2k2 ⋅… ⋅ xrkr ,

(2.26)

kde součet se provádí přes všechny uspořádané r-tice přirozených čísel ( k1 , k2 ,… , kr ) , jejichž součet je roven m, tj. k1 + … + k r = m . Důkaz. ad a) Roznásobením výrazu ( x + y ) ⋅ ( x + y ) ⋅… ⋅ ( x + y ) dostaneme 2m členů obsahujících m 1. člen

m -tý člen

2. člen

symbolů (z každé závorky právě jeden) a tvořící zřejmě všechny variace m-té třídy s opakováním ze dvou prvků

{ x , y} .

vyskytuje i-krát symbol x a

Dále je evidentní, že počet členů ve kterých se

( m − i ) -krát

symbol y je roven počtu permutací

s opakováním řádu ( i, m − i ) . Po sloučení všech těchto členů dostáváme jako koeficient u xi ⋅ y m −i právě počet permutací s opakováním řádu ( i, m − i ) , tj. P ( i, m − i ) = Cmi . ad b) Zcela analogický k části a). Roznásobením výrazu ( x1 + … + xr ) ⋅ ( x1 + … + xr ) ⋅… ⋅ ( x + … + xr ) dostáváme všechny 1. člen

m -tý člen

2. člen

variace m-té třídy s opakováním z r prvků { x1 ,… , xr } . Po sloučení členů se stejnými mocninami dostáváme jako koeficient u x1k1 ⋅… ⋅ xrkr počet permutací s opakováním řádu

( k1 ,… , kr ) , tj. P ( k1 ,… , kr ) . ¶ Příklad 2.3.1 Určete a) koeficient u x 6 ⋅ y 2 v rozvoji (3x − 5 y ) , 8

b) koeficient y 2 ⋅ u ⋅ v v rozvoji (x + 2 y − 3u + 2v − w) . 4

Řešení. ad a) Z binomické věty je zřejmé, že člen obsahující výraz x 6 ⋅ y 2 má tvar C86 ⋅ (3 x ) ⋅ (− 5 y ) a tedy hledaný koeficient je C86 ⋅ 3 6 ⋅ (− 5) = 510 300 . 6

2

2

ad b) Dle (2.26) má člen obsahující výraz y 2 ⋅ u ⋅ v tvar

P(0, 2,1,1, 0) ⋅ x 0 ⋅ (2 y ) ⋅ (− 3u ) ⋅ (2v ) ⋅ (− w) 2

1

1

0

a tedy jeho koeficient je roven

P(0, 2,1,1, 0) ⋅ (2) ⋅ (− 3) ⋅ (2 ) = −288 . ¶ 2


strana 87

Poznámka 2.3.1 ♦

Binomická a multinomická věta (jak uvidíme později, jde o vytvořující funkce) má velmi široké možnosti využití, např. jako účinný nástroj při řešení celé řady netriviálních úloh. Pro ilustraci uvedeme důkazy vztahů (2.17), (2.19) a (2.24).

ad (2.17) Dosazením x = −1, y = 1 do binomické věty dostáváme m

m

0 = (− 1 + 1) = ∑ C mi ⋅ (− 1) ⋅ 1m −i = ∑ (− 1) ⋅ C mi , m

i

i =0

i

i =0

tj. platnost dokazovaného tvrzení. ad (2.19) Aplikujme binomickou větu na zřejmou identitu

(1 + x )

m+ n

= (1 + x ) ⋅ (1 + x ) . m

n

Platí tak  m i i  n j j i i ⋅ = C x  ∑ C m ⋅ x  ⋅  ∑ C n ⋅ x  ∑ m+ n i =0  i =0   j =0 

m+ n

a porovnáním koeficientů obou stran u x k dostáváme k

C mk + n = ∑ C mi ⋅ C nk −i , k ≤ min (m, n ) , i =0

což bylo třeba dokázati. Stejně snadno lze pouhým dosazením x1 = x 2 = … = x r = 1 do multinomické věty dokázat vztah (2.24). ♦

Binomická věta je speciálním případem následujícího tvrzení, které bývá označované jako Newtonův vzorec: Pro libovolná x, m ∈ R , x < 1 platí

(1 + x )m

= 1+ m ⋅ x +

m ⋅ (m − 1) 2 m ⋅ (m − 1) ⋅ … ⋅ (m − i + 1) i ⋅ x +… + ⋅ x +… 2! i!

(2.27)

(Jako cvičení na matematickou indukci dokažte platnost pro m celé záporné.) Snadno ověříme, že pro m přirozené je koeficient u x i roven právě binomickému koeficientu C mi a jelikož koeficienty všech členů x i , i > m jsou nulové, dostáváme binomickou větu. V případě, kdy exponent je záporné celé číslo, budeme psát − m , kde m ∈ N + a (2.27) má tvar

(1 + x )− m

= 1 − C m1 ⋅ x + C m2 +1 ⋅ x 2 + … + (− 1) ⋅ C mi +i −1 ⋅ x i + … i

(2.28)

Koeficient u x i je tedy roven C −i m , což plně opět odpovídá definici 2.26.


strana 88

V následující části odstavce se budeme věnovat několika kombinatorickým úlohám (úlohy s omezujícími podmínkami a rozklady), které jsou dnes považovány za klasické. Při jejich řešení budou využívány postupy, které mají obecný charakter a jsou významné pro řešení celé řady dalších úloh.

Věta 2.3.4 a) Označme D(m) počet permutací řádu m (bez opakování), ve kterých nezůstává žádný prvek na svém místě. Potom platí 1  1 1 1 m D(m ) = m!⋅1 − + − + … + (− 1) ⋅  . m!  1! 2! 3!

(2.29)

b) Označme Dk (m ) počet permutací řádu m (bez opakování), ve kterých právě k prvků

(0 ≤ k ≤ m ) , zůstává na svém místě. Potom platí Dk (m ) = C mk ⋅ D(m − k ) .

(2.30)

Důkaz.

(

ad a) Označme N ai1 ,… , aik

(

místě a N ai1 ,… , aik

) počet permutací, ve kterých prvky i ,…, i 1

) počet permutací, kdy prvky i ,…, i 1

k

k

zůstávají na svém

na svém místě nezůstávají.

Aplikací principu inkluze a exkluze dostáváme D(m ) = N (a1 ,… , a m ) = N − [N (a1 ) + … + N (a m )] + + [N (a1 , a 2 ) + N (a1 , a3 ) + … N (a m −1 , a m )] + − [N (a1 , a 2 , a3 ) + N (a1 , a 2 , a 4 ) + … + N (a m − 2 , a m −1 , a m )] + + (− 1) ⋅ N (a1 ,… , a m ) . m

Pro jednotlivé počty permutací zřejmě platí: N = m ! … celkový počet permutací řádu m, N ( a1 ) = … = N ( am ) = ( m − 1) ! … počet permutací, ve kterých jeden prvek zůstává na

svém místě a zbývajících m − 1 prvků lze umístit libovolně, N ( a1 , a2 ) = … = N ( am −1 , am ) = ( m − 2 ) ! … počet permutací, ve kterých dva prvky

zůstávají na svém místě a zbývajících m − 2 prvků lze umístit libovolně,


strana 89

N ( a1 ,… , am −1 ) = … = N ( a2 ,… , am ) = 1 ! … počet permutací, ve kterých m − 1 prvků

zůstává na svém místě a zbývající lze umístit libovolně, N ( a1 ,… , am ) = 0 ! … počet permutací, kde zůstávají všechny prvky na svém místě.

Odtud D(m ) = m !−C m1 ⋅ (m − 1)!+C m2 ⋅ (m − 2 )!+ … + (− 1)

m −1

⋅ C mm −1 ⋅ 1!+(− 1) ⋅ C mm ⋅ 0! m

1  1 1 1 m a po snadné úpravě D(m ) = m!⋅1 − + − + … + (− 1) ⋅  . m!  1! 2! 3! ad b) Prvky (v počtu k), které zůstávají na svém místě lze vybrat C mk způsoby a zbývajících

(m − k )

prvků je možné umístit D(m − k ) způsoby (nezůstávají na svém místě).

Aplikací pravidla součinu tak dostáváme dokazovaný vztah. ¶

Pozorný čtenář si jistě uvědomí, že hranatá závorka ve vztahu pro D(m) obsahuje prvních m + 1 členů rozvoje e-1. Vzhledem k tomu, že v závorce uvedená řada konverguje velmi

rychle, lze pro m ≥ 2 použít k výpočtům vztah  m!  D ( m ) = round   ,  e  kde round() je funkce zaokrouhlení.

Definice 2.3.1 Subfaktoriálem budeme nazývat čísla D(m ) , kde m ∈ N , definované vztahem (2.29). ¶

Jak vyplývá z níže uvedené věty, má subfaktoriál D(m) mnohé vlastnosti podobné faktoriálu P(m) (viz vztah (2.4) a (2.22)).

Věta 2.3.5 Platí: a) D ( m ) = ( m − 1) ⋅  D ( m − 1) + D ( m − 2 )  ,

(2.31)

b) D ( m ) = m ⋅ D ( m − 1) + ( −1) .

(2.32)

m

m

c) P(m ) = ∑ C mk ⋅ D(m − k )

(2.33)

k =0


strana 90

Důkaz. ad a) Označme A množinu všech permutací na {a1 ,… , a m } , ve kterých nezůstává žádný prvek na svém místě. Tuto množinu lze rozložit do (m − 1) tříd A2 ,… , Am , kde Ai obsahuje právě všechny permutace z A, které mají na první pozici prvek ai . Vzhledem k tomu, že evidentně všechny třídy mají stejný počet prvků (důsledek „symetrie“), pro libovolné i platí D(m ) = (m − 1) ⋅ Ai . Nyní stačí určit počet permutací, např. v třídě A2 . Třídu A2 rozložíme na dvě podmnožiny A21 , A20 , kde A21 obsahuje všechny permutace z A2 , ve kterých je na druhé pozici a1 a na zbývajících (m − 2 ) pozicích není žádný prvek na svém místě. Odtud A21 = D(m − 2) . Podmnožina A20 obsahuje všechny zbývající permutace z A2 (tj. na první pozici je a2 , na druhé není a1 a na zbývajících pozicích není také žádný prvek na svém místě). Odtud A20 = D(m − 1) a tedy s ohledem

[

na D(m ) = (m − 1) ⋅ A20 + A21

]

dostáváme platnost dokazovaného tvrzení.

ad b) Označme hm = D(m ) − m ⋅ D(m − 1) . Jednoduchou úpravou vztahu (2.31) dostáváme hm = (− 1) ⋅ hm −1 ,

tedy

hm = (− 1)

m−2

⋅ h2 ,

kde

h2 = D(2 ) − 2 ⋅ D(1) = 1 .

Odtud

D(m ) − m ⋅ D(m − 1) = (− 1) a po snadné úpravě dostáváme dokazovaný vztah. m

ad c) Množinu všech permutací řádu m lze rozložit do (m + 1) tříd A0 , A1 ,… , Am , kde Ai obsahuje všechny permutace, ve kterých zůstává právě i prvků na svém místě. Odtud m

P(m ) = ∑ Dk (m ) . Ze vztahu (2.30) pak dostáváme dokazované tvrzení. ¶ k =0

Příklad 2.3.2 V náhodném pořadí propojíte šest různých vstupů se šesti výstupy. Spočtěte průměrný počet správně propojených dvojic vstup-výstup (existuje právě jedno správné propojení všech vstupů s výstupy). Řešení. Zadání příkladu je zřejmě ekvivalentní s úlohou na výpočet průměrného počtu prvků, které v permutacích řádu šest zůstávají na svém místě. Označíme-li X hledaný průměrný počet, zřejmě platí


strana 91

6

X =

∑ k ⋅ Dk (6) k =0

P(6 )

6

=

∑k ⋅C k =0

6−k 6

⋅ D(6 − k )

P(6 )

.

Nyní jednoduchým výpočtem zjistíme D0 (6) = C 60 ⋅ D(6) = 265 ,

D1 (6) = C 61 ⋅ D(5) = 264 ,

D2 (6) = C 62 ⋅ D(4 ) = 135 ,

D3 (6) = C 63 ⋅ D(3) = 40 ,

D4 (6) = C 64 ⋅ D(2 ) = 15 ,

D5 (6) = C 65 ⋅ D(1) = 0 ,

D6 (6 ) = C 66 ⋅ D(0) = 1 ,

P(6 ) = 720 .

Odtud dostáváme X = 1 . ¶

Příklad 2.3.3 Zvolme na kružnici m různých bodů. Určete kolik existuje různých m-úhelníků (nikoliv nutně konvexních), jejichž vrcholy tvoří tyto body. Řešení. Zvolené body očíslujme 1,… , m . Nyní je zřejmé, že každému m-úhelníku odpovídá některá permutace na množině {1,… , m} , kde pořadí čísel v permutaci odpovídá pořadí vrcholů, ve kterém jsou spojovány. Pro ilustraci je na následujícím obrázku znázorněna situace pro m = 4.

1

1

1

2

2

3

3

4

4

(1, 2, 3, 4)

2

(1, 3, 2, 4)

3 4

(1, 3, 4, 2)

Pro řešení je podstatné si dále ujasnit pojem různé m-úhelníky. Z obrázků je patrné, že první čtyřúhelník je popsán nejenom permutací (1, 2, 3, 4 ) , ale i všemi permutacemi (2, 3, 4,1) ,

(3, 4,1, 2), (4,1, 2, 3) a tedy m-úhelníky se nemění při cyklické záměně jejich vrcholů. Všechny P(m ) tříd a každá třída obsahuje všechny permutace, permutace řádů m se tak rozpadají do m

které lze na sebe převést cyklickou záměnou a tudíž reprezentující stejné m-úhelníky. Dále je evidentní,

že

také


permutace

(1, 4, 3, 2), (2,1, 4, 3), (3, 2,1, 4), (4, 3, 2,1)

definují

stejný

strana 92

čtyřúhelník, neboť m-úhelníky se nemění při změně orientace. Tím se počet výše uvedených tříd permutací a tedy i různých m-úhelníků zmenší na polovinu. Nyní je zřejmé, že hledaný počet všech různých m-úhelníků je roven

P(m ) P(m − 1) = . Speciálně v případě m = 4 2⋅m 2

existují tři různé čtyřúhelníky, které jsou znázorněny na obrázku. ¶

Příklad 2.3.4 Uvažujme rovinnou síť znázorněnou na sousedním obrázku a

y

předpokládejme, že pohyb v síti je realizován pouze pomocí dvou typů tahů [x, y ]  → [x + 1, y ] (o jeden úsek na východ) a [x , y ]  → [x, y + 1] (o jeden úsek na sever). Spočtěte: a) Kolik existuje různých cest z bodu [0, 0] do bodu [m, n] .

[0,0]

x

b) Kolik existuje různých cest z bodu [0, 0] do bodu [m, m], které nepřekročí diagonálu (tj. pro souřadnice [x, y ] všech bodů cesty platí x ≥ y ). Řešení. → [x + 1, y ] symbolem 0 a tah typu ad a) Pro potřeby důkazu označme tah [x, y ] 

[x, y ] → [x, y + 1]

symbolem 1. Nyní je zřejmé, že každé cestě (používající pouze

tahy typu 0 a 1) lze jednoznačně přiřadit posloupnost délky m + n , která obsahuje právě m nul a n jedniček. Naopak, každá taková posloupnost m nul a n jedniček definuje jedinou cestu z bodu [0, 0] do bodu [m, n] a tedy počet uvažovaných cest je roven počtu všech permutací s opakováním, které se skládají z m nul a n jedniček, tj. P(m, n ) = C mm+ n . ad b) Snadno zjistíme, že „povoleným“ cestám (nepřekročí diagonálu a vedou z bodu [0, 0] do [m, m]), jednoznačně odpovídají posloupnosti a1 ,… , a 2 m , které obsahují m nul, m jedniček a pro každé k (1 ≤ k ≤ 2m ) je

k

∑a i =1

i

k  ≤   , tj. pro každé k je počet jedniček 2

v řadě a1 ,… , a k nejvýše roven počtu nul (tyto posloupnosti začínají nulou, tj. a1 = 0 a končí jedničkou, tj. a 2 m = 1 ). Nyní určíme počet „povolených“ cest (posloupností) jako rozdíl C 2mm − Z m , kde C 2mm je počet všech cest vedoucích z [0, 0] do [m, m] (viz


strana 93

část a)) a Z m je počet „zakázaných“ cest (překročí diagonálu). Počet Z m snadno určíme následující kombinatorickou úvahou. Označme a1 ,… , a k ,… , a 2 m „zakázanou“ cestu a k index, kde cesta prvně překročí diagonálu. V tomto okamžiku je poprvé počet jedniček v řadě a1 ,… , a k o jedničku větší než počet nul. Číslo k je proto nutně liché, tj. k = 2l + 1 . V této chvíli přidejme na začátek posloupnosti nulu. Tím dostáváme posloupnost 0, a1 ,… , a k ,… , a 2 m , která v úseku 0, a1 ,… , a k obsahuje stejný počet jedniček i nul. Nyní v této části posloupnosti zaměníme nuly a jedničky a dostáváme tak posloupnost 1, a1 ,… , a k , a k +1 ,… , a 2 m , kde ai = 0 , jestliže ai = 1 a ai = 1 v ostatních případech. Tato nová posloupnost začíná jedničkou, obsahuje m + 1 nul, m jedniček a snadno nahlédneme, že každé „zakázané“ cestě lze takto přiřadit posloupnost uvedených vlastností (dvěma různým „zakázaným“ cestám zřejmě odpovídají i různé posloupnosti – zdůvodněte!). Nyní je podstatné si uvědomit, že každá posloupnost b0 , b1 ,… , bk ,… , b2 m uvedených vlastností (tj. začínající jedničkou a obsahující m + 1 nul a m jedniček) jednoznačně definuje „zakázanou“ cestu, kterou lze zkonstruovat následovně. Nechť k je označuje pozici (k sudé), kde se poprvé vyrovná počet jedniček a nul (tato situace musí nastat zdůvodněte!). Nyní v úseku b0 , b1 ,… , bk zaměníme nuly a jedničky a odstraníme úvodní nulu. Získáme tak posloupnost b1 ,… , bk , bk +1 ,… , b2 m , která zřejmě odpovídá zakázané cestě (poprvé překročí diagonálu na pozici k). Tím jsme také dokázali, že počet „zakázaných“ cest je roven počtu všech posloupností, které začínající jedničkou a obsahující m + 1 nul a m jedniček, tj. Z m = P(m − 1, m + 1) = C 2mm−1 a tedy pro počet „povolených“ cest dostáváme C 2mm − C 2mm−1 =

1 ⋅ C 2mm . ¶ m +1

Definice 2.3.2 – Catalanova posloupnost Catalanovou posloupností budeme nazývat posloupnost {C m }m =0 , kde ∞

Cm =

1 ⋅ C 2mm m +1

(2.34)

a její členy budeme nazývat Catalanovými čísly. ¶


strana 94

Catalanova posloupnost patří mezi „prominentní“ kombinatorické posloupnosti a je řešením celé řady úloh. Například počet způsobů jak uzávorkovat součin x0 ⋅ x1 ⋅ … ⋅ x m tak, aby bylo zachováno dané pořadí čísel, je roven C m . Pro m = 3 dostáváme C 3 = 5 následujících možností, jak uzávorkovat součin x0 ⋅ x1 ⋅ x 2 ⋅ x3 :

((x0 ⋅ x1 ) ⋅ x2 ) ⋅ x3 ,

(x0 ⋅ x1 ) ⋅ (x2 ⋅ x3 ) ,

x0 ⋅ ((x1 ⋅ x 2 ) ⋅ x3 ) ,

x0 ⋅ ( x1 ⋅ ( x 2 ⋅ x3 )) .

(x0 ⋅ (x1 ⋅ x 2 )) ⋅ x3 ,

Z hlediska aplikací tvoří významnou třídu úloh tzv. rozklady (množin na podmnožiny určitých vlastností, přirozených čísel na součty určitých vlastností apod.). Lze ukázat, že většinu úloh tohoto typu lze převést na stanovení počtu řešení rovnice x1 + x 2 + … + x k = m

(2.35)

v oboru přirozených čísel (tzv. diofantická rovnice). Odtud motivace pro následující větu.

Věta 2.3.6 a) Rovnice (2.35) má v oboru přirozených čísel C mk −+1k −1 různých řešení. b) Počet všech kladných celočíselných řešení rovnice (2.35), kde k ≤ m , je roven C mk −−11 . c) Rovnice (2.35) má v oboru přirozených čísel Cmk −+1k −1− (a1 +…+ a k ) řešení, která vyhovují podmínkám xi ≥ ai , i = 1,…, k a kde ai jsou přirozená čísla taková, že a1 + … + ak ≤ m . Důkaz. ad a) Každému řešení rovnice (2.35) v oboru přirozených čísel zřejmě odpovídá uspořádaná

( m + k − 1) – rozmístíme

tice skládající se z m jedniček a

(k − 1)

(k − 1)

nul následovně. Nejprve

nul tak, aby mezi nimi vznikly mezery. Tím dostaneme k

„přihrádek“ (viz následující schéma), které reprezentují postupně proměnné x1 ,… , x k . Nyní do i-té přihrádky umístíme takový počet jedniček, který odpovídá hodnotě xi . 1.

( k −1).

2.

… 0 … 0 … x1 x2 x3

… 0 … xk −1 xk

m + k −1

Odtud je zřejmé, že počet hledaných řešení (2.35) je roven počtu všech permutací z m jedniček a (k − 1) nul, tj. P(m, k − 1) = C mk −+1k −1 .


strana 95

ad b) Velmi snadno zjistíme, že počet všech kladných celočíselných řešení (2.35) je roven počtu řešení rovnice x1 + x 2 + … + x k = m − k v oboru přirozených čísel (každá z k přihrádek musí být neprázdná a tedy zbývá rozmístit m − k jedniček). Odtud pro hledaný počet řešení dostáváme vztah P(m − k , k − 1) = C mk −−11 . ad c) Analogicky k části b) je zřejmé, že počet všech řešení (2.35) v oboru přirozených čísel, které vyhovují zadaným podmínkám, je roven počtu řešení rovnice x1 + x 2 + … + x k = m − (a1 + … + a k ) v oboru přirozených čísel, tj. C mk −+1k −1−(a1 +…+ ak ) . ¶

Poznámka 2.3.2 ♦

Počet kolika způsoby lze rozmístit m nerozlišitelných předmětů do k různých přihrádek (některé mohou zůstat i prázdné) je roven C mk −+1k −1 .

♦

Počet kolika způsoby lze rozmístit m nerozlišitelných předmětů do k různých přihrádek

(k ≥ m ) , kde každá přihrádka musí obsahovat alespoň jeden předmět je roven C mk −−11 . ♦

Počet kolika způsoby lze rozmístit m nerozlišitelných předmětů do k různých přihrádek, kde i-tá přihrádka musí obsahovat alespoň ai předmětů (a1 + … + a k ≤ m ) , je roven C mk −+1k −1−(a1 +…+ ak ) .

Příklad 2.3.5 Kolika způsoby lze mezi čtyři osoby rozdělit 10 pomerančů, 5 banánů a 15 hrušek, jestliže: a) neklademe žádná omezení, b) každá osoba musí dostat alespoň jeden kus některého ovoce, c) každá osoba musí dostat alespoň dva kusy pomerančů, jeden banán a tři hrušky. Řešení. Aplikací poznámky 2.3.2 na jednotlivé případy dostáváme: ad a)

k = 4, m = 30 , tedy hledaný počet je roven C 333 = 5 456 .

ad b)

3 = 3 654 . k = 4, m = 30 , tedy hledaný počet je roven C 29

ad c)

k = 4, m = 30, a1 = a 2 = a3 = a 4 = 6 , tedy hledaný počet je roven C153 = 455 .

¶


strana 96

2.4

Rekurentní vztahy a vytvořující funkce

Celou řadu velmi důležitých kombinatorických úloh nelze rozumně vyřešit pouze využitím pravidel a metod z předchozích odstavců. Jako příklad lze uvést úlohu objevující se při řešení různých problémů a otázek v mnoha oborech a kterou lze formulovat následovně: Kolik existuje bitových řetězců (tj. obsahují pouze nuly a jedničky) délky m, ve kterých se nevyskytuje dvě a více po sobě jdoucích nul. Označíme-li a m hledaný počet řetězců délky m, velmi snadno zjistíme, že takové řetězce končí buď jedničkou (jejich počet je zřejmě a m −1 ), nebo řetězcem 10 (jejich počet je a m − 2 ) a tedy platí a m = a m −1 + a m − 2 , kde a1 = 2 , a 2 = 3 . Tento vztah, který vyjadřuje řešení úlohy o velikosti m pomocí řešení stejné úlohy menšího rozsahu (v našem případě m − 1 a m − 2 ), se nazývá rekurentní vztah. Hodnoty a1 = 2 , a 2 = 3 se nazývají počáteční podmínky a jednoznačně určují řešení.

Definice 2.4.1 Rekurentním vztahem posloupnosti {a m }m =0 nazýváme rovnici ∞

a m = f (a m −1 ,… , a m − k ) ,

(2.36)

která pro každé m, kde m ≥ m0 , vyjadřuje m-tý člen posloupnosti pomocí k bezprostředně ho předcházejících členů. ¶

Poznámka 2.4.1 Posloupnost {a m }m =0 z definice 2.4.1 nazýváme řešením rekurentního vztahu (2.36). Důležité ∞

ovšem je si uvědomit, že v obecném případě má rekurentní vztah nekonečně mnoho řešení, tj. existuje nekonečně mnoho různých posloupností, pro které platí (2.36). V případě, kdy řešením rekurentního vztahu je i nulová posloupnost, mluvíme o homogenním rekurentním vztahu a v opačném případě o nehomogenním rekurentním vztahu.

Příklad 2.4.1 Rozhodněte, zda následující posloupnosti {a m }m =0 jsou řešením rekurentního vztahu ∞

a m = 3a m −1 − 2a m − 2 .


(∗)

strana 97

a) a m = 5 ⋅ 2 m , m ∈ N ,

b) a m = 4m , m ∈ N , c) a m = K 1 + K 2 ⋅ 2 m , m ∈ N a K 1 , K 2 jsou libovolné reálné konstanty. Řešení. ad a) V tomto případě a m −1 = 5 ⋅ 2 m −1 , a m − 2 = 5 ⋅ 2 m − 2 a tedy po dosazením do (∗) získáme

[

]

[

]

vztah 5 ⋅ 2 m = 3 ⋅ 5 ⋅ 2 m −1 − 2 ⋅ 5 ⋅ 2 m − 2 , který je platný pro každé m ≥ 2 . Odtud plyne, že posloupnost a m = 5 ⋅ 2 m , m ∈ N je řešením (∗). ad b) Zřejmě a m −1 = 4(m − 1) , a m − 2 = 4(m − 2) . Dosazením do (∗) dostáváme vztah 4m = 3[4(m − 1)] − 2[4(m − 2 )] , který je platný pouze pro m = −1 a tedy posloupnost

a m = 4m , m ∈ N není řešením daného rekurentního vztahu. ad c) Zřejmě a m −1 = K 1 + K 2 ⋅ 2 m −1 , a m − 2 = K 1 + K 2 ⋅ 2 m − 2 . Analogickým postupem (tj. dosazením do rekurentního vztahu) snadno zjistíme, že vztah

[

]

[

K 1 + K 2 ⋅ 2 m = 3 ⋅ K 1 + K 2 ⋅ 2 m −1 − 2 ⋅ K 1 + K 2 ⋅ 2 m −2

]

je platný pro m ≥ 2 a tedy posloupnost a m = K 1 + K 2 ⋅ 2 m , m ∈ N je řešením (∗). Jak uvidíme později, jde v tomto případě o tzv. obecné řešení, které má tu vlastnost, že vhodnou volbou konstant K 1 , K 2 lze získat libovolné řešení (∗). ¶

V další části odstavce se budeme zabývat řešením homogenních lineárních rekurentních vztahů s konstantními koeficienty.

Definice 2.4.2 Homogenním lineárním rekurentním vztahem řádu k nazýváme rovnici a m = C k −1 ⋅ a m −1 + … + C 0 ⋅ a m − k , m ≥ k ,

(2.37)

kde C i , 0 ≤ i ≤ k − 1 jsou reálná čísla, C 0 ≠ 0 a rovnici x k = C k −1 ⋅ x k −1 + … + C1 ⋅ x + C 0

(2.38)

nazýváme jeho charakteristickou rovnicí. ¶

Je evidentní, že vztah (2.37) má nekonečně mnoho řešení, neboť členům a 0 , a1 ,… , a k −1 lze přiřadit libovolné hodnoty (ostatní členy jsou pak určeny jednoznačně). Proto je každé řešení Diskrétní matematika II

strana 98

jednoznačně určeno k počátečními podmínkami (nejčastěji hodnotami prvních k členů posloupnosti a 0 , a1 ,… , a k −1 ). Obecným řešením vztahu (2.37) pak nazýváme výraz obsahující k konstant (k je tzv. řád), jejichž vhodnou volbou lze vyjádřit libovolné řešení.

Postup řešení homogenních lineárních rekurentních vztahů (2.37) lze popsat následovně: 1. Sestavte

charakteristickou

rovnici

(2.38)

a

vypočtěte

její

kořeny,

nazývané

charakteristické kořeny. 2. Označme λ 1 ,… , λ r všechny různé charakteristické kořeny a α 1 ,… , α r jejich násobnosti

(α1 + … + α r

= k ) , potom obecné řešení rekurentního vztahu (2.37) má tvar

(

)

a m = K 1,0 + K 1,1 ⋅ m + … + K 1,α1 −1 ⋅ m α1 −1 ⋅ λm1 +

(

)

+ K 2,0 + K 2,1 ⋅ m + … + K 2,α 2 −1 ⋅ m α 2 −1 ⋅ λm2 +

(

,

(2.39)

)

+ K r ,0 + K r ,1 ⋅ m + … + K r ,α r −1 ⋅ m α r −1 ⋅ λmr

kde m ∈ N a K i , j (1 ≤ i ≤ r , 0 ≤ j ≤ α i − 1) jsou libovolné reálné konstanty. (Důkaz viz Brualdi.)

Poznámka 2.4.2 ♦

Z (2.39) je patrné, že obecné řešení (2.37) se skládá z r členů, které mají tvar

(K

i ,0

)

+ K i ,1 ⋅ m + … + K i , α i −1 ⋅ m α i −1 ⋅ λmi , 1 ≤ i ≤ r .

(2.40)

Tyto členy zastupují jednotlivé kořeny charakteristické rovnice včetně jejich násobnosti a jsou také řešením původního rekurentního vztahu (Dokažte!). ♦

V případě, kdy charakteristická rovnice (2.38) má pouze jednoduché kořeny (tj. r = k , α 1 = … = α k = 1 ), má obecné řešení rekurentního vztahu (2.37) tvar a m = K 1 ⋅ λm1 + … + K k ⋅ λmk ,

(2.41)

kde λ i , 1 ≤ i ≤ k jsou kořeny charakteristické rovnice a K i jsou libovolné reálné konstanty. ♦

Vzhledem k tomu, že koeficienty charakteristického polynomu jsou reálná čísla, jsou jeho kořeny reálná čísla nebo dvojice komplexně sdružených čísel a tedy jim odpovídající členy (2.40) jsou komplexní, které však lze pomocí Moivreovy věty převést na členy reálné. Je-li totiž λ = a + b ⋅ i, λ = a − b ⋅ i dvojice komplexně sdružených kořenů, potom


strana 99

(a

2

+ b2

)

m

⋅ cos(m ⋅ ϕ),

(a

2

+ b2

)

m

b ⋅ sin (m ⋅ ϕ) , kde ϕ = arctan  , je dvojice lineárně a

nezávislých řešení uvažovaného rekurentního vztahu.

Příklad 2.4.2 (Leonardo Pisánský, zvaný Fibonacci, 1175-1250) Na prázdném ostrově byl vysazen pár mladých králíků, který za dva měsíce od svého vysazení začne pravidelně každý měsíc přivádět na svět nový pár králíků. Každý nově narozený pár králíků začne za dva měsíce od svého narození také pravidelně každý měsíc přivádět na svět nový pár králíků. Spočtěte, kolik párů králíků bude na ostrově za rok od vysazení prvního páru. Řešení. Označme Fm , m ∈ N velikost králičí populace (tj. počet párů) na konci m-tého měsíce od vysazení prvního páru na ostrově. Hledáme tak hodnotu F12 . Dále si uvědomme, že populace v m-tém měsíci se skládá z populace přecházejícího měsíce (tj. m − 1 ) a nových přírůstků, jejichž počet odpovídá velikosti populace v měsíci m − 2 (pouze tyto páry přivedou na svět nový pár). Pro Fm , m ≥ 2 tak dostáváme rekurentní vztah Fm = Fm −1 + Fm − 2 ,

(2.42)

se zřejmými počátečními podmínkami F1 = 1, F2 = 1 (velikost populace v prvním a druhém měsíci). Při řešení (2.42) postupujeme dle popsaného návodu. Charakteristická rovnice má tvar x 2 = x + 1 a její kořeny (charakteristické) jsou λ 1 =

1+ 5 1− 5 , λ2 = . Z (2.41) tak 2 2

dostáváme obecné řešení ve tvaru m

m

1+ 5  1− 5  ~  + K2 ⋅  Fm = K 1 ⋅    2  , 2     kde K 1 , K 2 jsou konstanty. Hodnoty těchto konstant určíme z počátečních podmínek F1 = 1 a F2 = 1 , které vedou k soustavě 1

1

2

2

1+ 5  1− 5   + K2 ⋅  1 = K 1 ⋅    2 ,  2    1+ 5  1− 5   + K2 ⋅  1 = K 1 ⋅    2  .  2   


strana 100

Odtud K 1 =

1 5

, K2 = −

1 5

a

 1 + 5  m  1 − 5  m     − Fm = ⋅   2  . 5  2      1

(2.43)

Pro hledanou velikost populace tak dostáváme F12 = 144 . ¶

Poznámka 2.4.3 Posloupnost

{Fm }∞m=0

definovaná rekurentním vztahem (2.42) s počátečními podmínkami

F0 = 0, F1 = 1 se nazývá Fibonacciho posloupnost a patří mezi nejvýznamnější číselné posloupnosti. Její m-tý člen je dán vztahem (2.43), který obsahuje iracionální čísla, přesto je zřejmě pro každé m ∈ N hodnota Fm přirozeným číslem. Hodnoty Fm , 0 ≤ m ≤ 44 lze nalézt v tabulce, která je obsažena v příloze.

Příklad 2.4.3 Nalezněte řešení rekurentního vztahu a m = 5a m −1 − 3a m − 2 − 9a m −3 , které vyhovuje počátečním podmínkám a 0 = 0, a1 = 1, a 2 = −10 . Řešení. Charakteristická rovnice má tvar x 3 = 5 x 2 − 3x − 9 a její kořeny jsou λ 1 = 3 násobnosti α 1 = 2 a λ 2 = −1 násobnosti α 2 = 1 . Odkud dostáváme obecné řešení ve tvaru m a~m = (K 1 + K 2 ⋅ m ) ⋅ 3 m + K 3 ⋅ (− 1) , m ∈ N .

Konstanty, které definují řešení vyhovující zadaným počátečním podmínkám nalezneme jako řešení soustavy 0 = (K 1 + K 2 ⋅ 0 ) ⋅ 30 + K 3 ⋅ (− 1) , 0

1 = (K 1 + K 2 ⋅ 1) ⋅ 31 + K 3 ⋅ (− 1) , 1

− 10 = (K 1 + K 2 ⋅ 2 ) ⋅ 3 2 + K 3 ⋅ (− 1) . 2

Odtud K 1 = 1, K 2 = −1, K 3 = −1 a jako hledané řešení dostáváme a m = (1 − m ) ⋅ 3 m + (− 1)


m +1

, m∈ N . ¶

strana 101

2.5

Základní kombinatorické posloupnosti

Při řešení celé řady kombinatorických úloh dostáváme číselné posloupnosti, jejichž členy vyjadřují výsledky v závislosti na rozsahu úlohy. Mezi nejznámější patří např. kombinační čísla, Fibonacciho čísla, Lucasova čísla, Catalanova čísla atd. Stručný přehled nejvýznamnějších posloupností a jejich charakteristik je obsahem tohoto odstavce.

Kombinační čísla Rekurentní vztah Kombinační čísla lze definovat rekurentním vztahem

Cmk = Cmk −1 + Cmk −−11 , 0 ≤ k ≤ m , s počátečními podmínkami C00 = 1 , C mk = 0 , pro 0 ≤ m < k a Cmk = 0 , pro k < 0 . Vytvořující funkce

f ( x ) = (1 + x ) , m ∈ N . m

Explicitní vyjádření viz definice 2.2.6 Základní vlastnosti

viz věty 2.2.5 a 2.3.1

Fibonacciho čísla

Rekurentní vztah Fibonacciho posloupnost { Fm }m =0 lze definovat rekurentním vztahem ∞

Fm = Fm −1 + Fm − 2 ,

s počátečními podmínkami F0 = 0 , F1 = 1 . x . 1− x − x2

Vytvořující funkce

f (x ) =

Explicitní vyjádření

m m 1− 5   1  1 + 5     −  Fm =  2   , m = 0,1,… 5  2     


strana 102

Základní vlastnosti ♦

Fm − 2 + Fm +1 , m = 2, 3,… 2

Fm = m

♦

∑F i =0

= Fm + 2 − 1, m = 0,1,…

i

m

♦

∑ (− 1)

i

i =0 m

♦

∑F i =0

2

i

⋅ Fi = (− 1) Fm −1 − 1, m = 1, 2,… m

= Fm ⋅ Fm +1 , m = 0,1,…

Lucasova čísla

Rekurentní vztah Lucasovu posloupnost { Lm }m =0 lze definovanou rekurentním vztahem ∞

Lm = Lm −1 + Lm − 2 , s počátečními podmínkami L0 = 2 , L1 = 1 . Vytvořující funkce f ( x ) =

2− x . 1− x − x2 m


m

1+ 5  1− 5   +  Lm =    2  , m = 0,1,… 2    

Základní vlastnosti ♦

Lm = Fm −1 + Fm +1 , m = 1, 2, …

♦

Fm =

♦

∑L

m

i =0 m

♦

i

∑L i =0

2 i

Lm −1 + Lm +1 , m = 1, 2,… 5

= Lm + 2 − 1, m = 0,1,… = Lm ⋅ Lm +1 + 2 , m = 0,1,…


strana 103

Catalanova čísla

Rekurentní vztah Catalanovu posloupnost {C m }m =0 lze definovat nelineárním rekurentním vztahem ∞

C m = C 0 ⋅ C m −1 + C1 ⋅ C m − 2 + … + C m −1 ⋅ C 0 , m ≥ 1 , s počáteční podmínkou C 0 = 1 .

Vytvořující funkce

f (x ) =

Explicitní vyjádření C m =

Základní vlastnosti

1 − 1 − 4x . 2x

1 ⋅ C 2mm , m = 0,1,… m +1

C m +1 =

2(2m + 1) C m , m = 0,1,… m+2

Harmonická čísla

Rekurentní vztah Harmonickou posloupnost {H m }m =0 lze definovat rekurentním vztahem ∞

H m = H m −1 +

1 , m = 1, 2,… , m

s počáteční podmínkou H 0 = 0 . Vytvořující funkce f ( x ) =


1 1 . ⋅ ln 1− x 1− x

m 1 H m = ∑ , m ≥ 1. i =1 i

Základní vlastnosti m

♦

∑ H = (m + 1) ⋅ (H i =1

i

m

♦

∑i ⋅ H i =1

i


m +1

− 1), m = 1, 2,…

1  = C m2 +1 ⋅  H m +1 −  , m = 1, 2,… 2 

strana 104

Přílohy


strana 105

Použité značení

Logika

∧

… logická spojka „a“ (konjunkce),

∨

… logická spojka „nebo“ (disjunkce),

→

… implikace (jestliže),

↔

… ekvivalence (právě když).

Množiny N

… množina přirozených čísel (včetně nuly),

N+

… množina kladných přirozených čísel,

Z

… množina celých čísel,

Q

… množina racionálních čísel,

R

… množina reálných čísel,

C

… množina komplexních čísel,

{a1 ,… , a n }

… množina skládající se z prvků a1 ,… , a n ,

{a V ( a )}

… množina prvků s vlastností V,

A∩ B

… průnik množin A, B,

A∪ B

… sjednocení množin A, B,

A− B

… rozdíl množin A – B,

A× B

… kartézský součin množin A, B,

P ( A)

… potenční množina,

A

… počet prvků (mohutnost, kardinalita) množiny A.

Dělitelnost a |b

… a dělí b (tj. beze zbytku),

a /| b

… a nedělí b,

NSD(a, b )

… největší společný dělitel čísel a, b,

NSN (a, b )

… nejmenší společný násobek čísel a, b,

a mod b

… zbytek při dělení a číslem b,


strana 106

a ≡ b ( mod m )

… a je kongruentní s b modulo m,

a ≡/ b ( mod m )

… a není kongruentní s b modulo m,

( an an−1 … a0 )b

… vyjádření čísla v soustavě o základu b.

Funkce f (a)

… hodnota funkce f v bodě a,

{an }n=0

… číselná posloupnost,

 x 

… horní celá část čísla x,

 x 

… dolní celá část čísla x,

{x}

… lomená část x,

n!

… m faktoriál,

ln x

… přirozený logaritmus čísla x,

µ(a )

… hodnota Möbiovy funkce v bodě a,

ϕ(a )

… hodnota Eulerovy funkce v bodě a.

∞

Kombinatorika C mk

… kombinace k-té třídy z m prvků (bez opakování),

C mk

… kombinace k-té třídy z m prvků s opakováním,

Amk

… variace k-té třídy z m prvků (bez opakování),

Amk

… variace k-té třídy z m prvků s opakováním,

P(m )

… permutace m-té třídy (bez opakování),

P(m1 ,… , mk )

… permutace m-té třídy s opakováním (m = m1 + … + mk ) ,

Cm

… Catalanovo číslo,

Fm

… Fibonacciho číslo,

Lm

… Lucasovo číslo,

Hm

… harmonické číslo.


strana 107

Tabulka všech prvočísel (prvních 840)

2 31 73 127 179 233 283 353 419 467 547 607 661 739 811 877 947 1019 1087 1153 1229 1297 1381 1453 1523 1597 1663 1741 1823 1901 1993 2063 2131 2221 2293 2371 2437 2539 2621 2689 2749

3 37 79 131 181 239 293 359 421 479 557 613 673 743 821 881 953 1021 1091 1163 1231 1301 1399 1459 1531 1601 1667 1747 1831 1907 1997 2069 2137 2237 2297 2377 2441 2543 2633 2693 2753


5 41 83 137 191 241 307 367 431 487 563 617 677 751 823 883 967 1031 1093 1171 1237 1303 1409 1471 1543 1607 1669 1753 1847 1913 1999 2081 2141 2239 2309 2381 2447 2549 2647 2699 2767

7 43 89 139 193 251 311 373 433 491 569 619 683 757 827 887 971 1033 1097 1181 1249 1307 1423 1481 1549 1609 1693 1759 1861 1931 2003 2083 2143 2243 2311 2383 2459 2551 2657 2707 2777

11 47 97 149 197 257 313 379 439 499 571 631 691 761 829 907 977 1039 1103 1187 1259 1319 1427 1483 1553 1613 1697 1777 1867 1933 2011 2087 2153 2251 2333 2389 2467 2557 2659 2711 2789

13 53 101 151 199 263 317 383 443 503 577 641 701 769 839 911 983 1049 1109 1193 1277 1321 1429 1487 1559 1619 1699 1783 1871 1949 2017 2089 2161 2267 2339 2393 2473 2579 2663 2713 2791

17 59 103 157 211 269 331 389 449 509 587 643 709 773 853 919 991 1051 1117 1201 1279 1327 1433 1489 1567 1621 1709 1787 1873 1951 2027 2099 2179 2269 2341 2399 2477 2591 2671 2719 2797

19 61 107 163 223 271 337 397 457 521 593 647 719 787 857 929 997 1061 1123 1213 1283 1361 1439 1493 1571 1627 1721 1789 1877 1973 2029 2111 2203 2273 2347 2411 2503 2593 2677 2729 2801

23 67 109 167 227 277 347 401 461 523 599 653 727 797 859 937 1009 1063 1129 1217 1289 1367 1447 1499 1579 1637 1723 1801 1879 1979 2039 2113 2207 2281 2351 2417 2521 2609 2683 2731 2803

29 71 113 173 229 281 349 409 463 541 601 659 733 809 863 941 1013 1069 1151 1223 1291 1373 1451 1511 1583 1657 1733 1811 1889 1987 2053 2129 2213 2287 2357 2423 2531 2617 2687 2741 2819

strana 108

2833 2909 3001 3083 3187 3259 3343 3433 3517 3581 3659 3733 3823 3911 4001 4073 4153 4241 4327 4421 4507 4591 4663 4759 4861 4943 5009 5099 5189 5281 5393 5449 5527 5641 5701 5801 5861 5953 6067 6143 6229 6311 6373

2837 2917 3011 3089 3191 3271 3347 3449 3527 3583 3671 3739 3833 3917 4003 4079 4157 4243 4337 4423 4513 4597 4673 4783 4871 4951 5011 5101 5197 5297 5399 5471 5531 5647 5711 5807 5867 5981 6073 6151 6247 6317 6379


2843 2927 3019 3109 3203 3299 3359 3457 3529 3593 3673 3761 3847 3919 4007 4091 4159 4253 4339 4441 4517 4603 4679 4787 4877 4957 5021 5107 5209 5303 5407 5477 5557 5651 5717 5813 5869 5987 6079 6163 6257 6323 6389

2851 2939 3023 3119 3209 3301 3361 3461 3533 3607 3677 3767 3851 3923 4013 4093 4177 4259 4349 4447 4519 4621 4691 4789 4889 4967 5023 5113 5227 5309 5413 5479 5563 5653 5737 5821 5879 6007 6089 6173 6263 6329 6397

2857 2953 3037 3121 3217 3307 3371 3463 3539 3613 3691 3769 3853 3929 4019 4099 4201 4261 4357 4451 4523 4637 4703 4793 4903 4969 5039 5119 5231 5323 5417 5483 5569 5657 5741 5827 5881 6011 6091 6197 6269 6337 6421

2861 2957 3041 3137 3221 3313 3373 3467 3541 3617 3697 3779 3863 3931 4021 4111 4211 4271 4363 4457 4547 4639 4721 4799 4909 4973 5051 5147 5233 5333 5419 5501 5573 5659 5743 5839 5897 6029 6101 6199 6271 6343 6427

2879 2963 3049 3163 3229 3319 3389 3469 3547 3623 3701 3793 3877 3943 4027 4127 4217 4273 4373 4463 4549 4643 4723 4801 4919 4987 5059 5153 5237 5347 5431 5503 5581 5669 5749 5843 5903 6037 6113 6203 6277 6353 6449

2887 2969 3061 3167 3251 3323 3391 3491 3557 3631 3709 3797 3881 3947 4049 4129 4219 4283 4391 4481 4561 4649 4729 4813 4931 4993 5077 5167 5261 5351 5437 5507 5591 5683 5779 5849 5923 6043 6121 6211 6287 6359 6451

2897 2971 3067 3169 3253 3329 3407 3499 3559 3637 3719 3803 3889 3967 4051 4133 4229 4289 4397 4483 4567 4651 4733 4817 4933 4999 5081 5171 5273 5381 5441 5519 5623 5689 5783 5851 5927 6047 6131 6217 6299 6361 6469

2903 2999 3079 3181 3257 3331 3413 3511 3571 3643 3727 3821 3907 3989 4057 4139 4231 4297 4409 4493 4583 4657 4751 4831 4937 5003 5087 5179 5279 5387 5443 5521 5639 5693 5791 5857 5939 6053 6133 6221 6301 6367 6473

strana 109

Tabulka hodnot Eulerovy funkce

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

1 1 10 12 30 40 32 60 70 54 72 100 72 110 130 92 150 132 108 180 190 132 210 192 120 240 250 168 270 280 192 252 310 212 330 300 216 342 312 252 352


2 1 4 10 16 12 24 30 24 40 44 32 48 60 40 70 72 54 84 72 64 100 104 72 112 110 72 130 128 92 144 150 96 132 164 108 160 180 120 190 168

3 2 12 22 20 42 52 36 72 82 60 102 112 80 108 120 96 162 172 120 192 168 140 222 232 162 220 262 144 282 292 200 312 288 216 294 352 220 372 382 260

4 2 6 8 16 20 18 32 36 24 46 48 36 60 66 48 60 80 56 88 96 64 106 96 72 120 126 80 136 140 84 144 156 108 166 168 116 144 160 128 196

5 4 8 20 24 24 40 48 40 64 72 48 88 100 72 112 120 80 120 144 96 160 168 120 184 168 128 208 200 144 232 240 144 240 264 176 280 288 200 240 312

6 2 8 12 12 22 24 20 36 42 32 52 56 36 64 72 48 82 80 60 84 102 72 112 116 80 128 108 88 120 144 96 156 162 96 172 176 120 184 192 120

7 6 16 18 36 46 36 66 60 56 96 106 72 126 136 84 156 166 116 160 196 132 180 226 156 216 256 176 276 240 180 306 316 216 336 346 192 366 336 252 396

8 4 6 12 18 16 28 32 24 40 42 36 58 64 44 72 78 48 88 92 60 96 108 72 96 120 84 132 138 96 148 120 104 160 156 112 178 176 108 192 198

9 6 18 28 24 42 58 44 78 88 60 108 96 84 138 148 104 156 178 108 198 180 144 228 238 164 216 268 180 272 264 204 280 276 224 348 358 240 378 388 216

10 4 8 8 16 20 16 24 32 24 40 40 32 48 48 40 64 64 48 72 80 48 80 88 64 100 96 72 96 112 80 120 128 80 128 120 96 144 144 96 160

strana 110

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

400 272 420 430 252 400 460 312 432 490 332 432 520 348 540 504 320 570 492 392 600 552 396 630 640 360 660 600 452 690 700 468 612 672 432 750 760 512 700 672 528 810 820


132 204 210 144 192 224 120 232 240 160 250 256 168 216 270 176 280 240 192 288 252 192 310 312 212 324 330 192 300 344 216 352 342 240 312 368 252 384 352 240 400 336 272

360 348 276 432 442 300 462 420 264 448 502 324 522 480 360 468 562 380 520 592 396 612 528 420 642 652 384 672 682 360 648 660 480 732 742 500 648 772 504 720 720 540 822

200 132 208 180 144 226 224 156 220 216 144 256 260 176 256 276 184 240 288 180 300 306 192 316 264 216 328 336 216 346 320 192 360 366 240 336 380 252 336 396 264 360 408

216 328 320 224 352 288 240 360 384 240 400 408 240 424 432 288 448 440 288 384 440 320 500 504 336 520 432 360 544 552 368 480 560 336 592 600 384 600 624 416 528 648 400

168 192 140 216 222 144 232 192 162 240 220 168 262 264 144 276 282 192 292 296 200 240 312 208 288 320 216 312 294 224 352 356 220 352 372 216 382 384 260 396 360 256 348

360 276 360 396 296 456 466 312 486 420 312 460 480 356 546 556 324 576 586 396 606 616 360 504 646 432 616 676 456 640 600 476 726 660 492 756 696 432 786 796 536 756 826

128 180 212 144 192 228 144 238 240 164 252 216 160 268 272 180 280 272 168 264 288 204 312 280 216 276 332 224 336 348 232 358 288 240 320 378 256 388 392 216 400 408 264

408 418 240 438 448 288 396 478 324 498 508 344 506 420 360 504 568 384 540 598 336 618 576 420 580 658 444 576 624 464 708 718 486 738 636 440 768 720 524 736 808 432 828

160 96 168 160 120 176 184 128 168 200 128 192 208 144 200 192 144 224 232 160 240 240 144 256 240 160 264 256 176 240 280 192 288 288 200 288 240 192 312 320 216 320 328

strana 111

Tabulka hodnot Möbiovy funkce

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

1 1 -1 1 -1 -1 1 -1 -1 0 1 -1 1 0 -1 1 -1 1 0 -1 -1 1 -1 1 -1 -1 -1 0 -1 -1 1 1 -1 1 -1 1 0 0 1 1 1


2 -1 0 1 0 -1 0 1 0 1 0 -1 0 1 0 1 0 0 0 -1 0 1 0 -1 0 0 0 1 0 -1 0 1 0 -1 0 0 0 1 0 1 0

3 -1 -1 -1 1 -1 -1 0 -1 -1 1 -1 -1 1 1 1 0 -1 -1 1 -1 1 1 -1 -1 0 1 -1 -1 -1 -1 1 -1 1 0 0 -1 0 -1 -1 1

4 0 1 0 1 0 0 0 1 0 1 0 -1 0 1 0 -1 0 -1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 -1 0 -1 0 1

5 -1 1 0 1 0 1 1 0 1 1 -1 1 0 0 1 1 -1 0 1 -1 1 1 0 1 0 -1 1 0 -1 1 1 0 0 1 -1 1 1 0 -1 1

6 1 0 1 0 1 0 -1 0 1 0 1 0 0 0 1 0 1 0 -1 0 1 0 1 0 -1 0 -1 0 -1 0 0 0 1 0 1 0 -1 0 1 0

7 -1 -1 0 -1 -1 1 -1 1 1 -1 -1 0 -1 -1 0 -1 -1 1 1 -1 0 1 -1 1 1 -1 1 -1 1 0 -1 -1 1 -1 -1 -1 -1 1 0 -1

8 0 0 0 1 0 1 0 -1 0 0 0 1 0 -1 0 1 0 1 0 0 0 1 0 -1 0 -1 0 1 0 1 0 -1 0 0 0 1 0 0 0 1

9 0 -1 -1 1 0 -1 1 -1 -1 0 -1 1 1 -1 -1 1 0 -1 0 -1 1 1 -1 -1 1 1 -1 0 0 1 1 1 1 1 -1 -1 0 -1 -1 -1

10 1 0 -1 0 0 0 -1 0 0 0 -1 0 -1 0 0 0 -1 0 -1 0 1 0 -1 0 0 0 0 0 -1 0 -1 0 1 0 0 0 -1 0 1 0

strana 112

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

-1 1 -1 -1 0 1 -1 1 1 -1 1 1 -1 0 -1 1 -1 -1 1 1 -1 1 0 -1 -1 -1 -1 1 1 -1 -1 0 1 1 -1 -1 -1 1 1 1 0 -1 -1


-1 0 1 0 -1 0 1 0 1 0 1 0 0 0 1 0 1 0 -1 0 -1 0 1 0 -1 0 1 0 -1 0 0 0 0 0 -1 0 -1 0 -1 0 1 0 -1

1 1 0 -1 -1 1 -1 1 -1 1 -1 0 -1 1 1 1 -1 1 1 -1 0 -1 1 1 -1 -1 -1 -1 -1 0 1 1 1 -1 -1 1 1 -1 0 1 1 1 -1

0 0 0 -1 0 1 0 -1 0 -1 0 1 0 -1 0 1 0 -1 0 0 0 1 0 1 0 -1 0 1 0 1 0 1 0 1 0 -1 0 0 0 1 0 -1 0

0 1 0 -1 1 -1 -1 0 1 0 1 1 0 1 1 -1 1 0 0 -1 0 -1 0 1 -1 1 -1 0 1 1 -1 -1 0 0 1 1 0 0 1 -1 -1 1 0

-1 0 -1 0 1 0 1 0 0 0 -1 0 1 0 1 0 1 0 1 0 -1 0 1 0 -1 0 0 0 0 0 1 0 0 0 1 0 1 0 -1 0 -1 0 -1

1 1 1 1 1 -1 -1 0 -1 1 0 1 1 1 -1 -1 0 -1 -1 1 -1 -1 -1 0 -1 0 1 -1 1 1 1 1 -1 1 0 -1 1 -1 -1 -1 1 1 -1

0 -1 0 -1 0 1 0 1 0 -1 0 -1 0 1 0 0 0 0 0 -1 0 -1 0 -1 0 -1 0 -1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0

-1 -1 -1 -1 -1 0 1 -1 1 -1 -1 1 0 0 0 1 -1 1 1 -1 -1 -1 1 0 1 -1 1 1 1 1 -1 -1 0 -1 1 -1 -1 1 1 1 -1 0 -1

-1 0 -1 0 0 0 -1 0 0 0 1 0 -1 0 0 0 1 0 -1 0 -1 0 0 0 0 0 -1 0 1 0 -1 0 -1 0 0 0 1 0 -1 0 0 0 -1

strana 113

Tabulka hodnot subfaktoriálů D(m )

m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 1 2 9 44 265 1 854 14 833 133 496 1 334 961 14 684 570 176 214 841 2 290 792 932 32 071 101 049 481 066 515 734 7 697 064 251 745 130 850 092 279 664 2 355 301 661 033 953 44 750 731 559 645 106 895 014 631 192 902 121

Tabulka hodnot Fibonacciho čísel

m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Diskrétní matematika II

Fm

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

m 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Fm 610 987 1 597 2 584 4 181 6 765 10 946 17 711 28 657 46 368 75 025 121 393 196 418 317 811 514 229

m 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

Fm 832 040 1 346 269 2 178 309 3 524 578 5 702 887 9 227 465 14 930 352 24 157 817 39 088 169 63 245 986 102 334 155 165 580 141 267 914 296 433 494 437 701 408 733 strana 114

Literatura

R. A.Brualdi: Introductory Combintorics. Prentice-Hall, 1997. R. P. Grimaldi: Discrete and Combinatorial Mathematics. Addison-Wesley, 1998. D. E. Knuth: The Art of Computer Programming. Volume 1: Fundamental Algorithms, Addison-Wesley, 1997. D. E. Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1997. D. E. Knuth: The Art of Computer Programming. Volume 3: Sorting and Searching, Addison-Wesley, 1998. L. Lovász: Combinatorial Problems and Exercises. North-Holland, 1979. I. Pohl, A. Shaw: The Nature of Computation: An Introduction to Computer Science. Computer Science Press, 1981. K. H. Rosen: Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000. K. H. Rosen: Elementary Number Theory and Its Applications. Addison-Wesley, 1999. K. H. Rosen: Discrete Mathematics and Its Applications. McGraw-Hill, 1999. N. R. Scott: Computer Number Systems and Arithmetic. Prentice Hall, 1985. A. Tucker: Applied Combinatorics. Addison-Wesley, 1995. N. J. Vilenkin: Kombinatorika. SNTL, Praha 1977 (překlad z ruštiny). I. M. Vinogradov: Základy theorie čísel. ČSAV, Praha 1953 (překlad z ruštiny).

Relevantní zdroje na internetu

http://sue.csc.uvic.ca/˜cos/

(Combinatorial Object Server)

http://www.cs.sunysb.edu/ãlgorith/

(The Stony Brook Algorithm Repository)

http://www.schoolnet.ca/vp/ECOS/

(The Amazing Mathematical Object Factory)

http://www.research.att.com/ñjas/sequences

(Sloane’s web page)

http://www.math.uga.edu/ñtheory/

(The Number Theory Pages)

http://www.mersenne.org/

(Great Internet Mersenne Prime Search)

http://www.utm.edu/research/primes

(The Prime Pages)

http://www.cs.purdue.edu/homes/ssw/cun/

(The Cunningham Project)

http://www.best.com/˜cgd/home/flt/

(Fermat’s Last Theorem)


strana 115

DISKRÉTNÍ MATEMATIKA II

Recommend Documents