Variace a kombinace
Jan Paseka
Masarykova univerzita Brno
Variace a kombinace ­ p.1/33

Abstrakt
Variace a kombinace ­ p.2/33

Abstrakt
V této kapitole shrneme základní poznatky
z kombinatoriky. Budeme podrobněji studovat
kombinatorické funkce ­
Variace a kombinace ­ p.2/33

Abstrakt
V této kapitole shrneme základní poznatky
z kombinatoriky. Budeme podrobněji studovat
kombinatorické funkce ­ faktoriál, kombinační
číslo.
Zmíníme se krátce o permutacích, variacích a
kombinacích k-té třídy v n-prvkové množině.
Variace a kombinace ­ p.2/33

Abstrakt
V této kapitole shrneme základní poznatky
z kombinatoriky. Budeme podrobněji studovat
kombinatorické funkce ­ faktoriál, kombinační
číslo.
Zmíníme se krátce o permutacích, variacích a
kombinacích k-té třídy v n-prvkové množině.
Přednášku ukončíme principem inkluze a
exkluze.
Variace a kombinace ­ p.2/33

Obsah přednášky
Faktoriál a kombinační číslo.
Binomická věta.
Polynomický koeficient.
Variace a kombinace ­ p.3/33

Obsah přednášky
Faktoriál a kombinační číslo.
Binomická věta.
Polynomický koeficient.
Variace k-té třídy v n-prvkové množině.
Kombinace k-té třídy v n-prvkové množině.
Permutace.
Princip inkluze a exkluze.
Variace a kombinace ­ p.3/33

Faktoriál
Výchozí kombinatorickou funkcí je faktoriál,
který je pro každé číslo n  N  {0} definován
předpisem:
Variace a kombinace ­ p.4/33

Faktoriál
Výchozí kombinatorickou funkcí je faktoriál,
který je pro každé číslo n  N  {0} definován
předpisem:
n! =
1 pro n = 0,
123 . . . (n-1)n pro n > 0.
Variace a kombinace ­ p.4/33

Příklad faktoriálu
Faktoriál přirozených čísel se velmi rychle
zvětšuje:
Variace a kombinace ­ p.5/33

Příklad faktoriálu
Faktoriál přirozených čísel se velmi rychle
zvětšuje:
0! = 1,
Variace a kombinace ­ p.5/33

Příklad faktoriálu
Faktoriál přirozených čísel se velmi rychle
zvětšuje:
0! = 1,
1! = 1, 2! = 2
Variace a kombinace ­ p.5/33

Příklad faktoriálu
Faktoriál přirozených čísel se velmi rychle
zvětšuje:
0! = 1,
1! = 1, 2! = 2
3! = 6, 4! = 24, 5! = 120
Variace a kombinace ­ p.5/33

Příklad faktoriálu
Faktoriál přirozených čísel se velmi rychle
zvětšuje:
0! = 1,
1! = 1, 2! = 2
3! = 6, 4! = 24, 5! = 120
6! = 720, 7! = 5040, 8! = 40320.
Variace a kombinace ­ p.5/33

Binomický koeficient
Další základní kombinatorickou funkcí je
binomický koeficient, nebo též kombinační
číslo, definované pro každá dvě čísla
n, k  N  {0} splňující k  n předpisem:
Variace a kombinace ­ p.6/33

Binomický koeficient
Další základní kombinatorickou funkcí je
binomický koeficient, nebo též kombinační
číslo, definované pro každá dvě čísla
n, k  N  {0} splňující k  n předpisem:
n
k
=
n!
k!(n - k)!
.
Variace a kombinace ­ p.6/33

Jednoduché vlastnosti
Variace a kombinace ­ p.7/33

Jednoduché vlastnosti
Pro libovolná n, k  N  {0} splňující k  n platí
n
0
= n
n
=
1 a
n
k
= n
n - k
.
Variace a kombinace ­ p.7/33

Jednoduché vlastnosti
Pro libovolná n, k  N  {0} splňující k  n platí
n
0
= n
n
=
1 a
n
k
= n
n - k
.
Tvrzení. Pro libovolná n, k  N splňující k < n
platí
n
- 1
k - 1
+ n
- 1
k
= n
k
.
Variace a kombinace ­ p.7/33

Pascalův trojúhelník
Variace a kombinace ­ p.8/33

