Permutácie

Autor: @hyperbola

Permutácia alebo poradie n prvkov je skupina n prvkov pri ktorej záleží na ich poradí. Permutovanie (obmieňanie) je proces tvorenia takejto skupiny. 
Pri permutáciach záleží na poradí. Permutácie poznáme bez opakovania a s opakovaním. Pokiaľ nie je špecifikované, či sú s opakovaním alebo bez opakovania, sú bez opakovania

Premutácie P bez opakovania

Permutácia n-prvkovej množiny M je ľubovoľná usporiadaná n-tica prvkov tejto množiny, v ktorej je každý prvok množiny M práve raz.
Pýta sa otázku “Koľkými spôsobmi môžeme zoradiť prvky konečnej množiny, ktorá obsahuje n-prvkov?” čo znamená, že máme množinu M z n rôznych prvkov, z ktorých tvoríme n-tice, pričom prvky v tejto množine sa nesmú opakovať.

Vzorec:
Počet všetkých permutácií n-prvkovej množiny môžeme vyjadriť vzťahom:
P(n) = n!

Počet všetkých možností zoradenia množiny M bez opakovania je n faktoriál

Legenda:
n je počet všetkých prvkov množiny, všetky naše možnosti

Pomôcka:
Či použiť varíacie bez opakovania si vieme overiť na základe týchto troch otázok:

  • Používame všetky prvky súšasne? Áno
  • Záleží na poradí prvkov? Áno
  • Môžu sa prvky v danej k-tici opakovať? Nie

Pokiaľ používame všetky prvky súčasne, záleží nám na poradí prvkov a prvky sa v danej k-tici nemôžu opakovať jedná sa o permutácie bez opakovania.

Pokiaľ máme množinu prvkov c; d; n; (počet prvkov je n = 3) počet všetkých spôsobov ich zoradenia môžeme vypočítať nasledovne:

P(3) = 3! = 6

Sú to:
cdn, cnd, ndc, ncd, dcn, dnc

Premutácie P´ s opakovaním

Pýta sa otázku “Koľkými spôsobmi môžeme usporiadať n prvkov z r druhov?”

V množine M je n prvkov, z ktorých tvoríme r druhov, teda prvky k1 sú rovnaké prvého druhu, prvky k2 sú rovnaké druhého druhu … prvky kr sú rovnaké r-tého druhu

Vzorec:
Počet všetkých spôsobov usporiadania n prvkov z r druhov môžeme vypočítať vzťahom:

Pomôcka:
Či použiť varíacie bez opakovania si vieme overiť na základe týchto troch otázok:

  • Používame všetky prvky súšasne? Áno
  • Záleží na poradí prvkov? Áno
  • Môžu sa prvky v danej k-tici opakovať? Áno

Pokiaľ používame všetky prvky súčasne, záleží nám na poradí prvkov a prvky sa v danej k-tici môžu opakovať jedná sa o permutácie s opakovaním.

Vysvetlime si to na príklade: Máme 4 písmená: ABBA, koľkými spôsobmi ich môžeme usporiadať?

Vidíme, že v slove ABBA máme 2x A, 2x B. Napíšme si ho ako AABB aby sme v tom mali poriadok.
Z toho vieme, že máme teda 2 druhy prvkov:

  1. AA; Počet prvkov 1. skupiny je k1 = 2
  2. BB; Počet prvkov 2. skupiny je k2 = 2

Počet miest v reťazci je n = 4 (reťazce majú dĺžku 4, pretože používame všetky prvky naraz) 

Počet možností usporiadania týchto prvkov vypočítame nasledovne:
Vieme, že sa jedná o permutácie s opakovaním, pretože používame všetky prvky súčasne (1. otázka), na poradí prvkov nám záleží (2. otázka) a prvky sa v danej k-tici môžu opakovať (3. otázka).

Použijeme nasledovný vzorec na vypočítanie permutácií s opakovaním, ktprý sme si už spomínali vyššie.

Môžeme si doplniť do vzorca údaje z nášho príkladu

Kalkulačku používať nemusíme. Rozložíme 4! na 4 * 3 * 2! a 2! vykrátime. Zostane nám

Výsledný počet spôsobov usporiadania prvkov ABBA je 6. Môžeme si to overiť:
ABBA, ABAB, AABB, BBAA, BABA, BAAB.

Výpočet nám sedí.

Riešené príklady

Riešený príklad 1

Koľko štvorciferných čísel vieme poskladať z cifier 2; 5; 0 také, aby boli deliteľné číslom 3. Začnime tým, že si

Riešenie

Z kapitoly Deliteľnosť prirodzených čísel vieme, že číslo je deliteľné číslom 3 len vtedy, ak je aj jeho ciferný súčet deliteľný číslom 3. 

1. Začnime tým, že si vypočítame, aké ciferné súčty potrebujeme. 2; 5; 0 ešte nie sú prvky, ktoré vložíme do permutácie. Stačí nam vypočítať kombinácie týchto cifier deliteľné číslom 3 do ciferného súčtu 20, pretože 20 je najviac, čo môžeme z týchto cifier vytvoriť v 4 cifrách (pretože najväčšie číslo máme 5 a máme 4 cifry => 4 * 5 = 20).

Najmenšie číslo deliteľné 3 je 3, však z čísel 2, 5 a 0 ciferný súčet 3 nevytvoríme. Môžeme ísť ďalej, toto budú kombinácie našich cifier:

