Kombinatorika – prehľad, vzorce a príklady

Kombinatorika – prehľad, vzorce a príklady

Kombinatorika je časť matematiky, ktorá sa zaoberá vytváraním rôznych skupín prvkov a určovaním počtu možností, akými možno tieto skupiny zostaviť.

Pri kombinatorických úlohách najčastejšie vyberáme k prvkov z n-prvkovej množiny. Pri rozhodovaní o správnom postupe sú dôležité najmä dve otázky:

• Záleží na poradí prvkov?
• Môžu sa prvky opakovať?

Základné princípy kombinatoriky

Pri riešení úloh rozlišujeme štyri základné možnosti:

• na poradí záleží a prvky sa nemôžu opakovať,
• na poradí záleží a prvky sa môžu opakovať,
• na poradí nezáleží a prvky sa nemôžu opakovať,
• na poradí nezáleží a prvky sa môžu opakovať.

Faktoriál

Faktoriál kladného celého čísla n je súčin všetkých kladných celých čísel menších alebo rovných číslu n. Označuje sa symbolom n!.

Platí:

• 0! = 1
• 1! = 1
• 2! = 2 · 1 = 2
• 3! = 3 · 2 · 1 = 6
• 4! = 4 · 3 · 2 · 1 = 24
• 5! = 5 · 4 · 3 · 2 · 1 = 120

Všeobecne:

n! = n · (n − 1) · (n − 2) · ... · 2 · 1

Príklad: Vypočítajme 6!.

6! = 6 · 5 · 4 · 3 · 2 · 1 = 720

Kombinačné číslo

Kombinačné číslo vyjadruje počet možností, ako možno vybrať k prvkov z n prvkov, ak nezáleží na poradí a jednotlivé prvky sa neopakujú.

Pre 0 ≤ k ≤ n platí:

C_k(n) = n! / [(n − k)! · k!]

Kombinačné číslo sa často zapisuje aj v tvare (n nad k).

Základné vlastnosti kombinačných čísel:

• C₀(n) = 1
• C₁(n) = n
• C_n(n) = 1
• C_k(n) = C_n−k(n)

Platí aj Pascalov vzťah:

C_k(n) + C_k+1(n) = C_k+1(n+1)

Príklad: Koľkými spôsobmi môžeme vybrať 3 žiakov z 10 žiakov?

C₃(10) = 10! / (7! · 3!) = (10 · 9 · 8) / (3 · 2 · 1) = 120

Pascalov trojuholník

Pascalov trojuholník je usporiadanie kombinačných čísel do trojuholníka. Na okrajoch každého riadku sa nachádza číslo 1 a každé vnútorné číslo vznikne ako súčet dvoch čísel, ktoré sa nachádzajú nad ním.

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

Čísla v jednotlivých riadkoch Pascalovho trojuholníka predstavujú hodnoty príslušných kombinačných čísel.

Variácie bez opakovania

Variácia k-tej triedy z n prvkov bez opakovania je usporiadaná k-tica vytvorená z n prvkov, pričom sa žiadny prvok neopakuje.

Pri variáciách bez opakovania:

• záleží na poradí,
• prvky sa nemôžu opakovať,
• vyberáme iba k prvkov z celkového počtu n prvkov.

Počet variácií bez opakovania vypočítame:

V_k(n) = n! / (n − k)!

Príklad: O prvé tri miesta v súťaži sa uchádza 8 súťažiacich. Koľko rôznych možností obsadenia prvého, druhého a tretieho miesta existuje?

V₃(8) = 8 · 7 · 6 = 336

Na poradí záleží, pretože umiestnenie A – B – C je iné ako B – A – C.

Variácie s opakovaním

Variácie k-tej triedy z n prvkov s opakovaním sú všetky možné usporiadané k-tice vytvorené z n prvkov, pričom sa jednotlivé prvky môžu opakovať.

Pri variáciách s opakovaním:

• záleží na poradí,
• prvky sa môžu opakovať.

