Přechod na menu, Přechod na obsah, Přechod na patičku
     

Permutace s opakováním


Při počítání s permutacemi bez opakování jsme počítali, kolik různých uspořádání můžeme utvořit ze všech předem daných prvků, kde se každý vyskytoval právě jednou.

I nyní nás bude zajímat počet různých uspořádání dané délky ze všech předem daných prvků s tím, že některé prvky mezi sebou nerozlišujeme, jinak řečeno mohou se opakovat. Na pořadí prvků stále záleží.



Řešené příklady

 

Příklad 1 – Vagóny

Strojvedoucí chce za lokomotivu připojit 3 vagóny, 1 je nákladní a 2 jsou osobní. Kolik různých možností má strojvedoucí, jak vagóny zapojit?     (Osobní vagóny mezi sebou nerozlišujeme.)

Řešení:(skrýt text)

Ilustrativní vlak se třemi vagóny

Uspořádáme všechny vagóny:
               $3 \cdot 2 \cdot 1 = 3!$

Tím, že osobní vagóny mezi sebou nerozlišujeme, nyní máme několik duplicitních uspořádání vagónů.

Všechna uspořádání jsou (N-nákladní, O1, O2-osobní vagóny – sice je nerozlišujeme, ale pro vysvětlení počítání si je označíme):
               N O1 O2    O1 N O2    O1 O2 N
               N O2 O1    O2 N O1    O2 O1 N

Jak to vyřešíme?
Všimněte si, že sloupce tvoří pevně umístěný nákladní vagón a k němu různá umístění osobních vagónů. Počet různých umístění osobních vagónů je 2!. Proto pokud je nerozlišujeme, musíme výsledek vydělit počtem permutací osobních vagónů. $$\frac{3!}{2!} = 3$$


Uspořádání vloček - bílá, modrá, bílá, bílá.

Příklad 2 – Vločky

Petra má 4 papírové sněhové vločky. Tři jsou bílé barvy a jedna je modrá. Kolik má možností uspořádání vloček, chce-li je zavěsit na čtyři okna tak, že na každém okně je právě jedna vločka.

Řešení:(skrýt text)

Celkem jsou $4$ vločky, počet jejich možných uspořádání je $4!$.

Jelikož bílé vločky mezi sebou nerozlišujeme, dělíme ještě počtem permutací třech bílých vloček a dostáváme výsledek:

$$ \frac{4!}{3!} = 4 $$

Proč dělíme počtem permutací třech vloček?

Pokud si vypíšeme všechna uspořádání vloček s rozlišením bílých vloček, dostáváme:
(B1, B2, B3 - bílé vločky, M - modré vločky)
               M B1 B2 B3    B1 M B2 B3    B1 B2 M B3    B1 B2 B3 M
               M B1 B3 B2    B1 M B3 B2    B1 B3 M B2    B1 B3 B2 M
               M B2 B1 B3    B2 M B1 B3    B2 B1 M B3    B2 B1 B3 M
               M B2 B3 B1    B2 M B3 B1    B2 B3 M B1    B2 B3 B1 M
               M B3 B1 B2    B3 M B1 B2    B3 B1 M B2    B3 B1 B2 M
               M B3 B2 B1    B3 M B2 B1    B3 B2 M B1    B3 B2 B1 M

V tabulce můžeme vidět, že sloupce tvoří právě ty čtveřice, které obsahují stejné postavení modré vločky vůči bílým. Tedy v rámci sloupce je umístění modré pevně dáno a bílé jsou propermutovány mezi sebou. Pokud tedy bílé vločky mezi sebou nerozlišujeme, musíme vydělit počtem řádků a těch je právě 3!.


Příklad 3 – Pěticiferná čísla

Určete počet všech pěticiferných přirozených čísel sestavených z číslic 4 a 6, má-li číslice 6 být obsažena právě třikrát.

Řešení:(skrýt text)

Jestliže číslice 6 má být obsažena třikrát, číslice 4 bude obsažena dvakrát.

Rozmísťujeme $2 + 3 $ ($= 5$) číslic: $ 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! $.

Číslice 6 mezi sebou nerozlišujeme, taktéž i číslice 4, proto ještě vydělíme počtem permutací jednotlivých číslic:

$$ \frac{5!}{2! \cdot 3!} = 10 $$

Příklad 4 – Abrakadabra

A) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA.

B) Určete, v kolika z nich žádná dvojice sousedních písmen není tvořena dvěma písmeny A.

Řešení:(skrýt text)

A) Jde o permutace s opakováním z pěti písmen A, B, D, K, R, v nichž je A pětkrát, B dvakrát, D jednou, K jednou a R dvakrát. Počet všech permutací tedy je: $ \dfrac{11!}{5! \cdot 2! \cdot 2! \cdot 1! \cdot 1!} = \dfrac{11!}{480} $

