28.B Kombinatorika Kombinatorika je součástí finitní matematiky, která studuje konečné soubory (množiny a uspořádané k-tice, k∈N). Kombinatorická pravidla Kombinatorické pravidlo součinu Počet všech uspořádaných k-tic, jejichž první člen lze vybrat n1 způsoby, druhý člen po výběru prvního n2 způsoby, ....., k-tý člen po výběru všech předchozích nk způsoby, je roven číslu p, pro které platí : p = n1 . n2 . … . nk Kombinatorické pravidlo součtu Jsou-li A1 , A2, ....., An konečné množiny, které mají po řadě p1, p2, ....., pn prvků, přičemž každé dvě z nich jsou disjunktní, pak platí: A...AA n21 ∪∪∪ = p1 + 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 ∈N, k ≤ n). počet všech popsaných variací: V(k, n) = n.(n - 1).(n - 2). … . (n - k + 1) = )!( ! kn 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, n∈N). počet všech popsaných variací: V´(k, n) = nk 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(n) = V (n, n) = n.(n - 1).(n - 2). … .1 = n! Pozn.: n! …. čteme n faktoriál Permutace k prvků s opakováním z n prvků (k, n∈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 k1-krát, druhý prvek k2-krát, třetí prvek k3-krát, ......, n-tý prvek kn-krát. Přitom k = k1+k2+…+kn. počet všech popsaných permutací s opakováním: P´k1, k2, ..., kn (k) = !!...!. ! 21 nkkk 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 ∈N, k ≤ n). počet všech popsaných kombinací: K (k, n) = !)!( ! ! ),( kkn n k V nk − = =       k n č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í: K´(k, n) =       −+ k kn 1 Pravidla pro práci s kombinačními čísly a faktoriály: Faktoriál n! Pro každé n přirozené: n! = n.(n - 1).(n - 2). ... .2.1 Pro n = 0 definujeme: 0! = 1 Kombinační číslo       k n Pro všechna n, k celá nezáporná, k ≤ n : ( ) !!. ! kkn n k n − =      Některé základní vlastnosti kombinačních čísel: 1) n n =      1 1 0 =     n 1=      n n 1 0 0 =      2)       − =      kn n k n pro k ≤ n 3)       + + =      + +      1 1 1 k n k n k n pro k < n.