Binomická věta
Věta. Pro libovolná x, y  R a pro libovolné
n  N platí
(x + y)n
=
nk
=0
n
k
x
k
yn-k
.
Variace a kombinace ­ p.9/33

Binomická věta
Věta. Pro libovolná x, y  R a pro libovolné
n  N platí
(x + y)n
=
nk
=0
n
k
x
k
yn-k
.
Důsledky. Pro libovolné n  N  {0} platí
nk
=0
n
k
=
2n
,
nk
=0
(-1)k
n
k
= 1
pro n = 0,
0 pro n > 0.
Variace a kombinace ­ p.9/33

Polynomický koeficient
Pro libovolná   N a n, k1, . . . , k  N  {0}
splňující n = k1 +    + kl je polynomický
koeficient definován předpisem:
Variace a kombinace ­ p.10/33

Polynomický koeficient
Pro libovolná   N a n, k1, . . . , k  N  {0}
splňující n = k1 +    + kl je polynomický
koeficient definován předpisem:
n
k1, . . . , k
=
n!
k1! . . . k!
.
Variace a kombinace ­ p.10/33

Rekurentní formule
Tvrzení. Pro libovolná   N, n  N a
k1, . . . , k  N  {0} splňující n = k1 +    + kl platí
Variace a kombinace ­ p.11/33

Rekurentní formule
Tvrzení. Pro libovolná   N, n  N a
k1, . . . , k  N  {0} splňující n = k1 +    + kl platí
n
k1, . . . , k
=
n - 1
k1, . . . , kj-1, kj - 1, kj+1, . . . , k
k
de suma je přes všechna j = 1, . . . ,  taková, že
kj  N.
Variace a kombinace ­ p.11/33

Aplikace rekurentní formule I
Věta. Pro libovolné   N, libovolná
x1, . . . , x  R a libovolné n  N platí
Variace a kombinace ­ p.12/33

Aplikace rekurentní formule I
Věta. Pro libovolné   N, libovolná
x1, . . . , x  R a libovolné n  N platí
(x1 +    + x)n
=
n
k1, . . . , k
x
k1
1 . . . xk
 ,
Variace a kombinace ­ p.12/33

Aplikace rekurentní formule I
Věta. Pro libovolné   N, libovolná
x1, . . . , x  R a libovolné n  N platí
(x1 +    + x)n
=
n
k1, . . . , k
x
k1
1 . . . xk
 ,
kde suma je přes všechny uspořádané -tice
(k1, . . . , k) čísel z N  {0} splňující
n = k1 +    + kl.
Variace a kombinace ­ p.12/33

Aplikace rekurentní formule II
Důsledek. Pro libovolné   N a libovolné
n  N  {0} platí
Variace a kombinace ­ p.13/33

Aplikace rekurentní formule II
Důsledek. Pro libovolné   N a libovolné
n  N  {0} platí
n
k1, . . . , k
=
n
,
kde suma je přes všechny uspořádané -tice
(k1, . . . , k) čísel z N  {0} splňující
n = k1 +    + kl.
Variace a kombinace ­ p.13/33

Variace k-té třídy I
Necht' n, k  N splňují k  n a necht' S je
n-prvková množina. Pak variace k-té třídy
v množině S jsou libovolné uspořádané k-tice
(a1, a2, . . . , ak)
vzájemně různých prvků a1, a2, . . . , ak  S.
Variace a kombinace ­ p.14/33

Variace k-té třídy I
Necht' n, k  N splňují k  n a necht' S je
n-prvková množina. Pak variace k-té třídy
v množině S jsou libovolné uspořádané k-tice
(a1, a2, . . . , ak)
vzájemně různých prvků a1, a2, . . . , ak  S.
Takovou uspořádanou k-tici můžeme vnímat také
jako prosté zobrazení množiny {1, . . . , k} do
množiny S, které každému číslu i  {1, . . . , k}
přiřazuje prvek ai  S.
Variace a kombinace ­ p.14/33

Variace k-té třídy II
Takové zobrazení je možno přehledně zapsat
například ve tvaru
1
2 . . . k
a1 a2 . . . ak
.
Variace a kombinace ­ p.15/33

