28 Kombinatorika - met. Stručný přehled teorie
Kombinatorika je součástí finitní matematiky, která studuje konečné soubory (množiny a uspořádané k-tice, ke N).
Kombinatorická pravidla
>  Kombinatorické pravidlo součinu
Počet všech uspořádaných k-tic, jejichž první člen lze vybrat ni způsoby, druhý člen po výběru prvního r\2 způsoby, ....., k-tý člen po výběru všech předchozích ni< způsoby, je roven číslu p, pro které platí:    p = ni. r\2.....ni<
>  Kombinatorické pravidlo součtu
Jsou-li Ai, A2,....., An konečné množiny, které mají po řadě pi, P2,....., pn prvků, přičemž každé dvě z nich jsou
disjunktní, pak platí:    \A1 U A2 U ... U An |= pi+ P2+ ... + Pn
Skupiny, v nichž záleží na pořadí prvků
Variace k-té třídy z n prvků bez opakování,
představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje nejvýše jednou (k, n e N, k < n).
Variace k-té třídy z n prvků s opakováním
představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje nejvýše
k-krát (k, ne N). počet všech popsaných variací:_V'(k,n)= n
Permutace z n prvků bez opakování = variace n-té třídy z n prvků bez opakování
- představuje každou uspořádanou n-tici sestavenou z těchto n prvků tak, že se v ní každý z nich vyskytuje právě jednou.
počet všech popsaných permutací:   P(„) = V („,n) = n.(n - l).(n - 2).....1 = n!
Pozn.: n! .... čteme n faktoriál
Permutace k prvků s opakováním z n prvků (k, n e N, k > n)
- představuje každou uspořádanou k-tici sestavenou z těchto n prvků tak, že se v ní každý prvek vyskytuje aspoň jednou.
Nechť se v uspořádané k-tici první prvek vyskytuje ki-krát, druhý prvek k2-krát, třetí prvek k3-krát,......, n-tý prvek
kn-krát. Přitom     k = ki+k2+...+kn.
počet všech popsaných permutací s opakováním:        P'u, a,.... kn (k) =-:-
Skupiny, v nichž nezáleží na pořadí prvků
Kombinace k-té třídy z n prvků bez opakování
■ je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý z nich vyskytuje nejvýše jednou (k, n e N, k < n).
počet všech popsaných kombinací:    K (k, n)
V,
(k,n)
k\ (n-k)\k\
čteme „n nad k"
Kombinace k-té třídy z n prvků s opakováním
-je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý z nich vyskytuje nejvýše k-krát.
počet všech popsaných kombinací:
ŕn + k-l\
(k, n):
Pravidla pro práci s kombinačními čísly a faktoriály:
Faktoriál n!
Pro každé n přirozené: n! = n.(n - l).(n - 2).....2.1
Pro n = 0 definujeme: 0! = 1
Kombinační číslo
Pro všechna n, k celá nezáporná, k < n :
Některé základní vlastnosti kombinačních čísel:
<)=»     (S) = i       C) = i       © = i
2»G) = (n-k) ProkSn
Met.:   Kombinatorika představuje relativně náročné téma, je však pro studenty zajímavá, hravá, pestrá. Učitel toho musí využít a dosáhnout u studentů co nejlepšího pochopení kombinatorických jevů a problémů a naučit je optimálním pohledům na kombinatorické úlohy a způsobům jejich řešení. Pokud by se mu to nepodařilo, měli by studenti potíže nejen s kombinatorikou, ale později i s mnoha dalšími oblastmi matematiky, do kterých ve větší či menší míře kombinatorika zasahuje (např. Pravděpodobnost,...).
Úvod kombinatoriky by měl rozhodně patřit kapitole o faktoriálech a kombinačních číslech I Studenti by měli být důkladně seznámeni s oběma těmito matematickými objekty, jejich nadefinováním, podmínkami jejich existence, pravidly pro počítání s nimi, měli by dokonale zvládat středoškolskou úroveň úprav výrazů, důkazů rovností i řešení rovnic a nerovnic s faktoriály a kombinačními čísly. Až budou řešit např. slovní kombinatorické úlohy, musí už mít faktoriály a kombinační čísla „v malíčku".
Řada kombinatorických úloh potřebuje k řešení znalost dvou základních pravidel, tedy kombinatorického pravidla součtu a kombinatorického pravidla součinu. Jakmile učitel s těmito pravidly studenty seznámí, měl by zařadit několik jednoduchých úloh, díky kterým studenti jejich podstatu lépe pochopí:
Př. V první restauraci nabízejí 3 druhy polévek, 8 druhů hlavních jídel a 4 druhy nápojů. Ve druhé restauraci mají jen 2 druhy polévek, ale 10 druhů hlavních jídel a 5 druhů nápojů. Kolika způsoby si host může vybrat oběd za předpokladu, že        a) zvolil první restauraci a bude jíst hlavní jídlo a nápoj?
b) zvolil první restauraci a bude jíst polévku, hlavní jídlo a nápoj?
c) bude vybírat restauraci a jíst polévku, hlavní jídlo a nápoj?
Řeš.:    a) hlavní jídlo ... 8 možností, nápoj... 4 možnosti_
počet všech možností (kombinatorické pravidlo součinu)... 8.4 = 32
b) polévka ... 3 možnosti, hlavní jídlo ... 8 možností, nápoj... 4 možnosti
počet všech možností (kombinatorické pravidlo součinu)... 3.8.4 = 96
c) první restaurace ... 3.8.4 = 96 možností druhá restaurace ... 2.10.5 = 100 možností
počet všech možností (kombinatorické pravidlo součtu)... 96 + 100 = 196_
Učitel musí k výuce přistupovat se stálým vědomím toho, že kombinatorika studuje dva typy konečných souborů, které jsou principiálně odlišné: • uspořádané k-tice, ke N, v nichž záleží na pořadí prvků,
• množiny, ve kterých na pořadí prvků nezáleží. Učitel musí především naučit studenty spolehlivě rozpoznat, s kterým z uvedených dvou typů souborů mají v zadané kombinatorické úloze pracovat. Zkušenosti ukazují, že to některým studentům dělá občas potíže.
Pozn.: Studentům je dobré poradit, aby si ze zadaných prvků vytvořili třeba trojici, pak v ní vyměnili pořadí prvků a promysleli si, zda jde o tutéž trojici nebo o trojici jinou: Př.l:    Nechť jsou Adam, Bedřich a Cyril tři studenti. Vytvořme z nich trojici pro
a) službu ve třídě: {A, B, C] = {B, C, A] = {A, C, B]
b) první tři místa v soutěži: [A, B, C] =é [B, C, A] =é [A, C, B] Př.2:    Tóny c, e, g zahrané
a) najednou (souzvuk) na klavír: {c, e, g] = {e, c, g] = {g, c, e]
b) postupně na trubku (jako souzvuk nelze): [c, e, g]    [e, c, g]    [g, c, e].
Vzorce, kterých je kombinatorika plná, si studenti jistě lépe zapamatují, když je jimi učitel nezasype, ale ukáže jim, jak se odvozují. Navíc, a to je jistě ještě mnohem důležitější, tak studenti uvidí další příklad toho, jak se matematika buduje a tvoří. Vzorce je třeba dokázat matematickou indukcí (některé - podle času).
1. Konečné soubory prvků, ve kterých záleží na pořadí prvků       - variace,
- variace s opakováním,
- permutace,
- permutace s opakováním
©I Variace k-té třídy z n prvků V7fc.tť)~^?| (prvky se nesmí opakovat) M = {1,2,3,4,5}
^(1,5)-?
^(2,5)-?
21 31 41
x
32
51
3	4	5
13	14	15
	24	25
