Matematika4. ročník SŠKombinatorika

Kombinatorika

Kombinatorika odpovedá na otázku „Koľkými spôsobmi…?“. Naučíš sa počítať možnosti bez toho, aby si ich musel všetky vypisovať — pomocou pravidla súčinu, faktoriálu, variácií, permutácií a kombinácií. Na konci uvidíš, ako kombinačné čísla tvoria Pascalov trojuholník a binomickú vetu.

Pravidlo súčinu a pravidlo súčtu

Kombinatorické pravidlo súčinu: ak prvý krok vieme urobiť n₁ spôsobmi a po každom z nich druhý krok n₂ spôsobmi, oba kroky za sebou vieme urobiť n₁ · n₂ spôsobmi. Pri viacerých krokoch násobíme ďalej: n₁ · n₂ · … · n_k.

Príklad: máš 2 tričká (T₁, T₂) a 3 nohavice (N₁, N₂, N₃). Každé tričko sa dá skombinovať s každými nohavicami, preto je oblečení 2 · 3 = 6. Všetky možnosti prehľadne ukáže strom možností:

Z každého trička vedú 3 vetvy, spolu 2 · 3 = 6 koncov stromu.

Kombinatorické pravidlo súčtu: ak vyberáme buď z jednej skupiny (n₁ možností), alebo z inej (n₂ možností) a skupiny nemajú spoločné prvky, možností je n₁ + n₂. Príklad: v jedálni si vezmeš buď jednu z 3 polievok, alebo jeden zo 4 šalátov (nie oboje) — možností je 3 + 4 = 7.

Stručne: kroky za sebou (a zároveň) → násobíme; možnosti buď–alebo → sčítame.

Faktoriál

Súčin všetkých prirodzených čísel od 1 po n označujeme n! (čítame „n faktoriál“):

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

Dohodou platí 0! = 1. Užitočný je vzťah n! = n · (n − 1)!, napríklad 6! = 6 · 5! = 6 · 120 = 720. Keby sme ho použili pre n = 1, dostaneme 1! = 1 · 0! — aj preto má zmysel dohoda 0! = 1.

n	0	1	2	3	4	5	6	7	8
n!	1	1	2	6	24	120	720	5 040	40 320

Faktoriál rastie veľmi rýchlo: 10! = 3 628 800. Pri výpočtoch preto faktoriály krátime, napr. 8! : 5! = 8 · 7 · 6 · 5! : 5! = 8 · 7 · 6 = 336.

Variácie

Variácia k-tej triedy z n prvkov (bez opakovania) je usporiadaná k-tica navzájom rôznych prvkov vybraných z n prvkov (k ≤ n). Usporiadaná znamená, že záleží na poradí: AB a BA sú dve rôzne variácie.

V(k, n) = n! : (n − k)! = n · (n − 1) · … · (n − k + 1)

Prečo: na 1. miesto vyberáme z n prvkov, na 2. miesto už len z n − 1 zvyšných, …, na k-te miesto z n − k + 1 prvkov. Podľa pravidla súčinu tieto počty vynásobíme — súčin má k činiteľov.

Príklad: dvojíc rôznych písmen z A, B, C, D, pri ktorých záleží na poradí, je V(2, 4) = 4 · 3 = 12: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

Variácie s opakovaním

Variácia k-tej triedy z n prvkov s opakovaním je usporiadaná k-tica, v ktorej sa prvky môžu opakovať. Na každé z k miest máme vždy všetkých n možností, preto

V′(k, n) = n^k

Tu môže byť k aj väčšie ako n. Príklad: trojmiestnych kódov z číslic 1 a 2 je V′(3, 2) = 2³ = 8: 111, 112, 121, 122, 211, 212, 221, 222.

Permutácie

Permutácia z n prvkov je každé usporiadanie všetkých n prvkov — je to variácia n-tej triedy z n prvkov. Keďže (n − n)! = 0! = 1, dostaneme

P(n) = n!

Príklad: 5 rôznych kníh môžeme na poličku zoradiť P(5) = 5! = 120 spôsobmi.

Permutácie s opakovaním

Ak sú medzi n prvkami rovnaké — prvý druh je tam k₁-krát, druhý k₂-krát, …, s-tý k_s-krát (k₁ + k₂ + … + k_s = n) — rôznych usporiadaní je

P′(k₁, k₂, …, k_s) = n! : k₁! · k₂! · … · k_s!

Delíme preto, lebo výmena rovnakých prvkov medzi sebou nové usporiadanie nevytvorí.

Príklad: slovo MATEMATIKA má 10 písmen — A je v ňom 3-krát, M 2-krát, T 2-krát a E, I, K po jednom. Rôznych „slov“ (anagramov), ktoré vzniknú preskladaním všetkých písmen, je

P′(3, 2, 2, 1, 1, 1) = 10! : 3! · 2! · 2! · 1! · 1! · 1! = 3 628 800 : 24 = 151 200

