Пермутация

Пермутация се нарича всяка подредена съвкупност от n естествени числа, в която дадено число да се среща само веднъж.

Определение

Пермутация на n елемента наричаме произволна тяхна наредба, в която всеки един от тези елементи се среща само веднъж. Броят на възможните различни наредби (пермутации) се намира с факториел от n (n!=1×2×3× … n).

Всяко подреждане на дадени различни елементи се нарича пермутация (пермутация без повторение) на тези елементи. В дадена пермутация на елементи всеки елемент участва точно веднъж и мястото му в пермутацията е съществено.

Във висшата алгебра, пермутацията се дефинира формално като биективна функция от дадено множество в същото множество. Така например, ако имаме множество $A=\{a,b,c\}$ и функция $f:A\rightarrow A$, за която

$f(a)=b$

$f(b)=c$

$f(c)=a$

То $f$ е пермутация ($f$ е едновременно сюрективна и инективна, т.е. – биективна).

Представяне

Нека са дадени n различни елемента $a_{1},a_{2},...,a_{n}$. Те могат да бъдат подредени по различни начини. Всяко подреждане на елементите $a_{1},a_{2},...,a_{n}$ се нарича пермутация на $n$ елемента. Броят на всички възможни пермутации от n елемента се бележи с $P_{n}$. $P_{n}=n!$ (n факториел)

Нотация

Както бе демонстрирано в примера към дефиницията, пермутацията може да се задава по елементи. Съществуват два начина за обозначаване, които са по-удобни за визуализиране и анализ на действието на пермутацията. Първият от тях е т.нар. "Нотация на Коши":

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

Горният запис е еквивалентен на:

$\sigma (1)=2$

$\sigma (2)=5$

$\sigma (3)=4$

$\sigma (4)=3$

$\sigma (5)=1$

И означава, че пермутацията поставя елемент 1 на мястото на елемент 2, елемент 2 на мястото на елемент 5, елемент 3 – на мястото на елемент 4, елемент 4 – на мястото на елемент 3, елемент 5 – на мястото на елемент 1. Друг начин на записване представлява така наречената "циклична нотация". Пермутацията

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

от горния пример може да бъде записана в циклична нотация по следния начин:

$(125)(34)$

Това отразява, факта, че пермутацията праща елемент 1 на мястото на елемент 2, елемент 2 – на мястото на елемент 5, елемент 5 – на мястото на елемент 1, елемент 3 – на мястото на елемент 4 и елемент 4 – на мястото на елемент 3. Този запис е еквивалентен на горния, но разкрива по-ясно т.нар. "орбити" на пермутацията.

Примери

Типичен пример за пермутация е размесването на карти за игра. Всяка една нова подредба е пермутация на началната.

Друг пример е разместването на буквите в дадена дума, напр. воал -> овал.

Пермутациите се делят на два вида: четни и нечетни. Пермутацията е четна, когато има четен брой инверсии, а нечетна-има нечетен брой инверсии.

Пример:

$P_{1}=1!,P_{2}=1.2=2!,P_{3}=1.2.3=3!,P_{n}=n!,P_{n}+1=n!(n+1)=(n+1)!$

Вижте също

• Комбинация
• Комбинаторика