Variace k-té třídy II
Takové zobrazení je možno přehledně zapsat
například ve tvaru
1
2 . . . k
a1 a2 . . . ak
.
Tato zobrazení je ovšem možno uvažovat i pro k =
0, v tom případě se jedná o jediné, totiž prázdné
zobrazení, a v takovém případě je možno připustit
i n = 0, tedy prázdnou množinu S.
Variace a kombinace ­ p.15/33

Počet variací k-té třídy
Tvrzení. Necht' n, k  N  {0} splňují k  n. Pak
počet všech variací k-té třídy v n-prvkové
množině S je roven číslu
n!
(n-k)! .
Variace a kombinace ­ p.16/33

Počet variací k-té třídy
Tvrzení. Necht' n, k  N  {0} splňují k  n. Pak
počet všech variací k-té třídy v n-prvkové
množině S je roven číslu
n!
(n-k)! .
Necht' n  N  {0}. Pak variace n-té třídy
v n-prvkové množině S se nazývají permutace
množiny S.
Variace a kombinace ­ p.16/33

Počet variací k-té třídy
Tvrzení. Necht' n, k  N  {0} splňují k  n. Pak
počet všech variací k-té třídy v n-prvkové
množině S je roven číslu
n!
(n-k)! .
Necht' n  N  {0}. Pak variace n-té třídy
v n-prvkové množině S se nazývají permutace
množiny S.
Důsledek. Necht' n  N  {0}. Pak počet všech
permutací n-prvkové množiny S je roven číslu n!.
Variace a kombinace ­ p.16/33

Variace k-té třídy s opakováním
Necht' dále n  N  {0} a k  N jsou libovolná
čísla a necht' S je n-prvková množina.
Variace a kombinace ­ p.17/33

Variace k-té třídy s opakováním
Necht' dále n  N  {0} a k  N jsou libovolná
čísla a necht' S je n-prvková množina.
Uvažujeme-li nyní zcela libovolné uspořádané
k-tice prvků množiny S, tedy libovolné prvky
kartézské mocniny Sk
, dostáváme variace k-té
třídy v množině S s opakováním.
Variace a kombinace ­ p.17/33

Variace k-té třídy s opakováním
Necht' dále n  N  {0} a k  N jsou libovolná
čísla a necht' S je n-prvková množina.
Uvažujeme-li nyní zcela libovolné uspořádané
k-tice prvků množiny S, tedy libovolné prvky
kartézské mocniny Sk
, dostáváme variace k-té
třídy v množině S s opakováním.
Takové uspořádané k-tice lze ovšem chápat jako
zobrazení množiny {1, . . . , k} do množiny S (pro
k = 0 jde o jediné a to prázdné zobrazení).
Variace a kombinace ­ p.17/33

Počet variací s opakováním
Tvrzení. Necht' n, k  N  {0}. Pak počet všech
variací k-té třídy v n-prvkové množině S
s opakováním je roven číslu nk
.
Variace a kombinace ­ p.18/33

Počet variací s opakováním
Tvrzení. Necht' n, k  N  {0}. Pak počet všech
variací k-té třídy v n-prvkové množině S
s opakováním je roven číslu nk
.
Poznámka. Aby toto tvrzení platilo i pro n = k =
0, je třeba klást 00
= 1.
Variace a kombinace ­ p.18/33

Počet variací s opakováním
Tvrzení. Necht' n, k  N  {0}. Pak počet všech
variací k-té třídy v n-prvkové množině S
s opakováním je roven číslu nk
.
Poznámka. Aby toto tvrzení platilo i pro n = k =
0, je třeba klást 00
= 1.
Variace a kombinace ­ p.18/33

Kombinace k-té třídy
Necht' nyní n, k  N  {0} splňují k  n a necht' S
je n-prvková množina.
Variace a kombinace ­ p.19/33

Kombinace k-té třídy
Necht' nyní n, k  N  {0} splňují k  n a necht' S
je n-prvková množina.
Pak kombinace k-té třídy v množině S jsou
libovolné k-prvkové podmnožiny T  S.
Variace a kombinace ­ p.19/33

Kombinace k-té třídy
Necht' nyní n, k  N  {0} splňují k  n a necht' S
je n-prvková množina.
Pak kombinace k-té třídy v množině S jsou
libovolné k-prvkové podmnožiny T  S.
Tyto k-prvkové podmnožiny lze jednoznačně po-
psat pomocí jejich tzv. charakteristických zob-
razení.
Variace a kombinace ­ p.19/33