X	34	35
43	X	45
53	54	X
^(1,5) = 5
V(2,s) = 5.4
^(3,5)—?       ►(231   234  235)       z každé uspořádané dvojice se vytvoří 3 uspořádané trojice 521    523 524) V(3i5) = 5.4.3
Zobecnění:    M = {1,2,3, ...,n]
V(2,n) = n. (n - 1)
V(3,n) = n.(n- 1). (n - 2)
(k,n)
n. (n - 1). (n - 2).....(n - k + 1)
n. (n - 1). (n - 2).....(n - /c + 1). (n - k).....3. 2.1
(n - k).....3.2.1
n! (n-k)
(Ž) Variace k-té třídy z n prvků s opakováním V^kn^ M = {1,2,3,4,5}
ľ(l.5)-?      1       2       3       4 5
(1,5)
ii
12     13     14 15 24 25
22
21
31       32     33 34 35
41       42     43 44 45
53 54 55
^0
^(2,5) = 5-5 = 5'
231	232	233	234	235
				
521	522	523	524	52Š
Zobecnění:	M = {1,2,3.....n]
V(X,n) = n V(2,n) = n2 V(?,n) = n3	
	
	
(p|Permutace z n prvků P(n)~? I   (prvky se nesmí opakovat)
Permutace z n prvků = variace k-té třídy z n prvků:
n!
P(n) - V(n,n)
_ ní _ ní _ | (n-n)! _ 0! _ 1 _
P(n) = n\
®
Permutace s opakováním P
(fc)"
M = {x1,x2,x3,x4,y1,y2,y3}
V této množině je ki = 4 prvků typu x a k2 = 3 prvků typu y, tedy celkem k = ki + k2 = 7 prvků.
Počet permutací (bez opakování) z těchto prvků je P(7) = 7!.
Jedna z těchto permutací je např.   [xlt x2,yi,x3,x4,y2,y3]- Kdybychom z této permutace tvořili další tak, že bychom všechny prvky typu y nechali na „svých" místech a „promíchávali" bychom pouze prvky typu x, získali bychom spolu s původní celkem 4! permutací. Ty všechny by ovšem splynuly v jedinou permutaci v okamžiku, kdy bychom přestali rozlišovat prvky typu x, tj. zavedli bychom xt, = x2 = x3 = x4 = x. Množina M by se změnila na M = {x, x, x, x, ylt y2, y3],
vybraná permutace by se změnila na [x, x, ylt x, x, y2, y3] a počet permutací (teď už s opakováním
71
prvku x) by se změnil na —.
Když přestaneme rozlišovat navíc i prvky typu y, bude M = {x, x, x, x, y, y, y] a počet permutací
71
s opakováním bude P43(7) =
Zobecnění
M = {x,..., x, y,..., y,......, z,..., z}        Přitom k1+k2 + —\- kn = k.
m-
Počet všech permutací s opakováním z prvků množiny M je Pki k2  fcn(fc) =
kilk2\.....knl
2. Konečné soubory prvků, ve kterých nezáleží na pořadí prvků   - kombinace,
- kombinace s opakováním
d)|Kombinace k-té třídy z n prvků K(kn^ — ?| (prvky se nesmí opakovat) M = {1,2,3,4,5}
51
Vytvořme variace 3. třídy z těchto pěti prvků. Je jich ^(3,5) =    _' .
Uvědomme si, že např. 123, 132, 213, 231, 312, 321 představuje 3! = 6 různých variací, ale jedinou kombinaci třetí třídy z pěti prvků. Podobně každých 3! variací vytvořených „promícháním" každé
5!
trojice prvků množiny M představuje jedinou kombinaci. Proto ^(3,5) = -^p =
(5-3)!.3! '
Zobecnění:
" = 11.2.3.....„} Uow-1^-7^5-0
Pozn
n.(n-l).....(n-k+l).(n-k).(n-k-l).....3.2.1      n.(n-l).....(n-/c+l).(n-fc).(n-fc-l).....3.2.1
(n-fc)l.fc!
(n-k).(n-k-l).....3.2.1M
(n-fc).(n-fc-l).....3.2.1,/c!
n.(n-l).....(n-fc+1)
... Skutečnost, že v čitateli i jmenovateli posledního zlomku je stejný počet činitelů, umožňuje velmi zjednodušit výpočet kombinačních čísel:
Např.: 1) (®) = — = 28    místo    (8>) = -^-
^ '  \2J      2.1 \2J      (8-2)!.2!      6!.2! 2.1
7.6!=H=28.
(|) Kombinace k-té třídy z n prvků s opakováním /f(fcn)—? I
Aby učitel dosáhl pochopení tvorby kombinací s opakováním u co největšího počtu studentů, měl by jim na začátku ukázat několik konkrétních příkladů:
Př.:   Nechť M = {1,2,3}. Vypište několik kombinací s opakováním páté třídy ze tří prvků množiny M a pokuste se zjistit, kolik takových kombinací existuje.
Řeš.: tf(5i3)-? {1,1,1,3,3}
{2, 2,2,2,2} {3, 3,2,1,1}
Jak zjistit počet všech možných kombinací s opakováním páté třídy ze tří prvků?
1. způsob .... Použít vzorec K(kn) = (n + ^~1^, tedy % 3) = (3 + j! ~ X) = Q = Q = ^ = 21
2. způsob .... Využít skutečnosti, že každou kombinaci s opakováním lze jednoduše převést na
permutaci s opakováním.
V případě tří prvků stačí vytvořit prostor s dvěma oddělovači (oddělovačů je vždy o jeden méně než prvků - viz obrázek). Pak zvolíme dva grafické znaky:
- první pro oddělovač .... např. |
- druhý jako značku registrující přítomnost prvku v „jeho" prostoru .... např. •
prvky 1	prvky 2	prvky 3	
• • •		• •	Zápis                         znamená {1,1,1,3,3}
			