Počet variácií s opakovaním vypočítame:

V'_k(n) = n^k

Príklad: Koľko rôznych štvorciferných kódov môžeme vytvoriť z číslic 0 až 9, ak sa číslice môžu opakovať?

Na každej zo štyroch pozícií máme 10 možností:

10 · 10 · 10 · 10 = 10⁴ = 10 000 možností

Permutácie bez opakovania

Permutácie bez opakovania sú špeciálnym prípadom variácií bez opakovania, pri ktorých používame všetkých n prvkov.

Ide teda o všetky možné usporiadania n rôznych prvkov.

Počet permutácií bez opakovania:

P(n) = n!

Príklad: Koľkými spôsobmi môžeme zoradiť 5 rôznych kníh na poličke?

P(5) = 5! = 5 · 4 · 3 · 2 · 1 = 120

Permutácie s opakovaním

Permutácie s opakovaním používame vtedy, keď usporadúvame všetky prvky, ale niektoré z nich sú rovnaké.

Ak máme spolu n prvkov, pričom:

• prvý druh prvku sa vyskytuje k₁-krát,
• druhý druh k₂-krát,
• ďalšie druhy k₃-krát atď.,

pričom platí:

k₁ + k₂ + ... + k_r = n,

potom počet rôznych permutácií vypočítame:

P = n! / (k₁! · k₂! · ... · k_r!)

Príklad: Koľko rôznych usporiadaní písmen môžeme vytvoriť zo slova MAMA?

Máme 4 písmená, pričom písmeno M sa nachádza dvakrát a písmeno A dvakrát.

P = 4! / (2! · 2!) = 24 / 4 = 6

Kombinácie bez opakovania

Kombinácia k-tej triedy z n prvkov bez opakovania je k-prvková podmnožina vytvorená z n prvkov.

Pri kombináciách bez opakovania:

• na poradí nezáleží,
• prvky sa nemôžu opakovať.

Počet kombinácií bez opakovania:

C_k(n) = n! / [k! · (n − k)!]

Príklad: Z 8 žiakov chceme vybrať trojčlennú skupinu. Koľko rôznych skupín môžeme vytvoriť?

C₃(8) = 8! / (3! · 5!) = (8 · 7 · 6) / (3 · 2 · 1) = 56

Poradie vybraných žiakov nie je dôležité. Skupina Adam – Peter – Jana je rovnaká skupina ako Jana – Adam – Peter.

Kombinácie s opakovaním

Kombinácie s opakovaním používame vtedy, keď vyberáme k prvkov z n druhov prvkov, pričom:

• na poradí nezáleží,
• prvky sa môžu opakovať.

Počet kombinácií s opakovaním vypočítame podľa vzorca:

C'_k(n) = C_k(n + k − 1) = (n + k − 1)! / [k! · (n − 1)!]

Príklad: Vyberáme 3 kopčeky zmrzliny z 5 príchutí. Jednu príchuť môžeme zvoliť aj viackrát a na poradí kopčekov nezáleží.

C'₃(5) = C₃(7) = 7! / (3! · 4!) = 35 možností

Ako rozpoznať správny typ kombinatorickej úlohy?

Pri riešení úlohy si postupne položte tieto otázky:

1. Záleží na poradí?
2. Môžu sa prvky opakovať?
3. Vyberáme iba časť prvkov alebo usporadúvame všetky prvky?

Kombinatorika v skratke

• Faktoriál: n! = n · (n − 1) · ... · 2 · 1
• Variácie bez opakovania: poradie je dôležité, prvky sa neopakujú.
• Variácie s opakovaním: poradie je dôležité, prvky sa môžu opakovať.
• Permutácie: usporadúvame všetky prvky.
• Kombinácie bez opakovania: poradie nie je dôležité, prvky sa neopakujú.
• Kombinácie s opakovaním: poradie nie je dôležité, prvky sa môžu opakovať.
• Pri každej úlohe je najdôležitejšie určiť, či záleží na poradí a či sa prvky môžu opakovať.