Пермутация

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Определение[редактиране | edit source]

Пермутация на 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 е едновременно сюрективна и инективна, т.е. - биективна).

Представяне[редактиране | edit source]

Нека са дадени n различни елемента  a_1, a_2,...,a_n . Те могат да бъдат подредени по различни начини. Всяко подреждане на елементите  a_1, a_2,...,a_n се нарича пермутация на  n елемента. Броят на всички възможни пермутации от n елемента се бележи с P_n. P_n = n! (n факториел)

Нотация[редактиране | edit source]

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

\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};

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

 (1 2 5)(3 4)

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

Примери[редактиране | edit source]

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

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

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

Пример:

 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)!

Свойства[редактиране | edit source]

Вижте също[редактиране | edit source]