Kombinatorika – permutácie, kombinácie, kombinačné čísla a Pascalov trojuholník

Kombinatorika – permutácie, kombinácie, kombinačné čísla a Pascalov trojuholník

Kombinatorika je časť matematiky, ktorá sa zaoberá počítaním rôznych možností výberu a usporiadania prvkov konečnej množiny. Pri riešení kombinatorických úloh zisťujeme najmä to, či sa prvky môžu opakovať a či pri ich výbere záleží na poradí. Základom učiva sú permutácie, kombinácie a kombinačné čísla, pomocou ktorých dokážeme určiť počet možných usporiadaní alebo výberov bez toho, aby sme ich museli všetky jednotlivo vypisovať.

Základný princíp kombinatoriky

Predstavme si konečnú neprázdnu množinu, ktorá obsahuje n prvkov, pričom n ∈ N. Z tejto množiny vyberáme určité skupiny prvkov a skúmame, koľkými spôsobmi môžeme daný výber uskutočniť.

Pri každej kombinatorickej úlohe si treba položiť najmä tieto otázky:

• Môžu sa prvky opakovať?
• Záleží na poradí vybraných prvkov?
• Koľko prvkov vyberáme?

Ak na poradí záleží, vytvárame usporiadané k-tice alebo n-tice. Ak na poradí nezáleží, rozhodujúce je iba to, ktoré prvky boli vybrané.

Permutácie

Permutácie používame vtedy, keď chceme usporiadať všetky prvky danej množiny a na ich poradí záleží.

Základná otázka znie:

Koľkými spôsobmi možno zoradiť do radu všetky prvky neprázdnej konečnej n-prvkovej množiny?

Každé jedno možné zoradenie všetkých prvkov nazývame permutáciou alebo poradím prvkov danej množiny.

Permutácie môžeme chápať aj ako usporiadané n-tice vytvorené zo všetkých prvkov n-prvkovej množiny.

Počet permutácií

Počet všetkých permutácií n prvkov označujeme:

P(n)

Platí:

P(n) = n!

Symbol n! čítame „n faktoriál“.

Faktoriál

Faktoriál prirodzeného čísla n je súčin všetkých prirodzených čísel od n po 1:

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

Príklady:

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

Pre potreby kombinačných čísel sa definuje aj:

0! = 1

Príklad permutácie

Ak máme tri rôzne prvky A, B a C, môžeme ich usporiadať:

• ABC,
• ACB,
• BAC,
• BCA,
• CAB,
• CBA.

Počet možností je:

P(3) = 3! = 3 · 2 · 1 = 6

Pri permutáciách teda:

• používame všetky prvky,
• prvky sa neopakujú,
• na poradí záleží.

Kombinácie

Kombinácie používame vtedy, keď z n rôznych prvkov vyberáme iba určitý počet k prvkov a na poradí nezáleží.

Základnú otázku môžeme formulovať dvoma spôsobmi:

• Koľkými spôsobmi môžeme spomedzi n rôznych objektov vybrať k objektov, ak nezáleží na poradí?
• Koľko k-prvkových podmnožín má n-prvková množina?

Každý výber k prvkov z n prvkov nazývame k-prvkovou kombináciou z n prvkov.

Keďže pri kombináciách nezáleží na poradí, výbery môžeme chápať ako k-prvkové podmnožiny.

Počet kombinácií

Počet k-prvkových kombinácií z n prvkov môžeme označiť:

K(k, n)

Platí:

K(k, n) = n! / [k! · (n − k)!]

Tento výraz sa v kombinatorike vyskytuje veľmi často, preto sa zapisuje pomocou kombinačného čísla:

C(n, k) = n! / [k! · (n − k)!]

Kombinačné číslo sa číta:

„n nad k“

Príklad kombinácie

Máme 5 rôznych prvkov a chceme z nich vybrať 2 prvky. Počet možností je:

C(5, 2) = 5! / [2! · 3!]

Po úprave:

C(5, 2) = (5 · 4 · 3 · 2 · 1) / [(2 · 1) · (3 · 2 · 1)] = 10

Z piatich rôznych prvkov teda môžeme vybrať dvojicu 10 rôznymi spôsobmi.

Pri kombináciách platí:

• vyberáme iba k prvkov z n prvkov,
• prvky sa neopakujú,
• na poradí nezáleží.

Rozdiel medzi permutáciami a kombináciami

Vlastnosť	Permutácie	Kombinácie
Koľko prvkov používame?	Všetkých n prvkov	Vyberáme k prvkov z n prvkov
Záleží na poradí?	Áno	Nie
Opakujú sa prvky?	Nie	Nie
Základný vzorec	P(n) = n!	C(n, k) = n! / [k! · (n − k)!]

Kombinačné čísla

Kombinačné číslo vyjadruje počet možností, ako môžeme vybrať k prvkov z n rôznych prvkov bez ohľadu na ich poradie.

Platí:

C(n, k) = n! / [k! · (n − k)!]

kde:

• n je počet všetkých prvkov,
• k je počet vyberaných prvkov,
• platí 0 ≤ k ≤ n.

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

1. Výber žiadneho prvku

Pre každé prirodzené číslo n platí:

C(n, 0) = 1

