Diskrétní matematika (MA0002)
—
Kombinatorika: Základní kombinatorická pravidla.
—
Odvození kombinatorických vzorců:
Permutace, variace, kombinace bez opakování a s opakováním.
—
Faktoriály a kombinační čísla. Binomická věta.
Princip inkluze a exkluze a další kombinatorické lahůdky.
—
Konečné součty.
—
Dělitelnost celých čísel. Základní věta aritmetiky.
—
Dělitelnost polynomů. Hledání kořenů polynomu.
Dělení polynomu polynomem. Euklidův algoritmus.
—
Základy teorie grafů.
—
Studijní text PdF MU - verze ze dne 29. října 2021
Helena Durnová
Pracovní verze
Obsah
I Spíše teoretická část 4
1 Značení a úmluvy 5
1.1 Číselné obory . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Jak psát řešení příkladů . . . . . . . . . . . . . . . . . . . . . 5
1.3 Důkaz jako prostředek komunikace v matematice . . . . . . . 5
2 Kombinatorika 6
2.1 Faktoriály a kombinační čísla. Kombinatorické identity. . . . . 8
2.2 Variace, permutace, kombinace. . . . . . . . . . . . . . . . . . 11
2.3 Další úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Binomická věta . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Princip inkluze a exkluze. . . . . . . . . . . . . . . . . . . . . 15
2.6 Sspeciální princip inkluze a exkluze . . . . . . . . . . . . . . . 18
2.7 Kompozice a rozklady. . . . . . . . . . . . . . . . . . . . . . . 18
2.8 Rozdělování do přihrádek. . . . . . . . . . . . . . . . . . . . . 20
2.9 Závěrem ke kombinatorice. . . . . . . . . . . . . . . . . . . . . 21
3 Rekurentní vztahy. Konečné součty. 22
4 Základy elementární teorie čísel 24
4.1 Znaky dělitelnosti (známe často ze ZŠ) . . . . . . . . . . . . . 25
4.2 Prvočísla a čísla složená. Základní věta aritmetiky. . . . . . . 27
4.3 Kongruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 Diofantické rovnice a Eukleidův algoritmus . . . . . . . . . . . 28
4.5 Úlohy na zbytkové třídy (důkazy) . . . . . . . . . . . . . . . . 32
5 Dělitelnost polynomu. Hledání kořenů polynomu. 33
6 Základy teorie grafů 34
II Domácí práce: zadání a řešení 36
1
Předmluva
Motto:
„Nevyučuj toho, kdo není připraven, aby byl vyučován.“
(Jan Ámos Komenský)
Matematika provází všechny děti po celou základní školní docházku od
70. let 20. století pod tímto jménem a pod jmény jinými (počty a měřictví,
či aritmetika a geometrie) ještě déle. Některé děti matematika prostě baví,
některé ne, ale přesto se jí musí učit všechny, stejně jako třeba češtině či
tělocviku.
V dnešní době se stalo módou chlubit se neznalostí matematiky, začněme
tedy kacířskou otázkou: co by se stalo, kdybychom děti, které matematické
poznatky přirozeně nechápou, povinnosti učit se matematiku zprostili? Odpovědět
na ni dokážeme teprve tehdy, když si uvědomíme, jaké učitele matematiky
jsme zažili a co od nás matematika vyžadovala.
Matematika se dá — s velkou nadsázkou — přirovnat ke sportu. Ani
ve sportu není talent všechno; skoro u každého je potřeba trénink. Tak je
tomu i s matematikou: během školní docházky se v matematice učíme postupům,
které nám procvičováním přejdou do krve. A tak si při při písemném
sčítání „sloupečků“ i v dospělosti pomáháme prsty. Pravda, příležitostí k využití
této dovednosti máme díky přítomnosti kalkulačky ve všudypřítomných
mobilních telefonech pramálo, ale když bylo vynalezeno auto, také jsme nepřestali
chodit pěšky a jezdit na kole.
Ve výuce matematiky se často klade důraz na správný zápis, na to, aby
byl výsledek dvakrát podtržen, na to, aby znaménko rovnosti bylo v úrovni
hlavní zlomkové čáry složeného zlomku. Všechny tyto věci se zvenčí mohou
zdát podružnými a nepodstatnými, ale právě tyto návyky nás učí odlišovat
podstatné od nepodstatného: vezměme si jako příklad pomocné výpočty
psané tužkou na okraj sešitu nebo dokonce na šmírák. Podobně důraz na
úpravu a dodržování pravidel není samoúčelný, nýbrž nám samotným později
ve složitějších výpočtech usnadní orientaci. Během hodin matematiky se
tak cvičíme v disciplíně; například samotné numerické počítání asi baví málokoho,
přesto je bezchybný numerický výpočet nutný pro dosažení správné
odpovědi na otázku, kterou jsme si položili.
Význam matematiky pro studující bývá často přirovnáván k latině. V
knize Nebezpečí jednotné školy použil Rudolf Mertlík slova Zdeňka Nejedlého:
Netajím se přesvědčením, že latina je velmi důležitý výchovný
předmět. Vzpomínám-li na své vzdělání, které z předmětů mi
2
vlastně co daly, byla to matematika (ačkoliv jsem historik) a latina.
To jsou předměty, které jsou takovou dresurou přesného
myšlení. Jen ten, kdo nezná latinský jazyk, může tvrdit, že je ho
možno nahradit jiným živým jazykem. Žádná frančtina, angličtina
ani jiná řeč nenahradí latinský jazyk. Není jazyka, který by
měl takovou logickou konstrukci, jako má klasická latina.
Latina už se dnes povinně učí na málokterém gymnáziu. Roli pomyslného
biče tak převzala matematika: všimněte si, že Nejedlý mluvil o tréninku
přesného myšlení. Samozřejmě, že i v matematice můžeme být kreativní, ale
současně musíme dodržovat jistá pravidla; podobně jako při hře v šachy.
Přesnost, kterou skrze matematiku pěstujeme, však netkví v počtu desetinných
míst výsledku.
Na závěr dovolte několik vět k předkládanému textu. Je věnován některým
partiím z tzv. diskrétní matematiky, zde konkrétně z teorie čísel, kombinatoriky
a teorie grafů a je koncipován spíše jako vodítko k Vaší orientaci.
Všechny partie zde probírané byly již popsány v řadě knih, na něž se v textu
odkazujeme. Nepochopíte-li vše hned, nezoufejte a mějte na paměti, že vše
lze pochopit, vyvinete-li dostatečné úsilí. Matematika je také práce.
3
Část I
Spíše teoretická část
4
Kapitola 1
Značení a úmluvy
Matematická komunikace je založena na konvencích. (Henri Poincaré) Proto
bude dobré, když si pro začátek některé pojmy a jejich značení sjednotíme.
Pro úspěšné zvládnutí předmětu není vždy bezpodmínečně nutné veškeré zde
uvedené konvence dodržet, ale můžete se sem vracet, bude-li v textu použito
značení, kterému z jakéhokoliv důvodu nebudete rozumět.
1.1 Číselné obory
N přirozená čísla (1, 2, 3, ...; nula není přirozené číslo)
Z celá čísla (. . . , -2, -1, 0, 1, 2, . . . )
Q racionální čísla čísla tvaru p
q , kde p ∈ Z a q ∈ N
R reálná čísla „lze vyjádřit jako délku úsečky“
C komplexní čísla čísla tvaru a + bi, kde a, b ∈ R a pro i platí: i2 = −1
1.2 Jak psát řešení příkladů
• čitelně (není třeba krasopisně) a tak, abyste po pěti letech sami věděli,
jak jste příklad řešili
• opticky oddělujme stěžejní a pomocné výpočty; pomocné výpočty můžeme
např. psát tužkou
• . . .
1.3 Důkaz jako prostředek komunikace v matema-
tice
Dohodneme-li se na značení, shodneme-li se na definicích, dospějeme v matematice
k těm samým výsledkům. V tomto procesu je důkaz prostředke
přesvědčování druhých, avšak nikoli ve smyslu nátlaku, ale spíše pomoci,
tak, aby také viděli to, co vidíme my. (František Kurřina: matematika jako
umění vidět)
5
Kapitola 2
Kombinatorika
Řada knih zabývajících se kombinatorikou a jejími počátky poukazuje na zálibu
lidí v přeskupování a vytváření vzorů. Athanasius Kircher (1602–1680)
v ní viděl největší umění a svou knihu věnovanou kombinatorice nazval Ars
Magna Sciendum, Sive Combinatoria. Kombinatorické úlohy jsou pro malé
počty prvků zábavné a snadno řešitelné jednoduchým způsobem, totiž vypsáním
všech možností. Při větším počtu však působí spíše magickým dojmem,
protože není v našich silách představit si všechny možnosti, pročež musíme
více důvěřovat korektnosti naší úvahy.
V moderním množinovém vyjádření můžeme stručně a jasně psát:
Věta 2.1 (Pravidlo součtu) Nechť A, B jsou množiny, A ∩ B = ∅. Pak
|A ∪ B| = |A| + |B|.
Příklad 2.2 Na otázku „kolika způsoby lze na šachovnici postavit pěšáka?“
lze odpovědět také rozdělením šachovnice na černá a bílá políčka. Pro variantu,
jak postavit pěšáka na bílé políčko, máme 32 možností; pro variantu,
kdy pěšák stojí na černém políčku, máme také 32 možností. Celkem je možností
64 = 32 + 32 (stojí-li pěšák na černém políčku, nestojí na bílém, a
naopak).
Věta 2.3 (Pravidlo součinu) Nechť A, B jsou neprázdné množiny. Pak
|A × B| = |A| · |B|.
Příklad 2.4 Ptáme-li se, kolika způsoby můžeme postavit na šachovnici černou
a bílou dámu tak, aby černá dáma stála na černém políčku a bílá na bílém,
odpověď určíme jako 32 · 32 = 1 024
V následujícím příkladu zkombinujeme pravidlo součtu a součinu:
Příklad 2.5 Kolik různých slov lze získat přeházením písmen slova KOLENA
tak, že se v nich samohlásky a souhlásky střídají a souhlásky jsou
seřazeny abecedně?
Pokud jsou souhlásky na sudých pozicích a samohlásky na lichých, můžeme
takto získat 6 slov (6 = 3! = 3 · 2 · 1) a stejně slov získáme i tehdy,
jsou-li souhlásky na lichých pozicích a samohlásky na sudých [užili jsme pravidlo
součinu]. Celkem je možností 12 = 6 + 6, neboť pokud jsou souhlásky
na sudých místech, nejsou na lichých místech a naopak [užili jsme pravidlo
součinu].
6
Věta 2.6 (Přihrádkový, též zvaný Dirichletův, princip) Máme-li rozdělit
n + 1 předmětů do n přihrádek, pak při libovolném rozdělení budou v
alespoň jedné přihrádce alespoň dva předměty.
Příklad 2.7 V zásuvce je 12 párů červených a 12 párů modrých ponožek. Pokud
bereme ponožky z přihrádky poslepu, kolik ponožek musíme vzít, abychom
měli alespoň dvě ponožky téže barvy?
[Stačí vytáhnout tři ponožky.]
Všechny kombinatorické vzorce, které znáte ze střední školy, se dají odvodit
pomocí pravidla součtu a pravidla součinu. Přihrádkový (Dirichletův)
princip lze s výhodou použít při řešení některých příkladů.
Několik postřehů z historie kombinatoriky. Kombinatorická pravidla
jsou tak jednoduchá a samozřejmá, že těžko můžeme očekávat, že bychom
v historických pramenech našli zmínky o jejich přesné formulaci.1 Zmínky
o úlohách, které bychom dnes klasifikovali jako kombinatorické, nacházíme
především v indických a čínských textech. První zmínky se však objevují již
ve starověkém Egyptě, jak dokládá následující
úloha z Rhindova papyru s poměrně nejasným zadáním. Obsahuje sloupec
(viz též ??)
domy 7
kočky 49
myši 343
pšenice 2401
hekaty 6807
19607
Obrázek 2.1: Úloha o majetku z Rhindova papyru. Převzato z knihy Vymazalová,
Hana. Hieratické texty.
Podobné počty najdeme i u Fibonnacciho (Liber abaci, 1202) ve formě
říkanky o sedmi starých ženách, které jdou do Říma:
1
Biggs, N. 1979. ‘Roots of combinatorics’. Historia Mathematica 6:109-136.
7
Sedm starých žen šlo do Říma
každá nesla.....
Kolik....
Tyto počty se dochovaly i v dětské říkance „Když jsem šel do St. Ives“:
As I was going to St. Ives,
I met a man with seven wives.
Each wife had seven sacks.
In each sack there were seven cats.
Each cat had seven kits.
Kits, cats, sacks, and wives,
How many were going to St. Ives?
Možná byly doby, kdy takové počítání patřilo spíše k zábavě, ale i ta patří
k matematice. Traduje se, že kombinatorické myšlení bylo pěstováno spíše
v Indii než v Evropě. Známá je úloha o počtu možných kombinací z pětii
chutí: slaná, sladká, hořká, pálivá a trpká. Výčtem všech možností dojdeme
k počtu 31:
5 chutí - 1 možnost
4 chutě - 5 možností (vždy se jedna vynechá)
3 chutě - 10 možností (kombinace 3 z 5)
2 chutě - 10 možností (kombinace 2 z 5)
1 chuť - 5 možností
(buď sladká, nebo slaná, nebo hořká, nebo pálivá, nebo trpká)
Na této úloze může být zajímavé si povšimnout, že možnost „bez chuti“ se
nepočítá; jinak se vlastně jedná o počet podmnožin pětiprvkové množiny,
kterých je 25 = 32. Vzhledem k tomu, že prázdná množina je jen jedna,
skutečně stačí odečíst 1.
V Evropě se dostala kombinatorika do obecného povědomí nejpozději v 17.
století v souvislosti s výpočtem počtu možností při hazardních hrách. Klasifikaci
na permutace, variace a kombinace znal už Jacob Bernoulli (1654–1708),
švýcarský matematik.
2.1 Faktoriály a kombinační čísla. Kombinatorické
identity.
V tomto oddíle stručně shrneme některé poznatky o faktoriálech a kombinačních
číslech tak, abychom s nimi v dalším mohli počítat bez dalšího
vysvětlování. Funkci faktoriál definujeme pouze pro přirozená čísla:
Definice 2.8 (Faktoriál přirozeného čísla) Pro libovolné n ∈ N klademe
n! = 1 · 2 · · · · · n (čteme: „n faktoriál“).
Dále klademe 0! = 1. Na okraj uveďme, že pojem faktoriálu lze rozšířit
i mimo obor přirozených čísel.
8
Tabulka hodnot faktoriálů pro n = 1 . . . 10, z níž je patrné, jak rychle
tato funkce roste:
0! 1
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
Definice 2.9 (Kombinační číslo) Pro libovolná k, n ∈ N definujeme kombinační
číslo (čteme: „n nad k“) takto:
n
k
=
n!
(n − k)!k!
Podobně jako pojem faktorál lze i i pojem kombinačního čísla rozšířit mimo
obor přirozených čísel; v kombinatorice však vystačíme s kombinačními čísly,
v nichž n i k budou přirozená čísla, pro něž navíc platí 0 ≤ k n. Hodnoty
kombinačních čísel lze elegantně zapsat do trojúhelníku, v němž na obou
ramenech jsou čísla 1 (n nad nulou stejně jako n nad n je vždy jedna) a v
ostatních případech můžeme kombinační číslo určit jako součet dvou čísel,
která leží na odpovídajících místech v o řádek výš, jak je naznačeno na
Obr. 2.2.2
Obrázek 2.2: Řádky aritmetického trojúhelnííka pro n = 0 . . . 7.
Počítání s faktoriály a kombinačními čísly: Jednodušší příklady lze
řešit rozepsáním faktoriálů. Kombinační číslo n
k představuje vlastně stručný
zápis zlomku n!
k!(n−k)! , platí tedy: n
k = n
n−k .
2
Courtesy artofproblemsolving.com.
9
Kombinatorické identity: pro kombinační čísla platí řada tzv. kombinatorických
identit. Lze je dokázat jednak rozepsáním jednotlivých kombinačních
čísel, jednak kombinatorickou úvahou. Nejznámější z nich je tato:
n
k
+
n
k + 1
=
n + 1
k + 1
Lze ji jednoduše ověřit rozepsáním kombinačních čísel. Také si můžeme
uvědomit, že vybíráme-li např. tři osoby ze sedmi, je z početního hlediska
jedno zda počítáme trojice těch, kteří nás budou reprezentovat, nebo naopak
čtveřice těch, kteří “zůstanou doma”.
Uveďme některé další typy jednoduchých příkladů na toto téma::
(a) Dokažte: n! + (n − 1)!n2 = (n + 1)! (Stačí na levé straně vytknout n!.)
(b) Sečtěte: (n+2)!
n! − 2(n+1)!
(n−1)! + n!
(n−2)! [=2]
(c) Vyjádřete jedním kombinačním číslem: 9
4 + 9
6 [= 10
6 ]; 11
2 + 11
8
[= 12
3 ]; 12
5 + 12
6 [= 13
6 ].
Dále platí tyto jednoduché kombinatorické identity:
(i) n
k = n
n−k
(ii) n
k = n−1
k−1 + n−1
k
(iii) 2n = n
0 + n
1 + n
2 + · · · + n
n−1 + n
n
(iv) 0 = n
0 − n
1 + n
2 − · · · + (−1)n−1 n
n−1 + (−1)n n
n
(v) n−1
0 + n
1 + n+1
2 + · · · + n+m−1
m = + n+m
m
(vi) n
n + n+1
n + n+2
n + · · · + n+m−1
n = + n+m
m
(vii) 1 + 2 + · · · + m = m(m+1)
2
(viii) 1 · 2 + 2 · 3 + 3 · 4 + · · · + m · (m + 1) = m(m+1)(m+2)
3
(ix) 1·2·2+2·3·4+3·4·5+· · ·+m·(m+1)·(m+2) = m(m+1)(m+2)(m+3)
4
(x) n
0
n
m − n
1
n−1
m−1 + n
2
n−2
m−2 + · · · + (−1)n m
m
n−m
0 = 0
Jednoduchou úvahou z platnosti identity (iii) vyplývá platnost následujících
identit pro sudé n:
(iii-a) 2n−1 = n
0 + n
2 + n
4 + · · · + n
n
(iii-b) 2n−1 = n
1 + n
3 + n
5 + · · · + n
n−1
a analogicky pro liché n:
(iii-c) 2n−1 = n
0 + n
2 + n
4 + · · · + n
n−1
(iii-d) 2n−1 = n
1 + n
3 + n
5 + · · · + n
n
10
Dále platí například:
(*) 4n = 2n+1
0 + 2n+1
1 + 2n+1
2 + 2n+1
3 + · · · + 2n+1
n
Řada vztahů mezi kombinačními čísly je patrná z tzv. Pascalova (též
aritmetického) trojúhelníka.
DOPLŇ OBRÁZEK ARITMETICKÉHO TROJÚHELNÍKA
Rovnice s kombinačními čísly
Cvičení 2.10 Najděte všechna x, pro něž platí:
x − 1
x − 3
+
x − 2
x − 4
= 9
[5]
Cvičení 2.11 Určete m, n, víte-li, že platí:
n + 1
m + 1
=
n + 1
m
=
5
3
m + 1
m − 1
[n = 6, m = 3]
2.2 Variace, permutace, kombinace.
V následujícím odvodíme pomocí pravidla součtu a součinu vzorce, které
znáte ze střední školy pod názvy variace, permutace a kombinace (bez opakování
a s opakováním). Postup vysvětlíme vždy na nějakém příkladu.
Variace bez opakování:
Příklad 2.12 Kolika způsoby lze na šachovnici rozestavit dámu, krále a věž?
Řešení: Opakovaným použitím pravidla součinu: 64 · 63 · 62 = 249 984
Obecně pokud vybíráme k předmětů z celkového počtu n předmětů, přičemž
k, n ∈ N a k ≤ n, možností je
n · (n − 1) · (n − 2) · · · · · (n − k + 1) =
n!
(n − k)!
Permutace bez opakování jsou zvláštním případem variací pro n = k.
Někdy mluvíme také o pořadí.
Příklad 2.13 Kolika způsoby lze sestavit devítimístné číslo z cifer 1 až 9
takové, že se v něm cifry neopakují?
Řešení: Opakovaným použitím pravidla součinu: 9 · 8 · · · · · 1 = 362 880
Obecně je počet pořadí n prvků roven n! (n ∈ N)
Příklad 2.14 Určete součet všech čtyřciferných čísel sestavených z cifer
1, 2, 3, 4.
Řešení: 640 + 6400 + 64000 + 640000 (číslice se mohou opakovat); 60 +
600 + 6000 + 60000 (číslice se nemohou opakovat).
11
Kombinace bez opakování: uvědomíme si, že množství stejně početných
variací a kombinací bez opakování prvků vybíraných ze stejně velké množiny
spolu úzce souvisí. V podstatě stačí počet variací vhodným číslem vydělit;
tímto vhodným číslem je faktoriál počtu vybíraných prvků; tj.
n!
(n − k)!k!
To je právě kombinační číslo:
n
k
=
n!
(n − k)!k!
Příklad 2.15 Kolika způsoby lze na šachovnici rozestavit tři bílé pěšáky?
Řešení: Vyjdeme z příkladu, kdy jsme na šachovnici měli postavit krále,
dámu a věž; možností bylo 64 · 63 · 62 = 249 984, Je zřejmé, že pokud na
tři daná políčka postavíme tři pěšáky, je možnost jediná (pěšáci jsou stejní),
zatímco krále, dámu a věž na tatáž políčka postavíme 3 · 2 · 1 = 6 způsoby.
U variant „s opakováním“ začneme s odvozováním vzorců také u variací.
Variace s opakováním
Příklad 2.16 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla.
Kolika způsoby si mohou objednat?
Řešení: Každý z hostů má 4 možnosti, tedy 4·4·4·4·4·4·4·4·4·4·4·4 = 412
možností.
Podobným způsobem lze odvodit počet podmnožin množiny A o n prv-
cích:
2|A|
= 2n
Permutace s opakováním tentokrát nejsou zvláštním případem variací.
Příklad 2.17 Kolika způsoby můžeme přeskládat písmena slova
(a) TATA
(b) POPOCATEPETL
Řešení:
(a) Vypíšeme možnosti dle abecedy: AATT, ATTA, ATAT, TAAT, TATA,
TTAA. To odpovídá permutacím všech čtyř písmen vyděleným permutacemi
opakujících se písmen, tj. 4!
2!2!
(b) Analogicky slovo POPOCATEPETL má 3 P, 2 O, 2 T, 2 E, 1 A, 1 C
1 L, tj. dohromady 12 písmen a možností přeházení je tedy 12!
3!2!2!2!1!1!1!
12
Kombinace s opakováním vyžadují zvláštní přístup. Začneme „kódovat“
a sestrojovat bijekce (vzájemně jednoznačná zobrazení) mezi objekty, jejichž
počet máme spočítat, a objekty, jejichž počet budeme umět spočítat.
Příklad 2.18 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla.
Kolika může být objednávek z hlediska kuchaře?
Řešení: Kuchaři je jedno, kdo si objednal které jídlo, zajímá ho pouze,
kolik má připravit porcí jídla č. 1 až 4. Možností je 12+4−1
4−1 = 12+4−1
12
Příklad 2.19 Kolika způsoby mohu vybrat deset mincí v hodnotě 5, 10 a 20
Kč? (Máme dostatečný počet mincí každé hodnoty.)
Řešení: Možností je 10+3−1
3−1 = 10+3−1
10 = 66
Oba výše uvedené případy můžeme „zakódovat“ pomocí nul a jedniček.
V příkladě s mincemi si například můžeme představit, že mince uspořádáme
podle hodnoty: nejprve dvacetikoruny, pak desetikoruny a nakonec pětikoruny.
Místo dvacetikorun napíšeme do řádku příslušný počet jedniček; za ně
napíšeme nulu. Pokračujeme tak, že zapíšeme tolik jedniček, kolik je desetikorun;
za ně opět napíšeme nulu. Nakonec napíšeme tolik jedniček, kolik je
pětikorun. Je zřejmé, že psát za nimi nulu je nadbytečné: pokud hromádka
dvaceti-, deseti- a pětikorun splňuje zadání a obsahuje deset mincí, napsali
jsme posud deset jedniček a dvě nuly. Je zřejmé, že mezi hromádkami mincí
a permutacemi deseti jedniček a dvou nul existuje vzájemně jednoznačné
zobrazení, neboli vyhovujících hromádek je právě tolik, kolik je permutací
deseti jedniček a dvou nul. Ty však již umíme spočítat: jedná se o předchozí
výsledek, který jsme nazvali permutace s opakováním (deseti jedniček a dvou
nul).
Výše uvedené odvození můžeme zopakovat při řešení jednotlivých příkladů;
je to spolehlivější než snaha dosazovat naslepo do vzorečku pro kombinace
s opakováním, kdy vybíráme k prvků n druhů:
Co(k, n) =
k + n − 1
n − 1
=
k + n − 1
k
Vzoreček pro kombinace s opakováním, v němž přehodíme značení pro
druhy a počet prvků ,a tedy vybíráme n prvků k druhů, totiž na první pohled
vypadá dost podobně.
2.3 Další úlohy
Nyní si ukážeme několik zajímavých příkladů, u kterých vhodně využijeme
výše uvedené vzorce a pravidla. Jsou převzaty z jiných učebnic, zejména
z výborných skript Antonína Vrby ([3]).
Příklad 2.20 Kolika způsoby lze přeskládat písmena slova LOKOMOTIVA
tak, aby žádná dvě „O“ nestála vedle sebe?
Řešení: Nejprve určíme, kolika způsoby lze přeskládat písmena L, K,
M, T, I, V, A. To lze provést 7! způsoby. Při libovolném z těchto rozložení
máme posloupnost sedmi písmen. Abychom vyhověli podmínkám, můžeme O
vložit před nebo za tuto posloupnost nebo do mezer mezi písmeny, přičemž na
každé z těchto míst lze vložit nejvýše jedno O. Taková místa můžeme vybrat
8
3 způsoby. Možností je tedy 7! 8
3 .
13
Příklad 2.21 Krotitel má do arény přivést 4 tygry a 5 lvů tak, aby žádní
dva tygři nešli za sebou. Kolika způsoby to lze provést?
Řešení: Nejrpve určíme počet seřazení tygrů a lvů bez ohledu na to,
který tygr a který lev kde konkrétně bude. Symbolicky můžeme napsat, že
hledáme permutace pěti L a čtyř T takových, že žádná dvě T nenásledují
těsně za sebou; například LTLTLTLTL. Takových rozmístění je 6
4 (mezi
pěti L jsou čtyři mezery, jedno místo je před prvním L a jedno za posledním;
podobně jako v předchozím příkladu vyberem z těchto šesti míst čtyři místa,
na něž umístíme T). V dalším kroku pak „dáme lvům a tygrům jména“, což
početně znamená, že například místo uvedené permutace bezejmenných tygrů
LTLTLTLTL dostáváme 5! · 4! Celkem je tedy možností 5! 6
4 · 4!
2.4 Binomická věta
Věta 2.22 Nechť a, b jsou proměnné, n ∈ N. Platí následující vztahy:
(a + b)n
=
n
0
an
+
n
1
an−1
b1
+ · · · +
n
n − 1
a1
bn−1
+
n
n
bn
a analogicky
(a − b)n
=
n
0
an
−
n
1
an−1
b1
+ · · · + (−1)n−1 n
n
bn
Příklad 2.23 Speciálními přiklady binomické věty jsou známé vzorce:
(a + b)2
=
2
0
a2
+
2
1
ab +
2
2
b2
(a − b)2
=
2
0
a2
−
2
1
ab +
2
2
b2
(a + b)3
=
3
0
a3
+
3
1
a2
b +
3
2
ab2
+
3
3
b3
(a − b)3
=
3
0
a3
−
3
1
a2
b +
3
2
ab2
−
3
3
b3
Se vzorci, které se opticky podobají binomické větě, se setkáte např. i v
matematické analýze.
Binomické věty lze s výhodou užít například při těchto výpočtech:
(a) 1015 = (100 + 1)5 = 1005 + 5 · 1004 + 10 · 1003 + 10 · 1002 + 5 · 100 + 1
(b) 995 = (100 − 1)5 = 1005 − 5 · 1004 + 10 · 1003 − 10 · 1002 + 5 · 100 − 1
V obou výše uvedených případech je výpočet jednodušší než přímo umocňovat
101 a 99.
Podobně lze umocňovat i komplexní čísla v algebraickém tvaru. Pro to,
abychom mohli podobné příklady počítat, vystačíme se znalostí faktu, že
každé komplexní číslo lze zapsat ve tvaru a + bi, přičemž platí i2 = −1.3
3
Pro ty, kteří se s komplexními čísly dosud nesetkali, doporučujeme např. knihu Emila
Caldy Komplexní čísla z řady Matematika pro gymnázia nakladatelství Prometheus.
14
Cvičení a úkoly k zamyšlení: binomická věta
Cvičení 2.24 Dokažte binomickou větu metodou matematické indukce.
Cvičení 2.25 Dokažte binomickou větu metodou matematické indukce.
Cvičení 2.26 Určete, který sčítanec je v binomickém rozvoji
√
2 +
√
3
50
největší.
[ 50
22
√
2
22√
3
28
]
2.5 Princip inkluze a exkluze.
V některých kombinatorických úlohách se výsledku dobereme tak, že nejprve
vezmeme počet možností, který umíme dobře spočítat, i když víme, že
tak zahrneme možností příliš mnoho; poté počet upravíme například odečtením
nepříznivých případů nebo vydělením. Tyto postupy jsme už použili
pro odvození vzorců pro kombinace (podělením příslušného počtu variací),
pro permutace s opakováním (podělením celkového počtu permutací počty
permutací opakujících se písmen), a tedy i pro odvození vzorce pro výpočet
kombinací s opakováním. Ukažme si tuto strategii řešení na některých dalších
příkladech.
Příklad 2.27 úprava výsledku dělením - př. č. 1
Příklad 2.28 úprava výsledku dělením - př. č. 2
Příklad 2.29 úprava výsledku odečtením - př. č. 1
Příklad 2.30 úprava výsledku odečtením - př. č. 2
Příklad 2.31 úprava výsledku odečtením - př. č. 3
Někdy nedokážeme určit výsledek pouze pomocí jediného odečtení a musíme
opět nějaké možnosti přičíst.
Nejjednodušším použitím principu inkluze a exkluze je vztah pro určení
počtu prvků sjednocení dvou konečných množin:
|A ∪ B| = |A| + |B| − |A ∩ B|
Pro odvození vztahu pro určení počtu prvů sjednocení tří množin můžeme
použít například Vennovy diagramy (viz Základy matematiky). Snadno
nahlédneme, že
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|;
pro čtyři množiny:
|A ∪ B ∪ C ∪ D| =
|A| + |B| + |C| + |D|
−|A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D|
15
+|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|;
pro pět množin:
|A ∪ B ∪ C ∪ D ∪ E| =
|A| + |B| + |C| + |D| + |E|
−|A∩B|−|A∩C|−|A∩D|−|A∩E|−|B∩C|−|B∩D|−|B∩E|−|C∩D|−|C∩E|−|D∩E|
+|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|
−|A ∩ B ∩ C ∩ D| − |A ∩ B ∩ C ∩ E| − |A ∩ C ∩ D ∩ E| − |B ∩ C ∩ D ∩ E|
+|A ∩ B ∩ C ∩ D ∩ E|
atd., a tedy pro n množin lze formulovat
Obecný princip inkluze a exkluze:
|M1 ∪ M2 ∪ · · · ∪ Mn| =
|M1| + |M2| + · · · + |Mn|
−|M1 ∩ M2| − |M1 ∩ M3| − · · · − |M1 ∩ Mn|
−|M2 ∩ M3| − · · · − |M2 ∩ Mn| − |M3 ∩ M4| − · − |Mn−1 ∩ Mn|
+|M1 ∩ M2 ∩ M3| + · · · |Mn−2 ∩ Mn−1 ∩ Mn|
− · · · + · · · + (−1)n
|M1 ∩ M2 ∩ · · · ∩ Mn|
Příklad 2.32 (Eratosthenovo síto) Kolik je prvočísel mezi čísly od 1 do
100.
Můžeme si představit, že budeme postupovat jako prý postupoval Eratoshenes
ve starověkém Řecku: na voskovou tabulku napíšeme čísla od 1 do
100 a horkou jehlou „propichujeme“ místa označená násobky prvočísel, tj.
násobky 2: 4, 6, 8, 10, . . . atd., násobky 3: 6, 9, 12, . . . atd., násobky 5: 10,
15, 20, 25, . . . atd. a násobky 7: 14, 21, . . . atd.
Snadno nahlédneme, že některá čísla vypichujeme vícekrát, například 6,
10, 15, 30, . . . atd. toho níže využijeme. Dále využijeme skutečnosti, že při
zkoumání toho, zda je dané číslo n prvočíslo, stačí vyzkoušet dělitelnost
prvočísly do hodnoty
√
n (včetně). V našem případě hledáme prvočísla do
100, tedy stačí zkoumat děliletnost prvočísly 2, 3, 5 a 7.
Víme, že 1 není prvočíslo, tedy můžeme počítat s 99 čísly. Nejprve od 99
odečteme počet všech násobků 2, 3, 5 a 7 s výjimkou těchto prvočísel:
99 − 49 − 32 − 19 − 13 = 50 − 51 − 13 = −14
Výsledkem je záporné číslo, neboť např. číslo 6 jsme odečetli dvakrát:
jednou jako násobek dvou, jednou jako násobek tří. Všechna tato nedopatření
se pokusíme napravit naráz tím, že přičteme zpět násobky 6, 10, 14, 15, 21
a 35:
99 − 49 − 32 − 19 − 13 + 16 + 10 + 7 + 6 + 4 + 2 = 31
Teď již nemáme varování v podobě záporného výsledku, ale snadno nahlédneme,
že jsme například 30 přičetli třikrát: v prvním kroku jsme 30
16
třikrát odečetli (jako násobek 2, 3 a 5) a nyní jsme je třikrát přičetli (jako
násobek 6, 10 a 15). Číslo 30 ale není prvočíslo, je tedy třeba je (a jemu podobná
čísla, např. 70) odečíst. Dalším pokusem o nápravu je tedy odečtení
násobků trojic prvočísel, tj. 30, 42, 70 a 105:
99 − 49 − 32 − 19 − 13 + 16 + 10 + 7 + 6 + 4 + 2 − 3 − 2 − 1 = 25
Naši snahu by mohlo zhatit číslo, které by bylo dělitelné všemi čtyřmi
prvočísly; nejmenší takové číslo však je 210, a tedy bychom přičetli 0 (tolik
je mezi čísly od 1 do 100 násobků 210).
(Jen pro úplnost: v prvním kroku bychom je 4x odečetli, následně 6x
přičetli a nakonec 4x odečetli; v součtu bychom je tedy odečetli 2x, přičemž
jsme je chtěli odečíst pouze 1x; to bychom napravili tím, že bychom je nyní
ještě 1x přičetli; nic takového však dělat nemusíme, protože číslo 210 vůbec
do hry nevstoupilo: počítali jsme stále pouze s čísly menšími nebo rovnými
100.)
Pro pořádek odpověď: mezi čísly 1 až 100 je 25 prvočísel.
Příklad 2.33 (jazyky) V oddělení pracuje nekolik osob, z nichž každá zná
alespoň jeden z těchto jazyků: ruština, španělština, italština. Rusky mluví
6 osob, španělsky 6 osob, italsky 7 osob, rusky a španělsky mluví 4 osoby,
španělsky a italsky 3 osoby, rusky a italsky 2 osoby, všechny tři uvedené
jazyky ovládá 1 osoba.
(a) Kolik osob pracuje v oddělení?
(b) Kolik z nich mluví rusky, avšak ne španělsky ani italsky?
(c) Kolik z nich mluví španělsky, avšak ne rusky ani italsky?
[(a) 11; (b) 1; (c) 3]
Definujeme-li jednotlivé množiny pomocí vlastností, pak množina
M1 obsahuje prvky s vlastností 1, množina Mn prvky s vlastností i, analogicky
Mi ∩ Mj prvky s vlastnostmi i a současně j, atd. Pak lze např.
odvodit, že prvků, které nemají žádnou z požadovaných vlastností (přičemž
prvky, které nemají vlastnost i označíme M1
′
a množinu obsahující všechny
uvažované prvky označíme M), je
|M1
′
∩ M2
′
∩ · · · ∩ Mn
′
| =
|M| − |M1| − |M2| − · · · − |Mn|
+|M1 ∩ M2| + |M1 ∩ M3| + · · · + |M1 ∩ Mn|
+|M2 ∩ M3| + · · · + |M2 ∩ Mn| + |M3 ∩ M4| + · + |Mn−1 ∩ Mn|
−|M1 ∩ M2 ∩ M3| − · · · |Mn−2 ∩ Mn−1 ∩ Mn|
+ · · · − · · · + (−1)n
|M1 ∩ M2 ∩ · · · ∩ Mn|
příklady:
lednička, auto, chata
znalost jazyků
kroužky
17
2.6 Sspeciální princip inkluze a exkluze
Úlohy, jejichž výpočet vede na tzv. speciální princip inkluze a exkluze, lze
formulovat jako „problém šatnářky“ nebo „problém roztržité sekretářky“.
Naším úkolem je určit, v kolika případech nedostane žádný pán svůj klobouk
nebo v kolika případech se nedostane žádný dopis ke svému adresátovi. Počet
možností zde nezávisí na konkrétní osobě, ale pouze na počtu osob, které
nedostanou svůj klobouk nebo dopis.
pro 4 osoby - 9 možností:
pro 5 osob - 44 možností:
Cvičení 2.34 Na třídní schůzce informoval učitel rodiče takto:
„Naše třída má 30 žáků. Mohou chodit do 4 zájmových kroužků, z nichž
každý probíhá jednou týdně. Pondělní kroužek navštěvuje 29 žáků, úterní 13,
středeční 18 a čtvrteční 11. Žádný žák nenavštěvuje více než dva kroužky a
žádné dva kroužky nemají více než 5 společných žáků. “
Určete, zda učitel mluvil pravdu
[Ne. Návod: použijte princip inkluze a exkluze a selský rozum.]
Cvičení 2.35 Kolika způsoby lze na šachovnici n × n rozestavit n věží tak,
aby každé neobsazené pole šachovnice bylo ohrožováno nějakou věží?
[2nn − n! Návod: zkuste pro šachovnice o rozměrech 2 × 2, 3 × 3, atd.]
Cvičení 2.36 Máme pět obálek s adresami (pro 5 různých lidí) a pět dopisů.
Kolika způsoby můžeme vložit dopisy do obálek tak, aby ani jeden dopis
nebyl ve správné obálce?
[44]
2.7 Kompozice a rozklady.
Další kombinatorické kategorie. Kromě variací, permutací a kombinací
známe další typické kombinatorické kategorie. Z nich si nyní představíme
dva typy, a to počítání, kolika způsoby lze přirozené číslo zapsat ve
tvaru sčítanců–přirozených čísel, a dále počítání, kolika způsoby můžeme věci
(rozlišitelné nebo nerozlišitelné) rozdělit do přihrádek (rozlišitelných nebo
nerozlišitelných)Úmluva:
Pro účely tohoto textu rozumíme přirozenými čísly (a značíme
N) čísla !1, 2, 3, . . .; jinými slovy, nulu za přirozené číslo nepovažujeme
S rozklady (přirozeného) čísla na (přirozené) sčítance se setkávají děti
již v 1. třídě, kdy si ujasňují, že např. 5 = 4 + 1 = 2 + 3. Pokud bychom
vyjádření čísla 5 jako 1+4 a jako 4+1 považovali za navzájem různá, mluvili
bychom z kombinatorického hlediska o kompozicích (čísla 5 ze dvou sčítanců);
pokud by pro nás tato vyjádření byla totožná, jednalo by se z kombinatorického
hlediska o rozklady. Vdalším textu budeme o kompozicích a rozkladech
mluvit ve smyslu níže uvedených definic. Ty nám říkají, že zatímco u rozkladů
nezáleží na pořadí sčítanců, zatímco u kompozic ano. Rozdíl v počtu
18
kompozic a rozkladů si můžeme ukázat na počtu rozkladů a kompozic čísla 4:
Rozkladů čísla 4 je 5:
4 = 4 = 2 + 2 = 3 + 1 = 2 + 1 + 1 = 1 + 1 + 1 + 1
Kompozic čísla 4 je 8:
4 = 4 = 2 + 2 = 3 + 1 = 1 + 3 =
= 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 1 + 1 + 1 + 1
Definice 2.37 (Kompozice) Kompozicí přirozeného čísla n z k sčítanců
rozumíme každou uspořádanou k-tici přirozených čísel, pro niž platí ásledující
vztah:
n = a1 + a2 + . . . + ak
Na základě předchozí definice formulujeme kombinatorickou úlohu: kolik je
možných kompozic čísla n z k sčítanců?
Definice 2.38 (Rozklad) Roykladem přirozeného čísla n na k sčítanců rozumíme
každou nuspořádanou k-tici přirozených čísel, pro niž platí ásledující
vztah:
n = a1 + a2 + . . . + ak
Analogicky jako u předchozího příkladu můžeme formulovat kombinatorickou
úlohu: kolik je rozkladů čísla n na k sčítanců? Navíc se můžeme ptát, kolik je
všech rozkladů — bez ohledu a počet sčítanců. Je zřejmé, že sčítanců může
být nejméně 1 a nejvýše n.
Uveďmě jako příklad všechny rozklady čísla 10 na dva sčítance:
10 = 5 + 5
10 = 4 + 6
10 = 3 + 7
10 = 2 + 8
10 = 1 + 9
Zajímavosti k rozkladům a kompozicím
Ferrersovy diagramy
Adjungovaný rozklad
Samoadjungovaný rozklad
Uspořádání rozkladů
Znázornění uspořádání rozkladů pomocí hasseovského diagramu
Cvičení 2.39 Vypište všechny kompozice čísla 10 ze čtyř sčítanců.
Cvičení 2.40 Vypište všechny kompozice čísla 10 z nejvíše 4 sčítanců.
Cvičení 2.41 Vypište všechny rozklady čísla 12 na 5 sčítanců.
Cvičení 2.42 Vypočtěte počty kompozic a rozkladů uvedených v přechozích
příkladech pomocí vzorce pro výpočet počtu kompozic a rekurentního
vzorce pro výpočet počtu rozkladů.
Cvičení 2.43 Vypište všechny rozklady čísla 12 na 3 sčítance takové, že
každý ze sčítanců je roven nejvýše 6.
19
2.8 Rozdělování do přihrádek.
Část kombinatorických úloh se dá vhodně přeformulovat jako tzv. rozdělování
předmětů (věcí) do přihrádek. Toto převedení si částečně ukážeme při odvozování
příslušných vztahů;ty lze brátch prostě jako další nástroje k uchopení
kombinatorické problematiky. U jednotlivých případů tedy budeme ptát, zda
jsou přihrádky rozlišitelné (např. různě barevné krabice) nebo nerozlišitelné
(např. stejné krabice) a zda jsou předměty rozlišitelné (např. různé knihy)
nebo nerozlišitelné (stejné knihy). Na základě toho dostáváme čtyři situace,
které si popíšeme níže. Ještě předtím si stručně připomeneme jednoduchý,
ale účinný
Dirichletův (přihrádkový) princip: Při každém rozdělení n předmětů
do k přihrádek, kde k < n, existuje alespoň jedna přihrádka obsahující alespoň
dva předměty.
Příklad: Dokažte, že vyberem-li v obdélníku 6 cm × 4 cm libovolných 25
bodů, budou mezi nimi nejméně dva, jejichž vzdálenost je menší než 1, 5 cm.
Návod: Uvažujme body, jejichž souřadnice jsou celočíselné,
Příklad: Dokažte, že mezi sedmi různými přirozenými čísly jsou alespoň
dvě taková, jejichž součet nebo rozdíl je dělitelný 10.
Návod: Rozdělte čísla do tříd podle dělitelnosti 10.
Rozdělování rozlišitelných předmětů do rozlišitelných přihrádek
Nechť n, k jsou libovolná přirozená čísla. Pak lze n rozlišitelných předmětů
rozdělit do k rozlišitelných přihrádek rozdělit právě kn způsoby.
Rozdělování rozlišitelných předmětů do rozlišitelných přihrádek,
přičemž žádná přihrádka nezůstane prázdná Nechť n, k jsou libovolná
přirozená čísla, n ≥ k. Pak lze n rozlišitelných předmětů do k rozlišitelných
přihrádek tak, aby žádná přihrádka nezůstala prázdná, rozmístit
právě
k!S(n, k) = Σk
i=0(−1)i k
i
(k − i)n
způsoby.
Rozdělování nerozlišitelných předmětů do rozlišitelných přihrádek
Nechť n, k jsou libovolná přirozená čísla,. Pak lze n nerozlišitelných předmětů
do k rozlišitelných přihrádek rozdělit právě
n + k − 1
k − 1
způsoby.
20
Rozdělování nerozlišitelných předmětů do nerozlišitelných přihrádek,
přičemž žádná přihrádka nezůstane prázdná Nechť n, k jsou
libovolná přirozená 4ísla,. Pak lze n nerozlišitelných předmětů do k rozlišitelných
přihrádek tak, aby v každé přihrádce bylo aspoň r předmetů, rozdělit
právě
n − kr + k − 1
k − 1
způsoby; pro r = 1 je tento počet zřejmě
n − 1
k − 1
.
Rozdělování rozlišitelných předmětů do nerozlišitelných přihrádek
Nechť n, k jsou libovolná přirozená čísla,. Pak lze n rozlišitelných předmětů
do k nerozlišitelných přihrádek rozdělit právě
S(n, 1) + S(n, 2) + · · · + S(n, k)
způsoby. (S(n, k) jsou tzv. Stirlingova čísla.)
Rozdělování nerozlišitelných předmětů do nerozlišitelných přihrádek
Nechť n, k jsou libovolná přirozená čísla,. Pak lze n nerozlišitelných
předmětů do k nerozlišitelných přihrádek rozdělit právě
p(n, 1) + p(n, 2) + · · · + p(n, k)
způsoby; chceme-li, aby všechny přihrádky byly neprázdné, je tento počet
p(n, k).
2.9 Závěrem ke kombinatorice.
Dosud představené kombinatorické úlohy jsou samozřejmě pouhou „ochutnávkou“.
Vůbec jsme se nedotkli problematiky magických či latinských čtverců, neformulovali
jsme Kirkmanův problém 15 dívek, nedefinovali jsme Bellova či
Stirlingova čísla. To je obsahem pokročilejších kurzů diskrétní matematiky.
Zde probíraná látka představuje — kromě procvičení logického uvažování
atp. — průpravu pro teorii pravděpodobnosti.
21
Kapitola 3
Rekurentní vztahy. Konečné
součty.
Některé příklady nedokážeme vyřešit pomocí pravidla součtu a součinu –
nedokážeme určit vzorec, do něhož bychom dosadili, a místo toho určujeme
počet řešení na základě znalosti počtu řešení pro menší hodnoty parametru
nebo parametrů. S tímto postupem jsme se již seznámili při určování počtu
rozkladů čísel na sčítance. Ukážeme si ho také na následujícím příkladě:
Příklad 3.1 Kolika způsoby lze vyjít 10 schodů, děláme-li kroky po 1, 2,
nebo 3 schodech?
Řešení: Poslední krok můžeme udělat ze 7., 8. nebo 9. schodu; tj.
S10 = S9 + S8 + S7.
Obecně můžeme psát:
Sn = Sn−1 + Sn−2 + Sn−3.
Lehce ověříme, že
S1 = 1, S2 = 2, S3 = 4,
a podle vzorce tedy dopočítáme
S4 = 7(= 1 + 2 + 4)
a analogicky
S5 = 13, S6 = 24, S7 = 44, S8 = 81, S9 = 149,
a tedy
S10 = S9 + S8 + S7 = 149 + 81 + 44 = 274.
S rekurentní vztahy jste se mohli setkat na střední škole při studiu aritmetických
a geometrických posloupností. Shrňme si, co o těchto posloupnostech
víme.
22
Aritmetická posloupnost. Posloupnost daná rekurentním vztahem an =
an−1 + d (a prvním členem), kde d nazýváme diferencí. U této posloupnosti
umíme sečíst prvních n členů; vzorec:
Sn = (a1 + an)
n
2
=
n(2a1 + (n − 1)d)
2
Traduje se, že jednu z variant této úlohy vyřešil Karl Friedrich Gauss
(1777–1855), když jako školák dostal za úkol sečíst čísla od 1 do 50 (někdy
se tvrdí, že od 1 do 100). Všiml si, že součet 1 a 50 je stejný jako součet 2 a
49 a tak dále, tedy dvojnásobek hledaného součtu je 51 · 50.
Příklad 3.2 Určete součet:
S = 2n − 4 + 2n − 2 + 2n + · · · + 4n.
Řešení: Jedná se o aritmetickou posloupnost s diferencí 2; její první
člen je v našem částečném součtu 2n − 4, poslední 4n, diference 2. Abychom
mohli použít výše uvedený vzorec, potřebujeme znát počet sčítanců, který
však není n. Pro určení tohoto počtu můžeme použít úvahu: n sčítanců by
bylo v součtu
Sn = (2n − 4) + (2n − 2) + (2n) + · · · + (4n − 6),
čili scházejí tři sčítance, neboť
S − Sn = (4n − 4) + (4n − 2) + (4n)
Dosazením do výše uvedeného vzorce získáváme
S = (2n − 4 + 4n)
n + 3
2
= (n − 1)(n + 3).
Rozmyslete si, že výsledkem zlomku bude pro posloupnost s celočíselnými
členy vždy celé číslo.
Geometrická posloupnost. Posloupnost daná rekurentním vztahem an =
an−1q (a prvním členem), kde q nazýváme kvocientem. U této posloupnosti
umíme sečíst prvních n členů; vzorec:
Sn = a1
1 − qn
1 − q
= a1(1 + q + q2
+ · · · + qn−1
)
Je tedy vidět, že posloupnost je určena svým prvním členem a rekurentním
vztahem.
Obecně platí, že každá rekurentní posloupnost je určena rekurentním
vztahem a prvními několika členy — tolika, kolik jich explicitně nebo implicitně
vystupuje v rekurentním vztahu.
Fibonacciho posloupnost patří mezi zajímavé posloupnosti Platí v ní,
že každý další člen lze určit jako součet dvou členů předchozích. Zpr: f1 =
1, f2 = 1, fn = fn−1 + fn−2; první členy: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . ..
Z rekurentního vztahu umíme v některých případech určit i tzv. vzorec pro
n-tý člen, tj. návod, jak vypočítat fn jen pomocí n.
23