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 10. listopadu 2020
Helena Durnová
Pracovní verze
Obsah
I Teorie a příklady k procvičení 3
1 Kombinatorika 4
1.1 Základní kombinatorická pravidla . . . . . . . . . . . . . . . . 4
1.2 Faktoriály a kombinační čísla. Kombinatorické identity. . . . . 6
1.3 Aritmetický (Pascalův) trojúhelník . . . . . . . . . . . . . . . 8
1.4 Odvození vzorců: variace, permutace, kombinace (bez opakování).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Další úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Binomická věta . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Princip inkluze a exkluze. . . . . . . . . . . . . . . . . . . . . 13
1.8 Kompozice a rozklady. . . . . . . . . . . . . . . . . . . . . . . 19
1.9 Rozdělování do přihrádek. . . . . . . . . . . . . . . . . . . . . 20
1.10 Závěrem ke kombinatorice. . . . . . . . . . . . . . . . . . . . . 20
2 Rekurentní vztahy. Konečné součty. 22
2.1 Fibonacciho posloupnost. . . . . . . . . . . . . . . . . . . . . 23
2.2 Aritmetická posloupnost. . . . . . . . . . . . . . . . . . . . . . 23
2.3 Geometrická posloupnost. . . . . . . . . . . . . . . . . . . . . 24
1
Předmluva
Motto:
„Nevyučuj toho, kdo není připraven, aby byl vyučován.“
(Jan Ámos Komenský)
Matematika provází všechny děti po celou základní školní docházku od
70. let 20. století pod tímto jménem a pod jmény jinými (počty a měřictví,
či aritmetika a geometrie) ještě déle. Některé děti matematika prostě baví,
některé ne, ale přesto se jí musí učit všechny, stejně jako třeba češtině či
tělocviku.
V dnešní době se stalo módou chlubit se neznalostí matematiky, začněme
tedy kacířskou otázkou: co by se stalo, kdybychom děti, které matematické
poznatky přirozeně nechápou, povinnosti učit se matematiku zprostili? Odpovědět
na ni dokážeme teprve tehdy, když si uvědomíme, jaké učitele matematiky
jsme zažili a co od nás matematika vyžadovala.
Matematika se dá — s velkou nadsázkou — přirovnat ke sportu. Ani
ve sportu není talent všechno; skoro u každého je potřeba trénink. Tak je
tomu i s matematikou: během školní docházky se v matematice učíme postupům,
které nám procvičováním přejdou do krve. A tak si při při písemném
sčítání „sloupečků“ i v dospělosti pomáháme prsty. Pravda, příležitostí k využití
této dovednosti máme díky přítomnosti kalkulačky ve všudypřítomných
mobilních telefonech pramálo, ale když bylo vynalezeno auto, také jsme nepřestali
chodit pěšky a jezdit na kole.
Ve výuce matematiky se často klade důraz na správný zápis, na to, aby
byl výsledek dvakrát podtržen, na to, aby znaménko rovnosti bylo v úrovni
hlavní zlomkové čáry složeného zlomku. Všechny tyto věci se zvenčí mohou
zdát podružnými a nepodstatnými, ale právě tyto návyky nás učí odlišovat
podstatné od nepodstatného: vezměme si jako příklad pomocné výpočty
psané tužkou na okraj sešitu nebo dokonce na šmírák. Podobně důraz na
úpravu a dodržování pravidel není samoúčelný, nýbrž nám samotným později
ve složitějších výpočtech usnadní orientaci. Během hodin matematiky se
tak cvičíme v disciplíně, učíme se odlišovat podstatné od nepodstatného.
Na závěr dovolte několik vět k předkládanému textu. Je věnován některým
partiím z tzv. diskrétní matematiky, zde konkrétně z teorie čísel, kombinatoriky
a teorie grafů a je koncipován spíše jako vodítko k Vaší orientaci.
Všechny partie zde probírané byly již popsány v řadě knih, na něž se v textu
odkazujeme. Nepochopíte-li vše hned, nezoufejte a mějte na paměti, že vše
lze pochopit, vyvinete-li dostatečné úsilí. Matematika je také práce.
2
Část I
Teorie a příklady k procvičení
3
Kapitola 1
Kombinatorika
Řada knih zabývajících se kombinatorikou a jejími počátky poukazuje na zálibu
lidí v přeskupování a vytváření vzorů. Athanasius Kircher (1602–1680)
v ní viděl největší umění a svou knihu věnovanou kombinatorice nazval Ars
Magna Sciendum, Sive Combinatoria (Velké umění vědecké, neboli kombinatorika).
Pro malé počty prvků jsou kombinatorické úlohy jsou pro malé
počty prvků snadno řešitelné jednoduchým způsobem, totiž vypsáním všech
možností. Při větším počtu však působí spíše magickým dojmem, protože vypsat
všechny možnosti by trvalo příliš dlouho. Nicméně i když není v našich
silách všechny možnosti vypsat, stojí za to se o to pokusit. Začneme-li totiž
možnosti systematicky vypisovat, může nám to pomoci uvidět, jak budeme
počítat. Toto umění vidět může působit jako magie, ale dá se docela dobře
nacvičit, podobně jako si člověk zvykne číst rukopis jiného člověka nebo se
naučí rozeznat jednoho brouka od jiného.
1.1 Základní kombinatorická pravidla
Kombinatorické výpočty se zakládají na několika jednoduchých pravidlech.
Uveďme si je v moderním množinovém vyjádření, neboť je stručné a jedno-
značné.1
Věta 1.1 (Pravidlo součtu) Nechť A, B jsou množiny, A ∩ B = ∅. Pak
|A ∪ B| = |A| + |B|.
Příklad 1.2 Na otázku „kolika způsoby lze na šachovnici postavit pěšáka?“
lze odpovědět také rozdělením šachovnice na černá a bílá políčka. Pro variantu,
jak postavit pěšáka na bílé políčko, máme 32 možností; pro variantu,
kdy pěšák stojí na černém políčku, máme také 32 možností. Celkem je možností
64 = 32 + 32 (stojí-li pěšák na černém políčku, nestojí na bílém, a
naopak).
Věta 1.3 (Pravidlo součinu) Nechť A, B jsou neprázdné množiny. Pak
|A × B| = |A| · |B|.
Příklad 1.4 Ptáme-li se, kolika způsoby můžeme postavit na šachovnici černou
a bílou dámu tak, aby černá dáma stála na černém políčku a bílá na bílém,
odpověď určíme jako 32 · 32 = 1 024
1
O základech teorie množin se dozvíte v předmětu Základy matematiky.
4
V následujícím příkladu zkombinujeme pravidlo součtu a součinu:
Příklad 1.5 Kolik různých slov vznikne přeházením písmen slova KOLENA
tak, že se v nich samohlásky a souhlásky střídají a souhlásky jsou seřazeny
abecedně?
Pokud jsou souhlásky na sudých pozicích a samohlásky na lichých, můžeme
takto získat 6 slov (6 = 3! = 3 · 2 · 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].
Věta 1.6 (Přihrádkový, též zvaný Dirichletův, princip) Máme-li rozdělit
n + 1 předmětů do n přihrádek, pak při libovolném rozdělení budou v
alespoň jedné přihrádce alespoň dva předměty.
Příklad 1.7 V zásuvce je 12 párů červených a 12 párů modrých ponožek. Pokud
bereme ponožky z přihrádky poslepu, kolik ponožek musíme vzít, abychom
měli alespoň dvě ponožky téže barvy?
[Stačí vytáhnout tři ponožky.]
Všechny kombinatorické vzorce, které znáte ze střední školy, se dají odvodit
pomocí pravidla součtu a pravidla součinu. Přihrádkový (Dirichletův)
princip lze s výhodou použít při řešení některých příkladů.
Několik postřehů z historie kombinatoriky.
Kombinatorická pravidla jsou tak jednoduchá a samozřejmá, že těžko můžeme
očekávat, že bychom v historických pramenech našli zmínky o jejich
přesné formulaci.2 Zmínky o úlohách, které bychom dnes klasifikovali jako
kombinatorické, nacházíme především v indických a čínských textech. První
zmínky se však objevují již ve starověkém Egyptě, jak dokládá následující
úloha z Rhindova papyru s poměrně nejasným zadáním. Obsahuje sloupec
(viz též ??)
domy 7
kočky 49
myši 343
pšenice 2401
hekaty 6807
19607
Podobné počty najdeme i u Fibonnacciho (Liber abaci, 1202) ve formě
říkanky o sedmi starých ženách, které jdou do Říma:
Sedm starých žen šlo do Říma
každá nesla.....
Kolik....
Tyto počty se dochovaly i v dětské říkance „Když jsem šel do St. Ives“:
2
Biggs, N. 1979. ‘Roots of combinatorics’. Historia Mathematica 6:109-136.
5
Obrázek 1.1: Úloha o majetku z Rhindova papyru. Převzato z knihy Vymazalová,
Hana. Hieratické texty.
As I was going to St. Ives,
I met a man with seven wives.
Each wife had seven sacks.
In each sack there were seven cats.
Each cat had seven kits.
Kits, cats, sacks, and wives,
How many were going to St. Ives?
Mezi staré kombinatorické úlohy patří také počítání kombinací chutí nebo
možnosti otevřených a zavřených dveří ( Lílavátí). Kombinatorické výpočty
se obejvují také v úvahách o hazardních hrách (Huygens, Pascal, Fermat).
Kombinatorická pravidla tak, jak je známe dnes, sepsal Jacob Bernoulli ve
spise Umění odhadu (Ars conjectandi), vydané v roce 1713.
1.2 Faktoriály a kombinační čísla. Kombinatorické
identity.
V tomto oddíle stručně shrneme některé poznatky o faktoriálech a kombinačních
číslech tak, abychom s nimi v dalším mohli počítat bez dalšího
vysvětlování. Funkci faktoriál definujeme pouze pro přirozená čísla:
Definice 1.8 (Faktoriál přirozeného čísla) Pro libovolné n ∈ N klademe
n! = 1 · 2 · · · · · n (čteme: „n faktoriál“).
Dále klademe 0! = 1. Na okraj uveďme, že pojem faktoriálu lze rozšířit
i mimo obor přirozených čísel; podobně i níže zmíněný pojem kombinačního
čísla:
Definice 1.9 (Kombinační číslo) Pro libovolná k, n ∈ N definujeme kombinační
číslo takto:
n
k
=
n!
(n − k)!k!
(čteme: „n nad k“).
6
Tabulka hodnot faktoriálů:
0! 1
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
Počítání s faktoriály a kombinačními čísly: Jednodušší příklady lze
řešit rozepsáním faktoriálů. Kombinační číslo n
k představuje vlastně stručný
zápis zlomku n!
k!(n−k)! , platí tedy: n
k = n
n−k .
Kombinatorické identity: pro kombinační čísla platí řada tzv. kombinatorických
identit. Lze je dokázat jednak rozepsáním jednotlivých kombinačních
čísel, jednak kombinatorickou úvahou. Nejznámější z nich je tato:
n
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
7
(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
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.
1.3 Aritmetický (Pascalův) trojúhelník
Kombinační čísla nalezneme i v tzv. aritmetickém (Pascalově) trojúhelníku.
Každý jeho následující řádek vznikne tak, že do mezery mezi čísly předchozího
řádku vepíšeme součty dvou čísel nad tímto místem. Postup je zřejmý
z obrázku 1.2.
Obrázek 1.2: Aritmetický trojúhelník
V aritmetickém trojúhelníku lze nalézt řadu vztahů mezi kombinačními
čísly. Známá identita n
k + n
k+1 = n+1
k+ se používá přímo při vytváření
trojúhelníka. Z toho, jak schéma vzniklo, se také lehce dá odvodit, že součet
čísel v daném řádku je dvojnásobkem součtu čísel v řádku předchozím, neboť
každé číslo předchozího řádku vstupuje jako sčítanec do dvou čísel v řádku
daném. Vztah naznačený na obrázku 1.3 můžete zkusit odhalit sami.
8
Obrázek 1.3: Aritmetický trojúhelník: některé vztahy
Rovnice s kombinačními čísly
Cvičení 1.10 Najděte všechna x ∈ N, pro něž platí:
x − 1
x − 3
+
x − 2
x − 4
= 9
[5]
Cvičení 1.11 Určete, pro jaká m, n ∈ N platí:
n + 1
m + 1
=
n + 1
m
=
5
3
m + 1
m − 1
[n = 6, m = 3]
1.4 Odvození vzorců: variace, permutace, kombinace
(bez opakování).
V následujícím odvodíme pomocí pravidla součtu a součinu vzorce, které
znáte ze střední školy pod názvy variace, permutace a kombinace (bez opakování
a s opakováním). Postup vysvětlíme vždy na nějakém příkladu.
Variace bez opakování:
Příklad 1.12 Kolika způsoby lze na šachovnici rozestavit dámu, krále a věž?
Řešení: Opakovaným použitím pravidla součinu: 64 · 63 · 62 = 249 984
Obecně pokud vybíráme k předmětů z celkového počtu n předmětů, přičemž
k, n ∈ N a k ≤ n, možností je
n · (n − 1) · (n − 2) · · · · · (n − k + 1) =
n!
(n − k)!
9
Permutace bez opakování jsou zvláštním případem variací pro n = k.
Někdy mluvíme také o pořadí.
Příklad 1.13 Kolika způsoby lze sestavit devítimístné číslo z cifer 1 až 9
takové, že se v něm cifry neopakují?
Řešení: Opakovaným použitím pravidla součinu: 9 · 8 · · · · · 1 = 362 880
Obecně je počet pořadí n prvků roven n! (n ∈ N)
Příklad 1.14 Určete součet všech čtyřciferných čísel sestavených z cifer
1, 2, 3, 4.
Řešení: 640 + 6400 + 64000 + 640000 (číslice se mohou opakovat); 60 +
600 + 6000 + 60000 (číslice se nemohou opakovat).
Kombinace bez opakování: uvědomíme si, že množství stejně početných
variací a kombinací bez opakování prvků vybíraných ze stejně velké množiny
spolu úzce souvisí. V podstatě stačí počet variací vhodným číslem vydělit;
tímto vhodným číslem je faktoriál počtu vybíraných prvků; tj.
n!
(n − k)!k!
To je právě kombinační číslo:
n
k
=
n!
(n − k)!k!
Příklad 1.15 Kolika způsoby lze na šachovnici rozestavit tři bílé pěšáky?
Řešení: Vyjdeme z příkladu, kdy jsme na šachovnici měli postavit krále,
dámu a věž; možností bylo 64 · 63 · 62 = 249 984, Je zřejmé, že pokud na
tři daná políčka postavíme tři pěšáky, je možnost jediná (pěšáci jsou stejní),
zatímco krále, dámu a věž na tatáž políčka postavíme 3 · 2 · 1 = 6 způsoby.
U variant „s opakováním“ začneme s odvozováním vzorců také u variací.
Variace s opakováním
Příklad 1.16 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla.
Kolika způsoby si mohou objednat?
Řešení: Každý z hostů má 4 možnosti, tedy 4·4·4·4·4·4·4·4·4·4·4·4 = 412
možností.
Podobným způsobem lze odvodit počet podmnožin množiny A o n prv-
cích:
2|A|
= 2n
10
Permutace s opakováním tentokrát nejsou zvláštním případem variací.
Příklad 1.17 Kolika způsoby můžeme přeskládat písmena slova
(a) TATA
(b) POPOCATEPETL
Řešení:
(a) Vypíšeme možnosti dle abecedy: 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!
Každý z hostů má 4 možnosti, tedy 4 · 4 · 4 · 4 · 4 · 4 · 4 · 4 · 4 · 4 · 4 · 4 = 412
možností.
Kombinace s opakováním vyžadují zvláštní přístup. Začneme „kódovat“
a sestrojovat bijekce (vzájemně jednoznačná zobrazení) mezi objekty, jejichž
počet máme spočítat, a objekty, jejichž počet budeme umět spočítat.
Příklad 1.18 Do restaurace přijde 12 hostí. Na jídelním lístku jsou 4 jídla.
Kolika může být objednávek z hlediska kuchaře?
Řešení: Kuchaři je jedno, kdo si objednal které jídlo, zajímá ho pouze,
kolik má připravit porcí jídla č. 1 až 4. Možností je 12+4−1
4−1 = 12+4−1
12
Příklad 1.19 Kolika způsoby mohu vybrat deset mincí v hodnotě 5, 10 a 20
Kč? (Máme dostatečný počet mincí každé hodnoty.)
Řešení: Možností je 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
11
Vzoreček pro kombinace s opakováním, v němž přehodíme značení pro
druhy a počet prvků ,a tedy vybíráme n prvků k druhů, totiž vypadá dost
podobně:
Co(n, k) =
n + k − 1
k − 1
=
n + k − 1
n
1.5 Další úlohy
Nyní si ukážeme několik zajímavých příkladů, u kterých vhodně využijeme
výše uvedené vzorce a pravidla. Jsou převzaty z jiných učebnic, zejména z
výborných skript Antonína Vrby.
Příklad 1.20 Kolika způsoby lze přeskládat písmena slova LOKOMOTIVA
tak, aby žádná dvě „O“ nestála vedle sebe?
Řešení: Nejprve určíme, kolika způsoby lze přeskládat písmena L, K,
M, T, I, V, A. To lze provést 7! způsoby. Při libovolném z těchto rozložení
máme posloupnost sedmi písmen. Abychom vyhověli podmínkám, můžeme 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 .
Příklad 1.21 Krotitel má do arény přivést 4 tygry a 5 lvů tak, aby žádní
dva tygři nešli za sebou. Kolika způsoby to lze provést?
Řešení: Nejrpve určíme počet seřazení tygrů a lvů bez ohledu na to,
který tygr a který lev kde konkrétně bude. Symbolicky můžeme napsat, že
hledáme permutace pěti L a čtyř T takových, že žádná dvě T nenásledují
těsně za sebou; například LTLTLTLTL. Takových rozmístění je 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!
1.6 Binomická věta
Věta 1.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 1.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
12
(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
Cvičení a úkoly k zamyšlení: binomická věta
Cvičení 1.24 Dokažte binomickou větu metodou matematické indukce.
Cvičení 1.25 Určete, který sčítanec je v binomickém rozvoji
√
2 +
√
3
50
největší.
[ 50
22
√
2
22√
3
28
]
1.7 Princip inkluze a exkluze.
V některých kombinatorických úlohách se výsledku dobereme tak, že nejprve
vezmeme počet možností, který umíme dobře spočítat, i když víme, že
tak zahrneme možností příliš mnoho; poté počet upravíme například odečtením
nepříznivých případů nebo vydělením. Tyto postupy jsme už použili
pro odvození vzorců pro kombinace (podělením příslušného počtu variací),
pro permutace s opakováním (podělením celkového počtu permutací počty
permutací opakujících se písmen), a tedy i pro odvození vzorce pro výpočet
kombinací s opakováním. Ukažme si tuto strategii řešení na některých dalších
příkladech.
Příklad 1.26 úprava výsledku dělením - př. č. 1
Příklad 1.27 úprava výsledku dělením - př. č. 2
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.
13
Příklad 1.28 Je dán čtverec ABCD. Na každé jeho straně je vyznačeno
n(n ≥ 3) vnitřních bodů. Určete počet trojúhelníků s vrcholy v těchto bodech.
Řešení:
(a) Výběr stran s vrcholy trojúhelníka: 4
3 - každý vrchol na jiné straně;
dále dva vrcholy na jedné straně a jeden na jiné: 4 · 3, nakonec výběr
konkrétního vrcholu na dané straně.
(b) Od počtu všech trojic bodů ( 4n
3 ) odečteme trojice, které netvoří troúhelníky
— to jsou ty případy, kdy vybrané vrcholy leží na jedné straně
a těchto možností je 4 · n
3
Nejčastěji se metoda odečtení původně započítaných možností používá
pro takzvaný doplňkový jev:
Příklad 1.29 Určete, kolik je možností takových, kdy při hodu třemi kostkami
padne alespoň na jedné kostce hodnota 1.
Řešení:
(a) Vypočteme zvlášť případy, kdy padne na právě jedné kostce hodnota 1,
právě na dvou a právě na třech: 3 · 52 + 3 · 5 + 1 = 91
(b) Ode všech možností (63 = 216) odečteme případy, kdy nepadne ani
jednou hodnota 1. To bude ve 53 = 125 případech; čili hodnota 1 padne
alespoň na jedné kostce ve 216 − 125 = 91 případech.
V následujícím příkladu není metoda odečtení části výsledků sice elegantní,
ale vede ke správnému výsledku:
Příklad 1.30 Kolika způsoby může k chlapců a d dívek utvořit taneční páry??
Řešení:
(a) k · d způsoby (počet prvků kartézského součinu)
(b) Od počtu všech dvojic k+d
2 odečteme počet dvojic složených jen z chlapců
k
2 a počet dvojic složených jen z dívek d
2 , neboť ty netvoří taneční
páry:
(k + d)(k + d − 1
2
−
(k)(k − 1
2
−
(d)(d − 1
2
=
k2 + d2 + 2kd − k − d − k2 + k − d2 + d
2
= kd
Někdy však nedokážeme určit výsledek pouze pomocí jednoho nebo dvou
odečtení a musíme opět nějaké možnosti přičíst. Tomuto vědomému a systematickému
přičítání a odečítání se říká princip inkluze a exkluze.
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|;
14
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|
+|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
Příklad 1.31 V ústavu pracuje 67 osob, z nich 47 ovládá angličtinu, 35
němčinu a 23 oba jazyky. Kolik lidí neumí ani anglicky, ani německy?
Řešení: (a) pomocí Vennových diagramů
(b) 67 − 47 − 35 + 23 = 8
Příklad 1.32 V ústavu pracuje 67 osob, z nich 47 ovládá angličtinu, 35
němčinu, 29 francouzštinu; dále 23 hovoří anglicky i německy, 12 anglicky
a francouzsky a 11 německy a francouzsky, všemi třemi jazyky 5 osob. Kolik
lidí neumí ani anglicky, ani německy, ani francouzsky?
Řešení:(a) pomocí Vennových diagramů
(b) 67 − 47 − 35 − 20 + 23 + 12 + 11 − 5 = 6
Příklad 1.33 Na sídlišti žije 2229 rodin, z nichž každá má ledničku, auto
nebo chatu. Určete, kolik rodin má všechno, víte-li že 13371 má ledničku,
1049 má auto,1022 má chatu, 315 má ledničku i auto, 571 ledničku a chatu
a 430 má auto a chatu.
Řešení:(a) pomocí Vennových diagramů
(b) 103
Příklad 1.34 Tělovýchovná jednota má čtyři oddíly: atletiky, košíkové, odbíjené
a šachový.
A 26, K 17,
AK 7, AO 18, AŠ 2, KO 9, KŠ 0, OŠ 5
AKO 5, AKŠ 0, AOŠ 2, KOŠ 0
AKOŠ 0
Kolik členů má jednota?
Řešení: (a) pomocí Vennových diagramů není vhodné
(b) 85
15
Příklad 1.35 Kolik přirozených čísel menších než 105 obsahuje každou z
cifer 1, 3, 5, 7?
Řešení: Úlohu lze řešit dvěma způsoby:
(a) Rozdělím si všechna možná čísla na čtyřiciferná a pěticiferná.
(b) Pomocí principu inkluze a exkluze: všech pěticiferných čísel je 9 · 104,
od nich odečtu ty, které neobsahují 1 nebo 3 nebo 5 nebo 7, přičtu ty,
které neobsahují 1 a 3, 1 a 5, atd.
Musí to vyjít stejně, jinak je jeden z postupů špatně.
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+1
|M1 ∩ M2 ∩ · · · ∩ Mn|
Příklad 1.36 (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
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:
16
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.
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 Mi 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, při nichž využíváme principu inkluze a exkluze lze řešit
pomocí Vennových diagramů, avšak elegantněji je vyřešíme prostým sčítáním
a odčítáním příslušných zadaných hodnot. Z níže uvedených příkladů je
zřejmé, že potřebujeme zadat poměrně hodně údajů, které však nejsou zcela
nezávislé. Touto metodou se dají odhalit tzv. zfalšovaná hlášení, tj. případy,
kdy na první pohled není zřejmé, že čísla nemohou odpovídat pravdě.
Příklad 1.37 U velkého stolu se sešlo několik osob. Pouze jeden z nich neuměl
ani španělsky, ani italsky, ani francouzsky, z ostatních 8 umělo španělsky,
10 francouzsky, 8 italsky, 3 španělsky a italsky, 5 španělsky a francouzsky, 6
italsky a francouzsky a 2 španělsky, italsky a francouzsky. Určete, kolik lidí
sedělo u stolu.
Řešení: Úlohu lze řešit dvěma způsoby:
(a) Pomocí Vennových diagramů (viz obrázek 1.4).
(b) Všech osob bylo 1 + 8 + 10 + 8 − 3 − 5 − 6 + 2 = 16.
17
Obrázek 1.4: Vennův diagram pro úlohu fr. it. šp.
Obrázek 1.5: Venn. diagram pro úlohu o ledničkách, chatách a autech
Příklad 1.38 Ve sportovním klubu pěstují členové alepoň jeden z těchto čtyř
sportů: atletika (A), gymnastika (G), plavání (P) a lyžování (L).
Řešení:Zkusíme naznačit, co sezměnilo oproti předchozímu příkladu.
(a) Řešit úlohu pomocí Vennových diagramů není vhodné, neboť Vennův
digram pro 4 množiny je nepřehledný.
(b) c − s
Příklad 1.39 Na sídlišti je 2229 rodin, z nichž každá má ledničku, auto nebo
chatu. Určete, kolik rodin má všechno, víte-li, že 1371 rodin má ledničku,
1049 rodin má auto, 1022 má chatu, 315 rodin má ledničku a auto, 571 má
ledničku a chatu a 430 má auto a chatu.
Řešení: Úlohu lze řešit dvěma způsoby:
(a) Pomocí Vennových diagramů (viz obrázek 1.5); v tomto případě je to
dobré spíš pro kontrolu, ale ne pro počítání, neboť neznáme počet rodin,
které mají všechno.
(b) 2229 − 1371 − 1049 − 1022 + 315 + 571 + 430 = 103
Problém šatnářky (speciální princip inkluze a exkluze)
Příklad 1.40 Před koncertem si pánové odloží v šatně klobouky. Po koncertě
jim je šatnářka vydává poněkud chaoticky, neboť shodou okolností všichni
ztratili lístky. Kolika různými způsoby může šatnářka vátit rklobouky pánům
tak, aby žádný z nich neměl na hlavě svůj klobouk?
Řešení pro 4 osoby: 4! − 4 cot 3! + 4
2 · 2! − 4
3 1! + 4
4 · 0! = 9
Možnosti
18
pro 4 osoby - 9 možností
v tabulce všech 24, z toho 15 nevyhovuje
ABCD x BACD x CABD x DABC
ABDC x BADC CADB DACB x
ACBD x BCAD x CBAD x DBAC x
ACDB x BCDA CBDA x DBCA x
ADBC x BDAC CDAB DCAB
ADCB x BDCA x CDBA DCBA
pro 5 osob --- 44 možností
BADCE BADEC BAECD
BCAED BDAEC BDEAC
CABED CADEB
Pro 4 osoby je možností 9, pro 5 osob analogicky vypočteme 44.
pro 4 osoby - 9 možností
pro 5 osob - 44 možností
Kromě variací, permutací a kombinací známe další typické kombinatorické
kategorie. Z nich si nyní představíme dva typy, a to počítání, kolika
způsoby lze přirozené číslo zapsat ve tvaru sčítanců–přirozených čísel, a dále
počítání, kolika způsoby můžeme věci (rozlišitelné nebo nerozlišitelné) rozdělit
do přihrádek (rozlišitelných nebo nerozlišitelných)-
1.8 Kompozice a rozklady.
Definice 1.41 Rozkladem čísla n na k sčítanců rozumíme vyjádření čísla
n ∈ N pomocí k(∈ N), přičemž na pořadí sčítanců nezáleží. Počet rozkladů
čísla n na právě k sčítanců označíme p(n, k) (z anglického partition), rozklad
čísla n na libovolný počet sčítanců označíme p(n)
Je zřejmé, že k může nabývat hodnot od 1 do n. Dále platí (rozmyslete
si, že to opravdu platí):
p(n, 1) = 1
a také
p(n, n) = 1.
Zaveďme nyní funkci celá část z čísla x a její označení: [x]. Tato funkce
přiřadí každému číslu jeho celou část, tj. [2, 5] = 2 = [2] atp. Pak lze jednoduše
zapsat počet rozkladů čísla n na dva sčítance:
p(n, 2) = [
n
2
].
Přesvědčte se, že to to tvrzení skutečně platí. Důkaz l ze najít ve skriptech
E. Fuchse Diskrétní matematika pro učitele.
Určení počtu rozkladů je obecně úkol, který vyžaduje tzv. rekurentní
postup. To znamená, že abychom mohli spočítat počet rozkladů čísla 7 na
19
4 sčítance, musíme znáte rozklady menších čísel na menší nebo stejný počet
sčítanců. Konkrétně platíí:
p(n, k) = Σk
i=1p(n − k, i),
tedy např.
p(5, 3) = p(5−3, 1)+p(5−3, 2)+p(5−3, 3) = p(2, 1)+p(2, 2)+p(2, 3) = 1+1+0.
Zřejmě 5 = 3 + 1 = 1 = 2 + 2 + 1, zřejmě také p(2, 3) = 0, neboť nelze
rozložit číslo 2 na 3 přirozené sčítance.
Podívejme se znovu na vztah
p(n, k) = Σk
i=1p(n − k, i),
je to vlastně naopak konstruované než bychom čekali
od jednotlivých čísel (složek) rozkladu, který ještě neznáme,
ale předpokládáme, že budeme znát,
odečteme vždy jedničku --- tím dostaneme rozklad čísla o k menšího na
!nejvýše! k sčítanců
Definice 1.42 Kompozicí m čísla n z k sčítanců rozumíme vyjádření čísla
n ∈ N pomocí k(∈ N), přičemž záleží na pořadí sčítanců.
Výpočet počtu kompozic je ve srovnání s výpočtem počtu rozkladů poměrně
jednoduchý, neboť se jedná o analogii vzorce pro kombinace s opakováním:
máme-li rozdělit číslo n na právě k sčítanců, musí být každý ze
sčítanců alespoň 1, tedy počet kompozic je
n − k + k − 1
k − 1
=
n − k + k − 1
n − k
1.9 Rozdělování do přihrádek.
rozlišitelné a nerozlišitelné věci
roz. a neroz. přihrádky
tabulka
převedení jednotlivých problémů na
již známé kombinatorické kategorie
1.10 Závěrem ke kombinatorice.
Dosud představené kombinatorické úlohy jsou samozřejmě pouhou „ochutnávkou“.
Vůbec jsme se nedotkli problematiky magických či latinských čtverců, neformulovali
jsme Kirkmanův problém 15 dívek, nedefinovali jsme Bellova či
Stirlingova čísla. To je obsahem pokročilejších kurzů diskrétní matematiky.
Zde probíraná látka představuje — kromě procvičení logického uvažování
atp. — průpravu pro výukuteorii pravděpodobnosti.
20
Příklad 1.43 Dokažte, že mezi čtyřmi libovolně zvolenými přirozenými čísly
vždy najdeme dvě taková, že jejich součet nebo rozdíl je dělitelný pěti, nebo
dvě, jejichž rozdíl je dělitelný pěti.
Řešení: pomocí přihrádkového principu
Některé příkady nelzě řešit ani jedním z výše uedených způsobů, např.
tento:
Příklad 1.44 Kolika způsoby lze nalepit na dopis známky v hodnotě 18 Kč,
máme-li k dispozici známky v hodnotě 10 Kč, 4 Kč a 2 Kč (v libovolném
množství)? Řešení: vypíšeme...
je rozdíl mezi 2+2+10+4 a 10 + 4 + 2 + 2 atp.? —- ANO
21
Kapitola 2
Rekurentní vztahy. Konečné
součty.
Uveďme nejprve příklad:
Příklad 2.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.
Příklad 2.2 Na kolik oblastí rozdělí rovinu n přímek v obecné poloze?
Řešení: Nejprve si ujasněme, co je to obecná poloha: znamená to, že
žádné dvě přímky nejsou rovnoběžné a žádné tři se neprotínají v jednom
bodě.
Pak jedna přímka rozdělí rovinu na dvě části.
Druhá přímka přidá dvě další části — dvě přímky rozdělí rovinu na čtyři
části.
Třetí přímka protne každou z již nakreslených dvou, tedy přidá tři části
a dohromady bude rovina rozdělena na sedm částí.
Obecně:
pn+1 = pn + n + 1
22
Právě uvedenému vztahu říkáme rekurentní: abychom podle něj mohli postupovat,
musíme pro pn+1 znát pn, pro to zase pn−1, atd. V tomto případě
však můžeme i odvodit vzorec pro n-tý člen takové posloupnosti:
pn =
n2 + n + 2
2
Toto se dá dokázat — např. matematickou indukcí.
Faktoriál lye definovat rekurentně: (n + 1)! = n!(n + 1)
Obecně rekurentní vztah závislý na jednom předchozím členu: f(n+1) =
F(n, f(n))
2.1 Fibonacciho posloupnost.
Známá posloupnost je příkladem rekurentního vztahu, v němž pro každý
další člen potřebujeme znát dva členy předchozí:
Rekurentní vztahy. např. Fibonacciho posloupnost: 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.
2.2 Aritmetická posloupnost.
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 2.3 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
= (3n − 2)(n + 3).
23
Rozmyslete si, že výsledkem zlomku bude pro posloupnost s celočíselnými
členy vždy celé číslo.
2.3 Geometrická posloupnost.
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ů, a to podle vzorce
Sn = a1
1 − qn
1 − q
= a1(1 + q + q2
+ · · · + qn−1
)
Příklad 2.4 Sečtěte:
S = 1 + 2 + 4 + 8 + 16 + 32 + 64
Řešení: Jedná se o geometrickou posloupnost s kvocientem 2; její první
člen je 1, poslední (sedmý) 64. Podle vzorce
Sn = 1
1 − 27
1 − 2
= 1
−127
−1
= 127.
24