Diskr´ etn´ı matematika
Petr Kov´aˇr petr.kovar@vsb.cz
Vysok´a ˇskola b´aˇnsk´a – Technick´a univerzita Ostrava
zimn´ı semestr 2021/2022
DiM 470-2301/01, 470-2301/03*, 470-2301/05
O tomto souboru
Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ucka pro pˇredn´aˇsej´ıc´ıho.
Radu d˚ˇ uleˇzit´ych informac´ı v souboru nenajdete, protoˇze pˇredn´aˇsej´ıc´ı je ˇr´ık´a, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇredn´aˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıran´a t´emata z pˇredn´aˇsek, kter´e zameˇskali.
Pro samostatn´e studium doporuˇcuji skripta:
M. Kubesa: Z´aklady diskr´etn´ı matematiky, v´yukov´y text P. Kov´aˇr: ´Uvod do teorie graf˚u, v´yukov´y text
Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici:
P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php
Pˇrehled pˇredn´aˇsky
Kapitola 4. Dalˇ s´ı poˇ cetn´ı postupy
princip inkluze a exkluze kombinatorick´e identity binomick´a vˇeta
nˇekolik d˚ukaz˚u
”poˇc´ıt´an´ım“
Opakov´an´ı
Zavedli jsme pojmy a symboly permutaceP(n)
kombinace bez opakov´an´ıC(n,k) i s opakov´an´ımC∗(n,k) variace (bez opakov´an´ı)V(n,k) i s opakov´an´ım V∗(n,k) Odvodili jsme vztahy pro poˇcet vˇsech v´ybˇer˚u zvolen´eho typu.
Avˇsak ne vˇsechny v´ybˇery m˚uˇzeme vyj´adˇrit pomoc´ı uveden´ych jednoduch´ych v´ybˇer˚u. Napˇr´ıklad
poˇcet prvk˚u ve sjednocen´ı mnoˇzin poˇcet bijekc´ı bez pevn´eho bodu
poˇcet rozklad˚u n prvkov´e mnoˇziny na pr´avˇe k disjunktn´ıch podmnoˇzin poˇcet rozklad˚u ˇc´ısla n na pr´avˇek sˇc´ıtanc˚u, pˇriˇcemˇz poˇrad´ı sˇc´ıtanc˚u nehraje roli
4.1. Princip inkluze a exkluze B´yv´a naz´yv´an tak´e
”princip zapojen´ı a vypojen´ı“, nebo
”zahrnut´ı a vylouˇcen´ı“.
Pro mal´an jej ˇcasto intuitivnˇe pouˇz´ıv´ame:
Vˇeta
Poˇcet prvk˚u ve sjednocen´ı dvou mnoˇzin je:
|A∪B|=|A|+|B| − |A∩B|.
A B
Poˇcet prvk˚u ve sjednocen´ı tˇr´ı je:
|A∪B∪C|=|A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C|+|A∩B∩C|.
A B
C
Obecn´y tvar principu inkluze a exkluze Poˇcet prvk˚u ve sjednocen´ın mnoˇzin je:
n
[
i=1
Ai
= X
J⊆{1,...,n}
J6=∅
(−1)|J|−1·
\
i∈J
Ai .
Abychom zjistili, kolik prvk˚u m´a sjednocen´ı seˇcteme velikosti jednotliv´ych mnoˇzin, odeˇcteme velikosti pr˚unik˚u vˇsech dvojic, pˇriˇcteme velikosti pr˚unik˚u vˇsech trojic, odeˇcteme velikosti pr˚unik˚u vˇsech ˇctveˇric, . . .
Velikost sjednocen´ı tˇr´ı mnoˇzin
Napˇr´ıklad pro n= 3 dost´av´ame
3
[
i=1
Ai
= X
J⊆{1,2,3}
J6=∅
(−1)|J|−1·
\
i∈J
Ai
=
= |A1|+|A2|+|A3| −
− |A1∩A2| − |A1∩A3| − |A2∩A3|+ +|A1∩A2∩A3|.
A1 A2
A3
Velikost sjednocen´ı ˇctyˇr mnoˇzin pro n= 4 dost´av´ame
4
[
i=1
Ai
= X
J⊆{1,2,3,4}
J6=∅
(−1)|J|−1·
\
i∈J
Ai
=
= |A1|+|A2|+|A3|+|A4| −
− |A1∩A2| − |A1∩A3| − |A2∩A3| − |A1∩A4| − |A2∩A4| − |A3∩A4|+ + |A1∩A2∩A3|+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4| −
− |A1∩A2∩A3∩A4|.
A1 A2
A3
Speci´aln´ı tvar principu inkluze a exkluze
Jednoduˇsˇs´ı tvar (s m´enˇe sˇc´ıtanci), maj´ı-li mnoˇziny a pr˚uniky i mnoˇzin stejn´e velikosti:
n
[
i=1
Ai
=
n
X
k=1
(−1)k−1· n
k
·
k
\
j=1
Aj
.
Abychom zjistili, kolik prvk˚u m´a sjednocen´ı
poˇcet jednoprvkov´ych pr˚unik˚u, tj. mnoˇzin samotn´ych ×|Ai|, odeˇcteme poˇcet dvouprvkov´ych pr˚unik˚u ×velikost pr˚unik˚u dvojic, pˇriˇcteme poˇcet tˇr´ıprvkov´ych pr˚unik˚u ×velikost pr˚unik˚u trojic, odeˇcteme poˇcet ˇctyˇrprvkov´ych pr˚unik˚u ×velikost pr˚unik˚u ˇctveˇric, . . .
Velikost sjednocen´ı tˇr´ı mnoˇzin maj´ı-li mnoˇziny i pr˚uniky mnoˇzin stejn´e velikosti
Pro n= 3 dost´av´ame
3
[
i=1
Ai
=
3
X
k=1
(−1)k−1· 3
k
·
k
\
j=1
Aj
=
= 3
1
· |A1| − 3
2
· |A1∩A2|+ 3
3
· |A1∩A2∩A3|.
A1 A2
A3
Velikost sjednocen´ı ˇctyˇr mnoˇzin maj´ı-li mnoˇziny i pr˚uniky mnoˇzin stejn´e velikosti
Pro n= 4 dost´av´ame
4
[
i=1
Ai
=
n
X
k=1
(−1)k−1· n
k
·
k
\
j=1
Aj
=
= 4
1
· |A1| − 4
2
· |A1∩A2|+ +
4 3
· |A1∩A2∩A3| − 4
4
|A1∩A2∩A3∩A4|.
A1 A2
A3
A4
Venn˚uv diagram pro sedm mnoˇzin – Adelaide
Pˇr´ıklad
Ve tˇr´ıdˇe je 25 ˇz´ak˚u. 17 z nich se uˇc´ı anglicky a 10 nˇemecky. 4 se uˇc´ı anglicky a nˇemecky, 4 anglicky a francouzsky, 2 nˇemecky a francouzsky a jeden studuje vˇsechny tˇri jazyky. Kolik student˚u se uˇc´ı jen francouzsky?
Mnoˇziny oznaˇc´ıme A,N aF. Zap´ıˇseme si
|A|= 17, |N|= 10, |A∩N|=|A∩F|= 4, |N∩F|= 2, |A∩N∩F|= 1 Z rovnice
|A∪N∪F|=|A|+|N|+|F| − |A∩N| − |N∩F| − |A∩F|+|A∩N∩F| dostaneme
|F|=|A∪N∪F| − |A| − |N|+|A∩N|+|N∩F|+|A∩F| − |A∩N∩F|
|F|= 25−17−10 + 4 + 4 + 2−1 = 7.
A N
F
Pˇr´ıklad (pokraˇcov´an´ı)
Ale nˇekteˇr´ı z tˇechto 7 student˚u se uˇc´ı i jin´e jazyky!
A N
F
Jen francouzsky
x =|F| − |A∩F| − |N∩F|+|A∩N∩F| x = 7−4−2 + 1 = 2 ˇz´aci.
Jen francouzsky se uˇc´ı 2 ˇz´aci.
Kombinatorick´e identity
Pro kombinaˇcn´ı ˇc´ısla plat´ı cel´a ˇrada zaj´ımav´ych vztah˚u. Zab´yv´a se jimi dokonce cel´a samostatn´a ˇc´ast diskr´etn´ı matematiky.
Lemma
Pro vˇsechna n≥0 plat´ı n
0
= n
n
= 1.
Tvrzen´ı, jejichˇz d˚ukaz spoˇc´ıv´a v dosazen´ı do definice povaˇzujeme za ”zˇrejm´a“ tvrzen´ı a d˚ukaz se neuv´ad´ı. Se spr´avn´ym zd˚uvodnˇen´ım je d˚ukaz tvrzen´ı zˇrejm´y:
Pod´ıvejme se na poˇcty pˇr´ısluˇsn´ych podmnoˇzin.
Dalˇs´ı kombinatorick´e identity
Lemma
Pro vˇsechna n≥k ≥0 plat´ı n
k
= n
n−k
. Pokud d˚ukaz vyˇzaduje nˇejak´y
”trik“, nebo neobvykl´e ´upravy (byt’ jen jednu jedinou ´upravu), je zvykem struˇcnˇe vysvˇetlit.
Pod´ıvejme se opˇet na poˇcty pˇr´ısluˇsn´ych podmnoˇzin.
Lemma
Pro vˇsechna n≥k ≥0 plat´ı n+ 1
k+ 1
= n
k
+ n
k+ 1
.
Pˇr´ım´y (dosazen´ım a ´upravou)
n k
+
n k+ 1
= n!
k!·(n−k)!+ n!
(k+ 1)!·(n−k−1)! =
= n!·(k+ 1) +n!·(n−k)
(k+ 1)!·(n−k)! = n!·(n+ 1) (k+ 1)!·(n−k)! =
= (n+ 1)!
(k+ 1)!·((n+ 1)−(k+ 1))! =
n+ 1 k+ 1
.
Kombinatorick´y d˚ukaz je n´azornˇejˇs´ı:
Rozeberme poˇcty (k+ 1)-prvkov´ych podmnoˇzin nˇejak´e (n+ 1)-prvkov´e
mnoˇziny.
V´yznam binomick´eho koeficientu
Uveden´e tˇri vztahy mohou slouˇzit jakoalternativn´ı definice kombinaˇcn´ıch ˇ
c´ısel. n
0
= n
n
= 1
n k
= n
n−k
n+ 1 k+ 1
= n
k
+ n
k+ 1
.
C´ıseln´ˇ e hodnoty binomick´ych koeficient˚u jsou urˇceny tˇemito rovnostmi nen´ı potˇreba poˇc´ıtat faktori´aly,
hodnoty lze (rekurentnˇe) dopoˇc´ıtat.
Pascal˚uv troj´uheln´ık
0 0
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
. . . .
Pascal˚uv troj´uheln´ık
0 0
= 1 1
0
= 1 1
1
= 1 2
0
= 1 2
1
2 2
= 1 3
0
= 1 3
1
3 2
3 3
= 1 4
0
= 1 4
1
4 2
4 3
4 4
= 1 5
0
= 1 5
1
5 2
5 3
5 4
5 5
= 1 . . . .
Pascal˚uv troj´uheln´ık
0 0
= 1 1
0
= 1 1
1
= 1 2
0
= 1 2
1
= 2 2
2
= 1 3
0
= 1 3
1
= 3 3
2
= 3 3
3
= 1 4
0
= 1 4
1
= 4 4
2
= 6 4
3
= 4 4
4
= 1 5
0
= 1 5
1
= 5 5
2
= 10 5
3
= 10 5
4
= 5 5
5
= 1 . . . . Krajn´ı ˇcleny maj´ı hodnoty 1.
Kaˇzd´y vnitˇrn´ı ˇclen je souˇctem dvou ˇclen˚u bezprostˇrednˇe nad n´ım.
Dalˇs´ı rovnosti
”Hokejkov´a“ rovnost
Pro vˇsechna pˇrirozen´a ˇc´ıslar,n, kden ≥r, plat´ıPn i=r
i r
= n+1r+1 . Elegantn´ı zd˚uvodnˇen´ı pomoc´ı Pascalova troj´uheln´ıka.
Dalˇs´ı rovnost
Pro vˇsechna pˇrirozen´a ˇc´ıslan plat´ıPn i=0
n i
2
= 2nn . Elegantn´ı kombinatorick´e zd˚uvodnˇen´ı.
Obecnˇejˇs´ı je
Vandermondova rovnost
Pro vˇsechna pˇrirozen´a ˇc´ıslar,m,n, kder ≤min{m,n}, plat´ı
r m n m+n
Binomick´a vˇeta
Binomick´a vˇeta Pro vˇsechna n>0 plat´ı
(1 +x)n= n
0
+ n
1
x+ n
2
x2+· · ·+ n
n−1
xn−1+ n
n
xn. D˚ukazTvrzen´ı je moˇzno dok´azat indukc´ı (skripta). Avˇsak moˇzn´y je i d˚ukaz jednoduchou ´uvahou (s vyuˇzit´ım lemmatu):
Algebraick´em rozvoji souˇcinu pouˇz´ıv´ame pravidlo
”vyn´asobit kaˇzd´y ˇclen s kaˇzd´ym“. Proto se v rozvoji vztahu (1 +x)(1 +x). . .(1 +x)
| {z }
n
ˇclenxk objev´ı tolikr´at, kolik je moˇznost´ı (neuspoˇr´adanˇe) vybratk z n ˇcinitel˚u – z´avorek. To je pr´avˇe nk
kr´at = poˇcetk prvkov´ych podmnoˇzin z nprvk˚u.
Kombinatorick´e identity odvozen´e z binomick´e vˇety
Binomick´a vˇeta Pro vˇsechna n>0 plat´ı
(1 +x)n= n
0
+ n
1
x+ n
2
x2+· · ·+ n
n−1
xn−1+ n
n
xn.
Z binomick´e vˇety pro pˇrirozen´an≥0 ihned plyne n
0
+ n
1
+ n
2
+ n
3
+· · ·+ n
n−1
+ n
n
= 2n. Vˇsech podmnoˇzin n-prvkov´e mnoˇziny je 2n.
Z binomick´e vˇety pro pˇrirozen´an>0 tak´e plyne n
− n
+ n
− n
+. . .−(−1)n−1
n
+ (−1)n n
= 0.
D˚ukazy
”metodou poˇc´ıt´an´ı moˇznost´ı“
Nˇekdy m´ame uk´azat existenci nˇejak´eho objektu nebo vlastnosti, aniˇz jsme schopni objekt zkonstruovat nebo jinak specifikovat. Takov´ym d˚ukaz˚um ˇr´ık´amenekonstruktivn´ı, nˇekdy tak´e existenˇcn´ı.
M´ısto abychom ˇreˇsen´ı
”zkonstruovali“, tak se n´am podaˇr´ı
”spoˇc´ıtat“, ˇze ˇreˇsen´ı mus´ı existovat.
Dirichlet˚uv princip (the pigeon-hole principle)
Rozm´ıst´ıme-li `+ 1 (nebo v´ıce) objekt˚u do` pˇrihr´adek, v nˇekter´e pˇrihr´adce mus´ı b´yt alespoˇn dva objekty.
D˚ukazy poˇc´ıt´an´ım moˇznost´ı
Existenci konkr´etn´ı moˇznosti (ze zn´am´e mnoˇziny) uk´aˇzeme, pokud poˇcet moˇznost´ı, kter´e nemohou nastat je menˇs´ı neˇz celkov´y poˇcet moˇznost´ı.
Pˇr´ıklad
Vid´ıme, jak do tunelu vjedou tˇri auta a jen dvˇe vid´ıme vyjet ven. To znamen´a, ˇze jedno auto v tunelu z˚ustalo (pˇrestoˇze ho nyn´ı nevid´ıme).
Pˇr´ıklad
8 kamar´ad˚u jelo na 9 dn´ı dovolen´e. Kaˇzd´y den nˇekter´a (jedna) trojice z nich ˇsla na v´ylet. Dokaˇzte, ˇze nˇekteˇr´ı dva z nich ani jednou nebyli spolu na v´yletˇe.
D˚ukaz rozeb´ır´an´ı moˇznost´ı by asi k niˇcemu nevedlo. . .
D˚ukaz poˇc´ıt´an´ım je vˇsak snadn´y: Jedna trojice m´a celkem 3 dvojice, proto po 9 dnech se mohlo vystˇr´ıdat nejv´yˇse r˚uzn´ych 9·3 dvojic, ale
9·3 = 27< 82
= 28, jedna dvojice n´am zde sch´az´ı.
Pˇr´ıklad
V ˇsupl´ıku je (poh´azeno) 30 p´ar˚u ˇcern´ych ponoˇzek, 10 p´ar˚u hnˇed´ych ponoˇzek a 3 p´ary b´ıl´ych ponoˇzek. Kolik mus´ıme potmˇe vyt´ahnout ponoˇzek, abychom mˇeli jistotu, ˇze m´ame alespoˇn jeden p´ar stejn´e barvy?
”Pˇrihr´adky“ Dirichletova principu budou odpov´ıdat tˇrem r˚uzn´ym barv´am.
Vyt´ahneme-li ˇctyˇri ponoˇzky (nerozliˇsujeme pravou a levou ponoˇzku), mus´ı b´yt alespoˇn dvˇe ponoˇzky stejn´e barvy.
Ot´azka
M´ame 4 pˇrirozen´a ˇc´ısla. Ukaˇzte, ˇze mezi nimi vˇzdy najdete dvˇe ˇc´ısla tak, aby jejich rozd´ıl dˇeliteln´y ˇc´ıslem 3.
Ot´azka
M´ame 3 pˇrirozen´a ˇc´ısla. Ukaˇzte, ˇze mezi nimi vˇzdy najdete dvˇe ˇc´ısla tak, aby jejich souˇcet byl dˇeliteln´y nˇejak´ym prvoˇc´ıslem.
Handshaking problem
V m´ıstnosti je n lid´ı, nˇekteˇr´ı si podali ruce. Ukaˇzte, ˇze alespoˇn dva lid´e podali ruku stejn´emu poˇctu lid´ı.
Pˇr´ıklad
M´ame 5 pˇrirozen´ych ˇc´ısel. Ukaˇzte, ˇze mezi nimi vˇzdy najdeme dvˇe ˇc´ısla tak, ˇze jejich souˇcet je dˇeliteln´y 9.
D˚ukaz (chybn´y!) Celkem m´ame 9 r˚uzn´ych zbytkov´ych tˇr´ıd po dˇelen´ı ˇc´ıslem 9. Z pˇeti ˇc´ısel m˚uˇzeme z´ıskat 10 r˚uzn´ych souˇct˚u. Jistˇe bude v kaˇzd´e zbytkov´e tˇr´ıdˇe alespoˇn jeden souˇcet, v nˇekter´e budou dokonce dva souˇcty.
Proto dvojice ˇc´ısel, jejichˇz souˇcet odpov´ıd´a zbytkov´e tˇr´ıdˇe 0, m´a souˇcet ˇ
c´ısel dˇeliteln´y dev´ıti.
Ot´azka
Co je ˇspatnˇe v uveden´em d˚ukazu pˇredchoz´ıho tvrzen´ı?
Zobecnˇen´y Dirichlet˚uv princip
Nen´ı obt´ıˇzn´e si rozmyslet, ˇze plat´ı jeˇstˇe obecnˇejˇs´ı tvrzen´ı.
Zobecnˇen´y Dirichlet˚uv princip
Rozm´ıst´ıme-li k`+ 1 (nebo v´ıce) objekt˚u do`pˇrihr´adek, v nˇekter´e pˇrihr´adce mus´ı b´yt alespoˇnk+ 1 objekt˚u.
Pˇr´ıklad
V krabici je dostateˇcn´e mnoˇzstv´ı kuliˇcek ˇctyˇr r˚uzn´ych barev. Kolik nejm´enˇe kuliˇcek mus´ıme vyt´ahnout, abychom mˇeli jistotu, ˇze m´ame alespoˇn 7 kuliˇcek stejn´e barvy?
Pˇrihr´adky odpov´ıdaj´ı barv´am, `= 4.
Kuliˇcky odpov´ıdaj´ı objekt˚um, k= 6.
Vyt´ahneme-li alespoˇn k`+ 1 = 6·4 + 1 = 25 kuliˇcek, tak alespoˇn 7 m´a stejnou barvu.
Dalˇs´ı poˇcetn´ı postupy
Ne vˇsechno lze spoˇc´ıtat pomoc´ı jednoduch´ych v´ybˇer˚u a principu inkluze a exkluze.
Rozdˇelen´ık r˚uzn´ych objekt˚u don nerozliˇsiteln´ych pˇrihr´adek tak, aby ˇ
z´adn´a nez˚ustala pr´azdn´a (Stirlingova ˇc´ısla prvn´ıho druhu),
rozdˇelen´ık r˚uzn´ych objekt˚u don r˚uzn´ych pˇrihr´adek tak, aby ˇz´adn´a nez˚ustala pr´azdn´a (Stirlingova ˇc´ısla druh´eho druhu),
rozdˇelen´ık nerozliˇsiteln´ych objekt˚u don nerozliˇsiteln´ych pˇrihr´adek tak, aby ˇz´adn´a nez˚ustala pr´azdn´a.
rozdˇelen´ık nerozliˇsiteln´ych objekt˚u don r˚uzn´ych pˇrihr´adek tak, aby ˇ
z´adn´a nez˚ustala pr´azdn´a.
Pro uveden´e v´ybˇery obecnˇeneexistuje uzavˇren´a formule. M˚uˇzeme poˇc´ıtat hodnoty rekurzivnˇe,
vyuˇz´ıt sumy s promˇenn´ymi parametry,
Pˇr´ıˇstˇe
Kapitola 5. Rekurentn´ı vztahy motivace
rekurentnˇe zadan´e posloupnosti metody ˇreˇsen´ı line´arn´ıch rekurenc´ı