• •	•	• •	Zápis    •• |*|**     znamená {1,1,2,3,3} = = {3, 3,2,1,1}
			
			
Je evidentní, že všechny kombinace s opakováním páté třídy ze tří prvků dokážeme zobrazit pomocí pouhých dvou druhů znaků:     pět modrých teček odpovídá pěti použitým prvkům (páté třídě),
dvě červené rysky představují dva potřebné oddělovače). Zároveň je jasné, že na pořadí těchto znaků záleží. Proto musíme pracovat s permutacemi
.      ,   , ' -   , .        7!        7.6.5! 7.6
s opakovaním: K(5 3) = P5>2(7) = — = ttt- = — =21
5!.2!
2.1
Tento druhý způsob řešení úlohy je jednoduchý, srozumitelný a logický, takže jej studenti mohou používat vždy, když hledají počet kombinací s opakováním, a to aniž by si museli pamatovat nepříjemný vzorec.
1Jdojít:
Navíc díky němu muže učitel studentům ukázat, jak lze ke vzorci K^kn^ = I
%3) - ^5,2 (7) - ^ - 7-^T ~ Ti ~ (?) ~ (D ~ C + 5 1
n + k k
Základní poznatky:
Poznámka: Ve výsledcích příkladů 2-6 této části uveďte také druh kombinatorické skupiny, kterou příklad procvičuje.
1)     MA 2017        Čtyřciferné přirozené číslo se má sestavit ze čtyř různých číslic. Na prvním místě má být číslice 2 a na místě desítek lichá číslice. (Daným podmínkám vyhovují např. čísla 2 430 a 2 793.) Kolik různých čísel je možné uvedeným způsobem sestavit?
a) 21 b)240 c) 280 d) 360 e) jiný počet [C]
2)    Je dána množina M = {1, 2, 3, 4, 5}.
a) Kolik trojciferných čísel, v nichž se neopakují cifry, lze vytvořit z jejich prvků?
[60, variace 3. třídy z 5 prvků bez opakování]
b) Kolik z nich je dělitelných pěti?
[12, variace bez opakování]
c) Kolik pěticiferných čísel bez opakování číslic lze vytvořit z prvků množiny M?
[120, permutace z 5 prvků (bez opakování) nebo variace 5. třídy z 5 prvků bez opakování]
Met.: Učitel by měl ukázat studentům dva způsoby řešení a nechat na studentech, který z nich si vyberou, až budou psát prověrku:
51
1. způsob: užitím vzorců      a) ^(3,5) =   _'   = 5.4.3 = 60 ;
b) Poslední cifra musí být 5, obsazujeme tedy jen první dvě
4'
pozice v čísle a nesmíme už použít 5 ... V(_2i4) = ^ = 12 ;
c) P(5) = 5! = 120.
2. způsob: užitím kombinatorického pravidla součinu:
a) Trojciferné číslo - znázornění pozic
r
Počet možností: 5.4.3 = 60
o c
o c
o c
Lfl
b) Trojciferné číslo - znázornění pozic
,-A-í>
T
T
T
Počet možností: 4.3.1
o c
o c
o c
c)
Pěticiferné číslo - znázornění pozic
T
T
T
Počet možností: 5.4.3.2.1 =
o c
o c
o c
o c
o c
Lfl
Pozn.: Zadání úlohy by měl učitel ještě zkomplikovat tím, že mezi prvky množiny M zařadí nulu. Pak může být např. M = {0,1,2, 3,4}. Předchozí výpočet je potom třeba doplnit o vyřazení všech trojic, které mají nulu na prvním místě. Úlohu lze nejprve využít jako prémiovou úlohu, jejíž správné řešení může učitel odměnit...
3) Řešte úlohu č. 2 pro případ, kdy se cifry mohou opakovat.
[a) 125, variace 3. třídy z 5 prvků s opakováním b) 25, variace s opakováním c) 3125, variace 5. třídy z 5 prvků s opakováním]
4) Kolik existuje osmiciferných čísel, ve kterých jsou 3 dvojky, 1 pětka a 4 šestky?
[280, 8 členné permutace s opakováním typu PV,4(8)]
5) Kolik existuje tříprvkových podmnožin množiny M?
[10, kombinace 3. třídy z 5 prvků bez opakování]
6) Student psal v matematice během pololetí 7 písemných prací a známky na konci pololetí uspořádal od nejlepších po nejhorší, např. 1,1, 2, 3, 3, 4, 5. Kolik různých výsledků mohl student získat?
[330, kombinace 7. třídy z 5 prvků s opakováním]
7)    Vyjádřete jedním kombinačním číslem:
					í3^		f4>		í5^		í6^				í1)
