Permutace a faktoriál

Podíváme se na pojem permutace v kombinatorice. Tento pojem se týká řazení prvků a symbolem P(n) označujeme počet všech různých permutací, které je možno sestavit z n prvků. Pojďme si to nejprve ukázat na nějakém konkrétním příkladu. Na pohovku, která má tři místa si chce sednout Adam, Bára a Cyril. Otázka je, kolika způsoby si na tuto sedačku mohou sednout, kolika způsoby mohou být seřazeni. Jenom pro jistotu, permutace nepočítají s opakováním, to znamená Adam, Bára, ani Cyril nemohou sedět na dvou nebo dokonce třech místech. Každý si sedne právě na jedno místo. Pojďme si zkusit všechna tato možná uspořádání vypsat. Nejprve někoho umístíme na první levé místo. Tam máme na výběr tři možnosti, Adama Báru, nebo Cyrila. Tyto možnosti ještě dále rozepíšeme. Jakmile už na prvním místě sedí Adam, pak na druhé místo už máme jenom dvě možnosti, Báru, nebo Cyrila. A jakmile posadíme někoho i na druhé místo, pak na třetí místo už si musí sednout ten poslední, který zbývá. Dostáváme tak první seřazení. Adam, Bára, Cyril a druhé seřazení, Adam, Cyril, Bára. Stejně tak budeme pokračovat, když si na první místo sedne Bára, pak na druhém místě může sedět Adam, nebo Cyril, a na třetím ten zbývající. Dostáváme další dvě možná uspořádání. A stejně tak když si na první místo sedne Cyril, tak na druhé může Adam nebo Bára. Na třetí potom půjde ten zbývající. A dostáváme tak dvě další a to už jsou poslední uspořádání, protože nikdo jiný už na prvním místě sedět nemůže. Všechny možnosti jsme vyčerpali. Celkem tak máme šest možností a to znamená, že existuje šest permutací ze tří prvků. Značíme symbolem P(3) rovno šest. Pojďme se podívat na nějaký systematický výpočet, jak na tyto výsledky můžeme přijít. Pokud ještě na sedačce nikdo není, pak máme tři možnosti, koho posadit na první místo, Adama, Báru, nebo Cyrila. Jakmile už si první sedl, na druhé místo máme už jen dvě možnosti. Tedy na každou z těchto tří možností navazují další dvě možnosti. A jakmile už sedí první dva, tak poslední už je jednoznačně dán. Tam máme pouze jednu možnost. Dostáváme tak výpočet tři krát dva krát jedna, to je oněch šest. A tento výpočet se v kombinatorice vyskytuje tak často, že dostal vlastní označení. Říká se mu faktoriál, konkrétně tři faktoriál, a značí se vykřičníkem. Je možné, že faktoriál máte i na kalkulačce. Stejnou úvahu můžeme provést i obecně, pro libovolný počet prvků, obecně n, a dostáváme tak vzoreček, že n-prvkových permutací je celkem n faktoriál. Což znamená m krát n minus jedna krát n minus 2 krát n minus 3 a tak dále, až do jedničky, vynásobíme všechna čísla od n až do 1. Pro jistotu ještě jeden příklad. Co kdybychom seřazovali pět prvků, pět kamarádů na nějakou větší pohovku. V tom případě na první místo můžeme posadit kteréhokoliv z pěti z nich, tedy pět možností. Jakmile tento první sedí, na druhé místo už zbývají pouze čtyři možnosti. Na třetí pouze tři, na čtvrté dvě a na poslední místo, tam už žádná volba není. Tam si musí sednout ten poslední, který zbývá. Dostáváme tak pět krát čtyři krát tři krát dva krát jedna. Pět krát čtyři je 20, krát tři je 60, krát dva je 120, násobení jedničkou už nic nezmění. Výsledek je tak 120, tedy existuje sto dvacet pěti-prvkových permutací, zkráceně zapíšeme jako 5 faktoriál. Mimochodem faktoriál je docela zajímavý tím, jak rychle narůstá a kolem faktoriálu je spousta úloh kombinatorických nebo z teorie her, ve kterých i velmi výkonné počítače začnou mít poměrně brzo problémy, protože počet možností, onen faktoriál, začne narůstat tak rychle, že ani superpočítač na to nestačí. Na závěr už jen připomenu náš odvozený vzoreček pro počet n-prvkových permutací.