Kombinácie

Kombinácia k-tej triedy z n prvkov (bez opakovania) je neusporiadaná k-prvková skupina navzájom rôznych prvkov vybraných z n prvkov — teda k-prvková podmnožina. Na poradí nezáleží: {A, B} a {B, A} je tá istá kombinácia.

C(k, n) = n nad k = n! : k! · (n − k)!

Symbol n nad k čítame „n nad k“ a voláme ho kombinačné číslo. Súvis s variáciami: každú k-prvkovú skupinu vieme usporiadať k! spôsobmi, preto C(k, n) = V(k, n) : k!

Príklad: dve písmená z A, B, C, D (bez ohľadu na poradie) vyberieme 4 nad 2 = 4 · 3 : 2 · 1 = 6 spôsobmi: AB, AC, AD, BC, BD, CD. Je to polovica z 12 variácií, lebo tam bola každá dvojica dvakrát (AB aj BA).

Kombinácie s opakovaním (stručne)

Ak sa prvky v neusporiadanej skupine môžu opakovať, počet skupín je

C′(k, n) = n + k − 1 nad k

Príklad: 2 kopčeky zmrzliny z 3 druhov (vanilková V, čokoládová Č, jahodová J), pričom oba kopčeky môžu byť rovnaké: C′(2, 3) = 4 nad 2 = 6 — VV, VČ, VJ, ČČ, ČJ, JJ.

Ako sa rozhodnúť, ktorý vzorec použiť

Vyberáme všetky prvky a len ich zoraďujeme? → permutácie (ak sú medzi prvkami rovnaké, permutácie s opakovaním).
Záleží na poradí? Vymeň dva vybrané prvky. Ak vznikne iná možnosť (iný kód, iné poradie na stupni víťazov), záleží → variácie. Ak ide stále o tú istú skupinu (družstvo, trojica kariet), nezáleží → kombinácie.
Môže sa prvok vybrať viackrát? Číslice v PIN kóde áno, ľudia v družstve nie → s opakovaním / bez opakovania.

záleží na poradí
bez opakovania

Variácie

V(k, n) = n! : (n − k)!

Pre k = n: permutácie P(n) = n!. Napr. stupeň víťazov, poradie v rade, kód s rôznymi číslicami.

záleží na poradí
s opakovaním

Variácie s opakovaním

V′(k, n) = n^k

Napr. PIN kód, niekoľko hodov kockou za sebou.

nezáleží na poradí
bez opakovania

Kombinácie

C(k, n) = n nad k

Napr. družstvo, výber otázok na skúšku, ťah čísel v lotérii.

nezáleží na poradí
s opakovaním

Kombinácie s opakovaním

C′(k, n) = n + k − 1 nad k

Napr. kopčeky zmrzliny, nákup niekoľkých kusov z ponuky druhov.

Rozhodovanie si môžeš vyskúšať v interaktívnej časti „Ktorý vzorec?“ nižšie.

Kombinačné čísla a ich vlastnosti

Pre celé čísla 0 ≤ k ≤ n je n nad k = n! : k! · (n − k)!. Platí:

n nad 0 = n nad n = 1, n nad 1 = n
Symetria: n nad k = n nad n − k — vybrať k prvkov je to isté ako určiť n − k prvkov, ktoré nevyberieme. Napr. 10 nad 8 = 10 nad 2 = 10 · 9 : 2 · 1 = 45.
Súčet susedných čísel: n nad k + n nad k + 1 = n + 1 nad k + 1. Napr. 4 nad 1 + 4 nad 2 = 4 + 6 = 10 = 5 nad 2.

Pascalov trojuholník

Ak kombinačné čísla zapíšeme do riadkov — v riadku n sú n nad 0, n nad 1, …, n nad n — dostaneme Pascalov trojuholník:

na okrajoch sú jednotky, lebo n nad 0 = n nad n = 1;
každé číslo vo vnútri je súčtom dvoch čísel nad ním — to je práve vzťah pre súčet susedných kombinačných čísel;
každý riadok je súmerný podľa stredu (symetria) a súčet čísel v riadku n je 2ⁿ.

Riadky n = 0 až 6. Zvýraznené: 5 nad 2 + 5 nad 3 = 10 + 10 = 20 = 6 nad 3.

Binomická veta

Pre všetky reálne čísla a, b a každé prirodzené číslo n platí

(a + b)ⁿ = n nad 0aⁿ + n nad 1aⁿ⁻¹b + n nad 2aⁿ⁻²b² + … + n nad n − 1abⁿ⁻¹ + n nad nbⁿ

Rozvoj má n + 1 členov. Exponent pri a klesá od n po 0, pri b rastie od 0 po n, ich súčet je v každom člene n.
Koeficienty sú čísla z n-tého riadka Pascalovho trojuholníka.