Charakteristické zobrazení
Charakteristické zobrazení množiny T je
zobrazení f : S  {0, 1} splňující podmínku
f(s) = 1 právě tehdy, když s  T.
Variace a kombinace ­ p.20/33

Charakteristické zobrazení
Charakteristické zobrazení množiny T je
zobrazení f : S  {0, 1} splňující podmínku
f(s) = 1 právě tehdy, když s  T.
Tedy T je k-prvková právě tehdy, kdyža
S f(a) = k.
Variace a kombinace ­ p.20/33

Charakteristické zobrazení
Charakteristické zobrazení množiny T je
zobrazení f : S  {0, 1} splňující podmínku
f(s) = 1 právě tehdy, když s  T.
Tedy T je k-prvková právě tehdy, kdyža
S f(a) = k.
Tvrzení. Necht' n, k  N  {0} splňují k  n. Pak
počet všech kombinací k-té třídy v n-prvkové
množině S je roven číslu
n
k
=
n!
k!(n - k)!
.
Variace a kombinace ­ p.20/33

Kombinace s opakováním I
Necht' dále n, k  N  {0} jsou libovolná čísla a
necht' S je n-prvková množina.
Variace a kombinace ­ p.21/33

Kombinace s opakováním I
Necht' dále n, k  N  {0} jsou libovolná čísla a
necht' S je n-prvková množina.
Definujeme nyní kombinace k-té třídy
v množině S s opakováním jakožto libovolná
zobrazení g : S  N  {0} splňující podmínku
a
S
g(a) = k.
Variace a kombinace ­ p.21/33

Kombinace s opakováním I
Necht' dále n, k  N  {0} jsou libovolná čísla a
necht' S je n-prvková množina.
Definujeme nyní kombinace k-té třídy
v množině S s opakováním jakožto libovolná
zobrazení g : S  N  {0} splňující podmínku
a
S
g(a) = k.
Hledáme tedy počet řešení rovnice
a1 +    + an = k, ai  N  {0}.
Variace a kombinace ­ p.21/33

Kombinace s opakováním II
Máme tedy obecný popis souboru k prvků
vybraných z množiny S, v němž se některé prvky
mohou vyskytovat opakovaně. Zmíněný popis
spočívá v tom, že pro každý prvek a  S udává
číslo g(a) počet výskytů prvku a v daném
souboru, tedy v dané kombinaci s opakováním.
Variace a kombinace ­ p.22/33

Kombinace s opakováním II
Máme tedy obecný popis souboru k prvků
vybraných z množiny S, v němž se některé prvky
mohou vyskytovat opakovaně. Zmíněný popis
spočívá v tom, že pro každý prvek a  S udává
číslo g(a) počet výskytů prvku a v daném
souboru, tedy v dané kombinaci s opakováním.
Tvrzení. Necht' n  N a k  N  {0}. Pak počet
všech kombinací k-té třídy v n-prvkové množině
S s opakováním je roven číslu
n
+ k - 1
k
.
Variace a kombinace ­ p.22/33

Kombinace s opakováním III
Variace a kombinace ­ p.23/33

Permutace s opakováním I
Necht' n  N  {0},   N a necht' U je -prvková
množina. Vypišme ji ve tvaru U = {b1, b2, . . . , b}.
Variace a kombinace ­ p.24/33

Permutace s opakováním I
Necht' n  N  {0},   N a necht' U je -prvková
množina. Vypišme ji ve tvaru U = {b1, b2, . . . , b}.
Uvažme libovolnou kombinaci n-té třídy
v množině U s opakováním chápanou jako
soubor n prvků vybraných z množiny U, v němž
se některé prvky vyskytují opakovaně. Necht' k1
je počet výskytů prvku b1, necht' k2 je počet
výskytů prvku b2, atd., až k je počet výskytů
prvku b v tomto souboru. Pak tedy platí
k1 +    + k = n.
Variace a kombinace ­ p.24/33

Permutace s opakováním II
Kolika navzájem odlišitelnými způsoby lze takový
soubor vypsat ve tvaru posloupnosti prvků?
Variace a kombinace ­ p.25/33

Permutace s opakováním II
Kolika navzájem odlišitelnými způsoby lze takový
soubor vypsat ve tvaru posloupnosti prvků?
Takovým posloupnostem se pak říká
permutace s opakováním.
Variace a kombinace ­ p.25/33

