Stručný úvod do kombinatoriky
Stepán Krehlŕk
Ekonomicko správní fakulta Masarykova Universita
podzim 2018
Štěpán Křehlřk
□ iS1
Stručný úvod do kombinatoriky
Kombinační číslo
Studenti jazykového gymnázia mají na výběr ze čtyř jazyků (angličtiny, němčiny, francouštiny, ruštiny), během studia se budou věnovat právě dvěma jazykům. Kolika způsoby mohou studenti vybírat? Máme množinu J = {A, A/, F, /?}, potom cardJ = 4.
Student tedy může vybírat z:
{A, A/}, {A, F}, {A, /?}, {A/, F}, {A/, /?}, {F, /?}.
Kombinační číslo - obecně
Chceme-li vybrat /c-prvkové podmnožiny z n-prvkové množiny, pak toto můžeme vyjádřit kombinačním číslem
n
n\
n
k J k\{n-k)\ n(n - l)(n - 2)... (n - k)\     n(n - l)(n - 2)... (n - k - 1)
k J k\(n-k)\ k\
Štěpán Křehlík Stručný úvod do kombinatoriky
Vlastnosti kombinačního čísla
Pro /c, r? G N a n > k platí:
Štěpán Křehlík
Stručný úvod do kombinatoriky
Modifikujme příklad 1
Při studiu si student vybírá tři jazyky ze čtyř, kde jazyk na prvním místě je hlavní (Cl), jazyk na druhém místě je vedlejší (B2) a na třetím místě je doplňkový jazyk (A2). Vypište všechny možnosti. Pak je zřejmé, že výběr A, A/, R NENI stejný jako výběr A/, /?, A.
A,I\I,R   N,R,A R,A,N A,R,N N,A,R R,N,A
11       11 ii        ii ii
/\ F R
F r l\l řR    l\l,R,F R,F,I\I ~,R,I\I l\l,F,R R,I\I,F
Štěpán Křehlřk
Stručný úvod do kombinatoriky
Modifikujme příklad 1
Při studiu si student vybírá tři jazyky ze čtyř, kde jazyk na prvním místě je hlavní (Cl), jazyk na druhém místě je vedlejší (B2) a na třetím místě je doplňkový jazyk (A2). Vypište všechny možnosti. Pak je zřejmé, že výběr A, N, R NENI stejný jako výběr A/, R, A.
A,N,R N,R,A R.A.N A,R,N N AR R,N,A
A,N,F N,F,A F,A,N A,F,N N,A,F F,N,A
A,F,R F,R,A R,A,F A,R,F F,A,R R,F,A
F,N,R N,R,F R,F,N F,R,N N,F,R R,N,F
Štěpán Křehlřk Stručný úvod do kombinatoriky
Počet všech možností z příkladu výše můžeme vyjádřit jako:
6-1  ,  I = 24.
kde 6 = 3! = 3 • 2 • 1
Tento výpočet můžeme napsat obecně
k ) k\{n-k)\ (n-k)\
Štěpán Křehlík Stručný úvod do kombinatoriky
speciální případ
Na večírek jisté firmy je pro zaměstnance připravena barmanská ahow(B), raut (R), živá hudba (H), degustace vín (D). Žádné dvě akce neprobíhají zároveň. Kolika způsoby může akce na večírku uspořádat?
B,R,H,D   D,B,R,H   H,D,B,R   R,H,D,B B,D,R,H B,H,D,R   B,R,H,D   BfDfHfR ... R, D, H, B   ... ...
B,D,H,R
Počet všech možností můžeme vyjádřit obdobně jako v předchozím příkladu
24-1 4 | = 24 • 1, kde 24 = 4! = 4 • 3 • 2 • 1
Štěpán Křehlík Stručný úvod do kombinatoriky
Speciální případ
Tento výpočet lze zobecnit na pro n prvků a vyjádřit pak vzorcem
„i|  n)=n*__-_= ni
n ) n\ • (n - n)\
Štěpán Křehlřk Stručný úvod do kombinatoriky
Úlohy bez opakování
Postupně jak šla přednáška, tak jsem zavedli Kombinace
K(n, k) =
k\(n-k)\ o Variace
V{n,k) =
(n-k) • Permutace
P(n) = n\
Štěpán Křehlřk Stručný úvod do kombinatoriky
Úlohy s opakování
Pro celkovou ucelenost, zavedeme všechny předchozí možnosti s opakováním:
• Kombinace
• Variace
V'(n,k) = nk
• Permutace
P'(n\= ( (kl + k2 ■ ■ ■ kn)\ \
r^n)    \   k1\k2\...kn )
Štěpán Křehlřk Stručný úvod do kombinatoriky
Shrnutí semestru
Témata:
• Množiny a výroková logika,
• Úprava algebraických výrazů,
• Rovnice a nerovnice,
• Funkce
9 Lineární prostory
• Analytické geometrie v rovině
• Analytická geometrie v prostoru
• Posloupnosti
• Uvod do kombinatoriky
Štěpán Křehlík Stručný úvod do kombinatoriky
Závěr
Diskuze:
• Zamyšlení nad kurzem,
• Zhodnocení kurzu,
• Návrhy na zlepšení.
S1 ► < 1 ►     =        1 >OOnO
Štěpán Křehlík Stručný úvod do kombinatoriky