Všeobecný člen: (k + 1)-vý člen rozvoja (k = 0, 1, …, n) je

T_k+1 = n nad k · a^n−k · b^k

Príklad: (a + b)³ = a³ + 3a²b + 3ab² + b³ (koeficienty 1, 3, 3, 1 z riadka n = 3). Pre (a − b)ⁿ dosadíme −b namiesto b a znamienka sa striedajú: (a − b)³ = a³ − 3a²b + 3ab² − b³.

Riešené príklady

Príklad 1 (PIN kódy): Koľko je štvormiestnych PIN kódov z číslic 0 až 9? Koľko z nich má všetky číslice rôzne?

Záleží na poradí (1234 a 4321 sú rôzne kódy) a číslice sa môžu opakovať → variácie s opakovaním, n = 10, k = 4.
Všetkých kódov: V′(4, 10) = 10⁴ = 10 000.
Všetky číslice rôzne → bez opakovania: V(4, 10) = 10 · 9 · 8 · 7 = 5 040.

Odpoveď: PIN kódov je 10 000, z toho 5 040 má všetky číslice rôzne.

Príklad 2 (stupeň víťazov): Vo finále behu je 8 pretekárov. Koľkými spôsobmi môžu byť obsadené 1., 2. a 3. miesto?

Vyberáme 3 pretekárov z 8, záleží na poradí (zlato nie je bronz) a nikto nemôže stáť na dvoch miestach → variácie bez opakovania.
V(3, 8) = 8! : 5! = 8 · 7 · 6 = 336

Odpoveď: stupeň víťazov môže byť obsadený 336 spôsobmi.

Príklad 3 (trojčlenné družstvo): Z 10 žiakov treba vybrať trojčlenné družstvo. Koľko je možností?

Na poradí nezáleží (družstvo Ana, Boris, Cyril je to isté ako Cyril, Ana, Boris) a žiak sa nemôže opakovať → kombinácie bez opakovania.
C(3, 10) = 10 nad 3 = 10! : 3! · 7!
= 10 · 9 · 8 : 3 · 2 · 1 = 720 : 6 = 120
Kontrola: usporiadaných trojíc je V(3, 10) = 720 a každé družstvo je medzi nimi 3! = 6-krát.

Odpoveď: družstvo sa dá vybrať 120 spôsobmi.

Príklad 4 (člen s x³): Nájdi člen s x³ v rozvoji (x + 2)⁵.

Je to binomická veta pre a = x, b = 2, n = 5.
Všeobecný člen: T_k+1 = 5 nad k · x^5−k · 2^k
Chceme x³, teda 5 − k = 3, odtiaľ k = 2 — je to tretí člen.
T₃ = 5 nad 2 · x³ · 2² = 10 · x³ · 4 = 40x³

Odpoveď: hľadaný člen je 40x³. Pre kontrolu celý rozvoj: (x + 2)⁵ = x⁵ + 10x⁴ + 40x³ + 80x² + 80x + 32.

Kombinatorika sa ti zíde aj pri výpočte pravdepodobnosti — počty možností z tejto kapitoly budeš dosadzovať do vzorcov. Pozri aj Pravdepodobnosť.

🧠 Zapamätaj si

Kroky za sebou → násobíme (pravidlo súčinu); buď–alebo → sčítame (pravidlo súčtu).
Záleží na poradí → variácie (všetky prvky → permutácie), nezáleží → kombinácie.
V(k, n) = n! : (n − k)!, V′(k, n) = n^k, P(n) = n!, C(k, n) = n nad k = n! : (k! · (n − k)!)
0! = 1, n nad k = n nad n − k, n nad k + n nad k + 1 = n + 1 nad k + 1.
Binomická veta: T_k+1 = n nad k · a^n−k · b^k; koeficienty sú n-tý riadok Pascalovho trojuholníka.

Vyskúšaj si to — ktorý vzorec?

Odpovedz na dve otázky a zadaj n (z koľkých prvkov vyberáš) a k (koľko prvkov vyberáš). Výpočet sa zobrazí hneď.

Záleží na poradí?

áno nie

Môžu sa prvky opakovať?

áno nie

n — počet prvkov

k — koľko vyberám

Vyskúšaj si to — Pascalov trojuholník a binomická veta

Klikni na číslo v trojuholníku (alebo doň prejdi klávesom Tab a pohybuj sa šípkami). Uvidíš, ktoré kombinačné číslo to je a z ktorých dvoch čísel nad ním vzniklo. Vybraný riadok n dáva koeficienty rozvoja (a + b)ⁿ.

Riadok n (0 až 15)

k (0 až n)

Pascalov trojuholník, riadky n = 0 až 15.

vybrané číslo n nad k
dve čísla nad ním (so spojnicami) — ich súčet je vybrané číslo
symetrické číslo n nad n − k s rovnakou hodnotou
riadok n — koeficienty rozvoja (a + b)ⁿ