Cvičení z kombinatoriky Princip inkluze a exkluze
26. 11. 2018
MA2BP_CKOM
8. cvičení
26. 11. 2018
Princip inkluze a exkluze
MA2BP_CK0M
8. cvičení
26. 11. 2018
Princip inkluze a exkluze
Princip inkluze a exkluze
Princip inkluze a exkluze
Princip inkluze a exkluze
MA2BP_CK0M
8. cvičení
26. 11. 2018
Princip inkluze a exkluze
MA2BP_CK0M
8. cvičení
26. 11. 2018
Princip inkluze a exkluze
au eu c
a + b + c
+1/4 n e n c
dne
dne - en c
r Princip inkluze	a exkluze	1
Nechť M1,M2,.	.., Mk jsou konečné množiny. Pak platí:	
| Mi U M2 U • • •	UA4| = |Mi| + |M2| + --- + |A4|	
	-|Mi n M2\ - |Mi n M3|-----	■ IMfc.inM/,1
	+ Mi n M2 n M3| H-----h |Mfc_2	n Mfc_i n M/d
	+(-i)/(+1|MinM2n---nM/<|	
MA2BP_CKOM
8. cvičení
26. 11. 2018
Princip inkluze a exkluze
au eu c
a + b + c
+1/4 n e n c
dne
dne - en c
r Princip inkluze	a exkluze 1
Nechť M1,M2,.	.., Mk jsou konečné množiny. Pak platí:
| Mi U M2 U • • •	UA4| = |Mi| + |M2| + --- + |A4|
	-|Mi n M2| - \Mx n M3|-----|Mfc_i n Mk\
	+ Mi n M2 n M3| h-----h |Mfc_2 n Mfc_i n Mfc|
	+(-i)/(+1|MinM2n---nM/<|
	(-i)r+1 Myi n Mh n • • • n Mjr
	í/'lvJr}C{l,...,/c}
MA2BP_CKOM
8. cvičení
26. 11. 2018
MA2BP_CK0M
8. cvičení
26. 11. 2018
H Určete počet všech přesmyček daného slova takových, v nichž žádné stejné hlásky neleží vedle sebe. a) BONBON
MA2BP_CKOM
8. cvičení
26. 11. 2018
Určete počet všech přesmyček daného slova takových, v nichž žádné stejné hlásky neleží vedle sebe. a) BONBON
fí-3^+3f -3! =30
5!
4!
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady
Určete počet všech přesmyček daného slova takových, v nichž žádné stejné hlásky neleží vedle sebe.
a) BONBON [§ - 3§ + 3f - 3! = 30
b) KOMBINATORIKA
Určete počet čísel nesoudělných s číslem
a) 100
b) 350
Dokažte, že zpráva o jednom ročníku jisté ZŠ je chybná (vymyšlená?)
Do 6. ročníku chodí 45 žáků, z toho 30 chlapců. 30 žáků 6. ročníku má dobrý prospěch, z toho je 16 chlapců. Sportu se věnuje 28 žáků, z toho 18 chlapců, resp. 17 žáků, kteří mají dobrý prospěch. 15 chlapců, kteří sportují, má dobrý prospěch.
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady
Určete počet všech přesmyček daného slova takových, v nichž žádné stejné hlásky neleží vedle sebe.
a) BONBON [§ - 3§ + 3f - 3! = 30
b) KOMBINATORIKA
Určete počet čísel nesoudělných s číslem
a) 100
b) 350
Dokažte, že zpráva o jednom ročníku jisté ZŠ je chybná (vymyšlená?)
Do 6. ročníku chodí 45 žáků, z toho 30 chlapců. 30 žáků 6. ročníku má dobrý prospěch, z toho je 16 chlapců. Sportu se věnuje 28 žáků, z toho 18 chlapců, resp. 17 žáků, kteří mají dobrý prospěch. 15 chlapců, kteří sportují, má dobrý prospěch.
Nápověda: Zaměřte se na dívky. Kolik z nich má dobrý prospěch, kolik jich
sportuje a pro koli platí oboje? Jsou ty údaje v pořádku?
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady
Určete počet všech přesmyček daného slova takových, v nichž žádné stejné hlásky neleží vedle sebe.
a) BONBON r6!    o5! 1 o4!
b) KOMBINATORIKA
Určete počet čísel nesoudělných s číslem
13! 16
§ -3§+3f -3! =30
-4
12
+ 6^-4 8 -r u 4 2
10!
+ 9!
a) 100 [100 - 50 - 20 + 10]
b) 350 [350 - 175 - 70 - 50 + 35 + 25 + 10 - 5]
Dokažte, že zpráva o jednom ročníku jisté ZŠ je chybná (vymyšlená?):
Do 6. ročníku chodí 45 žáků, z toho 30 chlapců. 30 žáků 6. ročníku má dobrý prospěch, z toho je 16 chlapců. Sportu se věnuje 28 žáků, z toho 18 chlapců, resp. 17 žáků, kteří mají dobrý prospěch. 15 chlapců, kteří sportují, má dobrý prospěch. [dívky: |P+|S|-|PnS| =22??]
Nápověda: Zaměřte se na dívky. Kolik z nich má dobrý prospěch, kolik jich
sportuje a pro koli platí oboje? Jsou ty údaje v pořádku?
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady pro pokročilé
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady pro pokročilé
H Kolik tlumočníků je zaměstnáno v tlumočnické agentuře, víme-li, že 36 jich umí anglicky, 32 německy, 31 rusky, 30 francouzsky, 28 polsky, 26 španělsky, přičemž 53 z nich zná více než jeden z uvedených jazyků, 24 tlumočníků zná alespoň tři jazyky, 9 alespoň čtyři jazyky, 3 alespoň pět a 1 všech šest jazyků.
Kolika způsoby se může posadit v kině n manželských párů do poslední řady, kde je 2n míst, tak, aby žádný manželský pár neseděl
vedle sebe?
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady pro pokročilé
Kolik tlumočníků je zaměstnáno v tlumočnické agentuře, víme-li, že 36 jich umí anglicky, 32 německy, 31 rusky, 30 francouzsky, 28 polsky, 26 španělsky, přičemž 53 z nich zná více než jeden z uvedených jazyků, 24 tlumočníků zná alespoň tři jazyky, 9 alespoň čtyři jazyky, 3 alespoň pět a 1 všech šest jazyků.
Nápověda: Číselné údaje pro více jazyků nejsou součtem ale sjednocením. Kolik tlumočníků umí 5 jazyků (tj. jaké je sjednocení)? A jak vypadá součet, tj. číslo
>4n/vn/?nFnP| + |>4n/vn/?nFnS| + -- - + |A/n/?nFnPnS|I které se
použije ve vzorci pro inkluzi a exkluzi?
Kolika způsoby se může posadit v kině n manželských párů do poslední řady, kde je 2n míst, tak, aby žádný manželský pár neseděl
vedle sebe?
MA2BP_CKOM
8. cvičení
26. 11. 2018
Příklady pro pokročilé
H Kolik tlumočníků je zaměstnáno v tlumočnické agentuře, víme-li, že 36 jich umí anglicky, 32 německy, 31 rusky, 30 francouzsky, 28 polsky, 26 španělsky, přičemž 53 z nich zná více než jeden z uvedených jazyků, 24 tlumočníků zná alespoň tři jazyky, 9 alespoň čtyři jazyky, 3 alespoň pět a 1 všech šest jazyků. [93]
Nápověda: Číselné údaje pro více jazyků nejsou součtem ale sjednocením. Kolik tlumočníků umí 5 jazyků (tj. jaké je sjednocení)? A jak vypadá součet, tj. číslo
>4n/vn/?nFnP| + |>4n/vn/?nFnS| + -- - + |A/n/?nFnPnS|I které se
použije ve vzorci pro inkluzi a exkluzi?
Kolika způsoby se může posadit v kině n manželských párů do poslední řady, kde je 2n míst, tak, aby žádný manželský pár neseděl
vedle sebe?
MA2BP_CKOM
8. cvičení
26. 11. 2018