6 => 2;2;2;0 - z cifier 2;2;2;0 môžeme vytvoriť čísla, ktoré sú 4-ciferné a majú súčet čísel 6, teda je deliteľný číslom 3 a sú to čísla, ktoré započítame do výsledku
9 => 5;2;2;0 - z cifier 5;2;2;0 môžeme vytvoriť čísla ktoré sú 4-ciferné a majú súčet čísel 9, teda je deliteľný číslom 3 a sú to čísla, ktoré započítame do výsledku
12 => 5;5;2;0 - znova to isté čo aj pri ciferných súčtoch vyššie, myslím, že už ste pochopili, čo ide
15 => 5;5;5;0 - ...
18 nevytvoríme
21 presahuje náš limit - 5;5;5;5 má ciferný súčet 20 a väčšie číslo už nevytvoríme

2. Keď už máme kombinácie cifier ktoré tvoria ciferné súčty deliteľné trojkou, vypočítajme koľko je možností usporiadať všetky tieto cifry aby tvorili 4 ciferné čísla. Na základe tohto vieme, že sa jedná o permutácie s opakovaním, pretože používame všetky prvky naraz (4 prvky, 4 cifry, 1. otázka), na ich poradí záleží (2. otázka) a môžu sa opakovať. 1. otázka sa nevzťahuje na cifry v zadaní - 2;5;0 ale na jednotlivé cifry pri ciferných súčtoch, ktoré sme si v 1. kroku vypisovali. preto vieme, že platí. Výsledok tohto príkladu bude súčet mnoho permutácií.   

Začnime číslom 6. Máme dva druhy prvkov:

  1. 2;2;2 => k1 = 3
  2. 0 => k2 = 1

Počet prvkov dokopy je n = 4, môžeme si to dosadiť do vzorca a výpočet bude vyzerať takto:

   

Výsledok by teda mal byť 4, avšak pozor! Keďže sú to len 4 možnosti, dôkladne si ich pozrime: Sú to čísla 2220; 2202, 2022 a 0222. Tu však nastáva problém, keďže číslo 0222, teda 222 je len trojciferné. Výsledný počet možností je teda len 3.

3. Skúsme teraz takto vypočítať čísla pre ciferný súčet 9, avšak pokúsme sa predísť tomu, aby medzi možnosťami boli aj trojciferné čísla (s 0 na začiatku). Tento výsledok dosiahneme tak, že si vypočítame všetky kombinácie týchto 4 cifier a odpočítame od nich všetky kombinácie, pri ktorých je cifra 0 na začiatku. Poďme počítať, máme nasledujúce typy prvkov, počet prvkov je n = 4:

  1. k1 = 1; iba prvok 5
  2. k2 = 2; prvky 2 a 2
  3. k3 = 1; prvok 0

    Toto platí pre všetky kombinácie, pre kombinácie kde bude na začiatku 0 máme nasledujúce špecifikácie, počet prvkov je n = 3:

  1. k4 = 1; iba prvok 5
  2. k5 = 2; prvky 2 a 2

    Prvok 0 tu už nebude, pretože vieme, že prvok 0 bude vždy na začiatku. V tomto prípade budú kombinácie vyzerať takto: 0XXX. Miesto X budú prvky a cifra 0 je vždy konštantná. Keďže 0 je iba jedna a to tá na prvom mieste, nemusíme s ňou ďalej počítať.

    Výpočet teda bude vyzerať takto:

   

Výsledný počet týchto 4-ciferných čísel s ciferným súčtom 9 je 9.

4. Pri cifernom súčte 12 pokračujeme rovnakým spôsobom:
V prvej permutácií máme nasledujúce prvky, n = 4:

  1. k1 = 1; iba prvok 2
  2. k2 = 2; prvky 5 a 5
  3. k3 = 1; prvok 0

    V druhej permutácií, ktorej reťazec vždy začína číslom 0 rovnako ako v kroku 4 máme nasledujúce prvky, n = 3:

  1. k4 = 1; iba prvok 2
  2. k5 = 2; prvky 5 a 5

Počet prvkov dokopy a v jednotlivých druhoch je rovnaký. To znamená, že výpočet bude presne rovnaký tiež, ako v 4. kroku:

5. Zostávajú nám už len 4-ciferné čísla s ciferným súčtom 15. Keďže počet prvkov a druhov je znovu rovnaký ako v pri číslach s ciferným súčtom 6, môžeme hneď konštatovať, že výsledok bude 3. Avšak aby sme si to precvičili, napíšem sem ucelený výpočet, keďže v 3. kroku sme to takto nepočítali.

Máme teda opäť dva druhy prvkov v prvej permutácií:

  1. k1 = 3; prvky 5; 5; 5
  2. k2 = 1; prvok 0

V druhej permutácií už bude iba 1 druh prvkov, a to:

  1. k3 = 3; prvky 5;5;5

    Pretože 0 je vždy na prvom mieste, je tam vždy a nepermutujeme ju v tejto permutácií.

    Výpočet bude vyzerať takto:

   

6. Na záver si zhrňme, čo nám vyšlo

6 => 2;2;2;0 - Počet 4-ciferných čísel s ciferným súčtom 6 nám vyšiel 3 
9 => 5;2;2;0 - Počet 4-ciferných čísel s ciferným súčtom 9 nám vyšiel 9 
12 => 5;5;2;0 - Počet 4-ciferných čísel s ciferným súčtom 12 nám vyšiel 9 
15 => 5;5;5;0 - Počet 4-ciferných čísel s ciferným súčtom 15 nám vyšiel 3 

7. Nakoniec čísla už len spočítame:

9 + 9 + 3 + 3 = 24

Odpoveď

Z cifier 2;5;0 vieme poskaladať 24 štvorciferných čísel deliteľných číslom 3.