Permutace s opakováním II
Kolika navzájem odlišitelnými způsoby lze takový
soubor vypsat ve tvaru posloupnosti prvků?
Takovým posloupnostem se pak říká
permutace s opakováním.
Lze je zapisovat jako uspořádané n-tice prvků
z U, v nichž se prvek b1 objevuje k1-krát, prvek b2
se objevuje k2-krát, atd., až prvek b se objevuje
k-krát.
Variace a kombinace ­ p.25/33

Počet permutací s opakováním
Tvrzení. Necht'   N, necht' U = {b1, . . . , b} je
-prvková množina a necht' n, k1, . . . , k  N  {0}
splňují k1 +    + k = n.
Variace a kombinace ­ p.26/33

Počet permutací s opakováním
Tvrzení. Necht'   N, necht' U = {b1, . . . , b} je
-prvková množina a necht' n, k1, . . . , k  N  {0}
splňují k1 +    + k = n.
Pak počet příslušných permutací s opakováním
v množině U je roven číslu
n
k1, . . . , k
=
n!
k1! . . . k!
.
Variace a kombinace ­ p.26/33

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Variace a kombinace ­ p.27/33

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Problém, který zkoumáme, spočívá v tom, jak určit, kolik je
objektů nemajících žádnou z uvedených vlastností.
Variace a kombinace ­ p.27/33

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Problém, který zkoumáme, spočívá v tom, jak určit, kolik je
objektů nemajících žádnou z uvedených vlastností.
Jestliže pro každé i  I označíme Ai množinu všech těch
objektů z Q, které mají vlastnost s indexem i, pak jde o to,
jak zjistit, kolik prvků má množina A(0) = Q -
i
I Ai.
Variace a kombinace ­ p.27/33

Vennův diagram
|ABC| = |A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|
Variace a kombinace ­ p.28/33

Vennův diagram
|Q| - |A  B  C| = |Q| - |A| - |B| - |C| + |A  B| + |A  C| + |B  C| - |A  B  C|
Variace a kombinace ­ p.29/33

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I.
Variace a kombinace ­ p.30/33

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I. Potom pro množinu
A(0) = Q -
i
I Ai platí
|A(0)| =
K
I
(-1)|K|

i
K
Ai
.
Variace a kombinace ­ p.30/33

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I. Potom pro množinu
A(0) = Q -
i
I Ai platí
|A(0)| =
K
I
(-1)|K|

i
K
Ai
.
Poznámka. Poněvadž Ai  Q pro i  I, klademe
i
 Ai = Q.
Variace a kombinace ­ p.30/33

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Variace a kombinace ­ p.31/33

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Q
-
i
I
Ai
=
|Q| -
i
I
A
i
+ {
i,j}I
i=j
A
i  Aj
-
{
i,j,k}I
i=j=k=i
A
i  Aj  Ak
+
   + (-1)|I|

i
I
Ai
.
Variace a kombinace ­ p.31/33

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Q
-
i
I
Ai
=
|Q| -
i
I
A
i
+ {
i,j}I
i=j
A
i  Aj
-
{
i,j,k}I
i=j=k=i
A
i  Aj  Ak
+
   + (-1)|I|

i
I
Ai
.
Tento vztah kvůli střídání znamének bývá právě označován
termínem princip inkluze a exkluze.
Variace a kombinace ­ p.31/33

Princip inkluze a exkluze - příklady
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Variace a kombinace ­ p.32/33

Princip inkluze a exkluze - příklady
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Ř ešení.
|A(0)| =
kj
=0
(-1)j

k
j

(k - j)n
.
Variace a kombinace ­ p.32/33

Princip inkluze a exkluze - příklady
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i.
Variace a kombinace ­ p.33/33

Princip inkluze a exkluze - příklady
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i.
Určete, kolik existuje permutací množiny {1, 2, . . . , n}, které
nemají ani jeden pevný bod.
Variace a kombinace ­ p.33/33

Princip inkluze a exkluze - příklady
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i.
Určete, kolik existuje permutací množiny {1, 2, . . . , n}, které
nemají ani jeden pevný bod.
Ř ešení.
|A(0)| = n!
1
-
1
1!
+
1
2!
-
1
3!
+    +
(-1)
!
+    +
(-1)n
n!

1
e
pro n  
.
Variace a kombinace ­ p.33/33