Z n prvkov možno nevybrať žiadny prvok práve jedným spôsobom – vytvorením prázdnej množiny.

2. Výber jedného prvku

Platí:

C(n, 1) = n

Z n prvkov možno jeden prvok vybrať n rôznymi spôsobmi.

3. Výber všetkých prvkov

Platí:

C(n, n) = 1

Všetkých n prvkov môžeme vybrať práve jedným spôsobom.

4. Symetria kombinačných čísel

Pre k ≤ n platí:

C(n, k) = C(n, n − k)

Táto vlastnosť znamená, že vybrať k prvkov z n je z hľadiska počtu možností rovnaké ako určiť n − k prvkov, ktoré vo výbere nezostanú.

Napríklad:

C(5, 2) = C(5, 3) = 10

5. Pascalovo pravidlo

Pre k < n platí:

C(n, k) + C(n, k + 1) = C(n + 1, k + 1)

Táto vlastnosť umožňuje vypočítavať kombinačné čísla pomocou sčítania bez potreby počítať faktoriály.

Pascalov trojuholník

Na vlastnostiach kombinačných čísel je založený Pascalov trojuholník.

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 11 5 10 10 5 1

V Pascalovom trojuholníku platia dve základné pravidlá:

• všetky krajné čísla sú 1,
• každé vnútorné číslo vznikne ako súčet dvoch čísel, ktoré sa nachádzajú bezprostredne nad ním.

Napríklad číslo 6 vznikne:

3 + 3 = 6

Číslo 10 vznikne:

4 + 6 = 10

Súmernosť Pascalovho trojuholníka

Z vlastnosti:

C(n, k) = C(n, n − k)

vyplýva, že Pascalov trojuholník má zvislú os súmernosti.

Preto sú čísla v každom riadku symetrické. Napríklad:

1, 5, 10, 10, 5, 1

Súčet kombinačných čísel

Kombinačné čísla majú množstvo ďalších vlastností. Jedna z významných vlastností vyplýva z binomickej vety:

C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ

Súčet všetkých kombinačných čísel pre dané n je teda rovný mocnine čísla 2.

Príklad

Pre n = 4 dostaneme:

C(4, 0) + C(4, 1) + C(4, 2) + C(4, 3) + C(4, 4)

1 + 4 + 6 + 4 + 1 = 16

A zároveň:

2⁴ = 16

Binomický rozvoj

Kombinačné čísla sa uplatňujú aj pri rozvoji mocniny dvojčlena:

(a + b)ⁿ

Takýto rozvoj nazývame binomický rozvoj.

Binomický rozvoj výrazu:

(a + b)ⁿ

má vždy:

n + 1 členov.

Koeficienty jednotlivých členov binomického rozvoja tvoria práve príslušný riadok Pascalovho trojuholníka.

Príklad

Pre druhú mocninu:

(a + b)² = a² + 2ab + b²

Koeficienty sú:

1, 2, 1

Pre tretiu mocninu:

(a + b)³ = a³ + 3a²b + 3ab² + b³

Koeficienty sú:

1, 3, 3, 1

Tieto čísla nájdeme aj v Pascalovom trojuholníku.

Ako riešiť kombinatorické úlohy

1. Urči počet všetkých prvkov n.
2. Zisti, koľko prvkov vyberáme.
3. Rozhodni, či záleží na poradí.
4. Zisti, či sa prvky môžu opakovať.
5. Vyber správny kombinatorický postup alebo vzorec.
6. Dosad hodnoty a výsledok vypočítaj.
7. Výsledok interpretuj podľa zadania úlohy.

Najdôležitejšie vzorce

Pojem	Vzorec
Faktoriál	n! = n · (n − 1) · ... · 2 · 1
Nulový faktoriál	0! = 1
Permutácie	P(n) = n!
Kombinácie	C(n, k) = n! / [k! · (n − k)!]
Výber 0 prvkov	C(n, 0) = 1
Výber 1 prvku	C(n, 1) = n
Výber všetkých prvkov	C(n, n) = 1
Symetria	C(n, k) = C(n, n − k)
Súčet kombinačných čísel	C(n, 0) + C(n, 1) + ... + C(n, n) = 2n

Čo si zapamätať

• Kombinatorika skúma počet možností výberu alebo usporiadania prvkov.
• Pri riešení úlohy je dôležité určiť, či záleží na poradí a či sa prvky môžu opakovať.
• Permutácia predstavuje usporiadanie všetkých n prvkov.
• Počet permutácií n prvkov je n!.
• Faktoriál čísla n je súčin všetkých prirodzených čísel od 1 po n.
• Platí 0! = 1.
• Kombinácia predstavuje výber k prvkov z n prvkov, pričom na poradí nezáleží.
• Počet kombinácií vypočítame pomocou kombinačného čísla.
• Kombinačné čísla majú vlastnosť symetrie.
• Pascalov trojuholník umožňuje určovať kombinačné čísla pomocou sčítania.
• Každé vnútorné číslo Pascalovho trojuholníka je súčtom dvoch čísel nad ním.
• Súčet všetkých kombinačných čísel pre dané n je 2ⁿ.
• Kombinačné čísla sa používajú aj pri binomickom rozvoji.
• Rozvoj (a + b)ⁿ obsahuje n + 1 členov.