a)		+		b)		+		+		+		[a)		b)	
	v8,		v9,				,3,				v3y		v9y		
Typové příklady standardní náročnosti 8)
9)
MA 2016        Je dána rovnice s neznámou ne N: Jaké je řešení rovnice? A) 11  B) 10  C) 9    D) 8    E) jiné řešení
80! 80!_n-80! 9! +10!~ 10!
Kolik přímek je určeno 12 body, jestliže: a) žádné tři body neleží na přímce? b) čtyři z nich leží na přímce?
[A]
[66, 61]
10) S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete počet:
a) všech možných pořadí jejich vystoupení.
b) všech možných pořadí jejich vystoupení, v nichž vystupuje A po E.
c) všech možných pořadí jejich vystoupení, v nichž vystupuje A ihned po E
[720, 360, 120]
11) MA 2014        Trenér vybírá z 5 děvčat a 4 chlapců šestičlennou skupinu, v níž budou 3 dívky a 3 chlapci. Kolika způsoby lze šestičlennou skupinu za těchto podmínek sestavit?
A) 16 B)20 C)40 D) 180 E) jiným počtem
[C]
12) V sérii 12 výrobků jsou 3 vadné. Kolika způsoby lze z nich vybrat 6 výrobků, z nichž právě 2 jsou vadné? [378]
13) a) Z kolika prvků lze vytvořit 600 variací druhé třídy bez opakování? [25] b) Kolik prvků dává 55 kombinací 2. třídy bez opakování? [11]
14)   a) Upravte a určete podmínky pro n:
-2 -9       6 1
n
b) Řešte v Z:
(n + 3)\   (n + 2)\   (n + l)\
(fi + 6)! n (fi-4)! (n + 4)l (n-5)l
5n + W
(n + 2)\
, n g Z;n > -1 ]
[5]
15)   Řešte rovnici a nerovnici:
a)
fn-r		fn	-2\
	+		
[n-3j		[n	-4,
b)
fn^	+	fn -3>	+	fn	-6\
v2y		v 2 j		v	2 ,
<72
[a) {5}, b) {8, 9}]
Rozšiřující cvičení
16)   V novinovém stánku lze koupit 10 druhů pohledů, přičemž každý druh je k dispozici v 50 exemplářích. Určete, kolika způsoby lze zakoupit: a) 15 pohledů b) 51 pohledů c) 8 různých pohledů
[1 307 504; K'(51, 10) -10; 45]