B) Nemají-li být dvě písmena A vedle sebe, musí být každé z pěti písmen A na jednom ze sedmi míst vyznačených podtržítkem:
_ B _ R _ K _ D _ B _ R _
Pět z těchto míst lze vybrat $\dbinom{7}{5}$ způsoby a zbývající písmena lze přemístit $ \dfrac{6!}{2! \cdot 2!}$
Počet všech "slov", v nichž žádná dvě písmena A spolu nesousedí, je $$\dbinom{7}{5} \cdot \dfrac{6!}{2! \cdot 2!} = 3780 $$



Definice

Definice: Permutace s opakováním z $n$ prvků je uspořádaná $n$-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje aspoň jednou.


Z předchozích úvah vyplývá následující věta:

Věta: Počet $P'(k_1, k_2, \ldots, k_n )$ všech permutací z $n$ prvků je: $$ P'(k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} $$

Ukážeme si postup podle vzorce:

Příklad 1 – Vagóny – podle vzorce(zobrazit text)


Příklad 4 – Abrakadabra – podle vzorce(zobrazit text)



Příklady k procvičení


Příklad 1

Určete počet způsobů, jimiž lze umístit všechny bílé šachové figurky (král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšáků)

a) na dvě pevně zvolené řady šachovnice 8 x 8;

b) na některé dvě řady šachovnice 8 x 8.

Řešení: (zobrazit text)


Příklad 2

Jistě jste poznali, že v anagramech AABIIKKMNOORT resp. MINIKABAROTOK je zašifrováno slovo KOMBINATORIKA. Určete počet všech anagramů, jež lze ze slova KOMBINATORIKA utvořit.

Řešení: (zobrazit text)


Příklad 3

Určete počet všech pěticiferných přirozených čísel, jež lze sestavit z číslic 5 a 7, má-li v každém z nich být číslice 5

a) právě třikrát;

b) nejvýše třikrát;

c) aspoň třikrát.

Řešení: (zobrazit text)


Příklad 4

Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než 0, 1, 5, 7.

Řešení: (zobrazit text)


Příklad 5

Určete počet všech anagramů, které lze získat z písmen slova ROKOKO, nesmějí-li v takovém anagramu stát všechna tři písmena O vedle sebe.

Řešení: (zobrazit text)


Příklad 6

Určete počet všech anagramů, které lze vytvořit z písmen slova PARABOLA, požadujeme-li, aby se ve vytvořeném anagramu pravidelně střídaly samohlásky a souhlásky.

Řešení: (zobrazit text)


Příklad 7

Pro osm studentů je připraveno v koleji ubytování ve 3 pokojích, z nichž 2 jsou třílůžkové, jeden dvoulůžkový. Kolik je způsobů rozdělení studentů do jednotlivých pokojů?

Řešení: (zobrazit text)


Příklad 8

Rychlíková souprava bude tvořena ze dvou zavazadlových vozů, jednoho jídelního vozu, čtyřech vozů lůžkových a tří lehátkových. Kolik různých typů souprav lze sestavit?

Řešení: (zobrazit text)


Příklad 9

Saturn Když Christian Huygens objevil Saturnův prstenec, zašifroval svůj objev, jak bylo v té době časté, do následujícího anagramu:

aaaaaaa ccccc d eeeee g h iiiiiii llll mm nnnnnnnnn
oooo pp q rr s ttttt uuuuu

Náležitým uspořádáním písmen dostaneme zprávu Annulo cingitur tenui, plano, nusquam cohaerente, ad eclipticam inclinato. Česky: Obklopen prstencem tenkým, plochým, nikde nezavěšeným, nakloněným k ekliptice.

Určete, za jak dlouho by počítač, který by vypsal milión permutací Huygensova anagramu za sekundu, vypsal všechny permutace.

Řešení: (zobrazit text)


Příklad 10

Poznáte zprávu Gaia Iulia Caesara zaslanou do Říma po vítězství nad pontským králem Farnakem, která se skrývá v anagramu CDEIIIIINVVV? Kolika způsoby lze v ní přemístit písmena?

Řešení: (zobrazit text)


Příklad 11

Určete počet všech deseticiferných přirozených čísel, jejichž ciferný součet je roven třem. Kolik z nich je sudých?

Řešení: (zobrazit text)


Příklad 12

Určete, kolik čtyřciferných čísel lze sestavit z číslic čísla 238 832.

Řešení: (zobrazit text)


Bc. Monika Stančíková |
ÚMS, Přírodovědecká fakulta, Masarykova univerzita |
Návrat na úvodní stránku webu, přístupnost |
Stránky Přírodovědecká fakulty MU
| Šablonu poskytlo:
| Servisní středisko pro e-learning na MU
| Fakulta informatiky Masarykovy univerzity, 2015