Пермутация: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м Робот Добавяне {{без източници}} |
м замяна с n-тире; козметични промени |
||
Ред 2:
{{обработка|форматиране, препратки}}
'''Пермутация''' се нарича всяка подредена съвкупност от n [[
== Определение ==
Пермутация на n елемента наричаме произволна тяхна наредба, в която всеки един от тези елементи се среща само веднъж. Броят на възможните различни наредби (пермутации) е n!=1.2.3...n.
Всяко подреждане на дадени различни елементи се нарича пермутация (пермутация без повторение) на тези елементи. В дадена пермутация на елементи всеки елемент участва точно веднъж и мястото му в пермутацията е съществено.
Във висшата алгебра, пермутацията се дефинира формално като биективна функция от дадено множество в същото множество. Така например, ако имаме множество <math>A=\{a, b, c\}</math> и функция <math>f:A\rightarrow A</math>, за която
:<math>f(a)=b</math>
:<math>f(b)=c</math>
:<math>f(c)=a</math>
То <math>f</math> е пермутация (<math>f</math> е едновременно сюрективна и инективна, т.е.
== Представяне ==
Нека са дадени n различни елемента <math> a_1, a_2,...,a_n </math>. Те могат да бъдат подредени по различни начини. Всяко подреждане на елементите <math> a_1, a_2,...,a_n </math> се нарича ''пермутация'' на <math> n </math> елемента. Броят на всички възможни пермутации от n елемента се бележи с <math>P_n</math>.
<math>P_n = n! </math> (n [[факториел]])
== Нотация ==
Както бе демонстрирано в примера към дефиницията, пермутацията може да се задава по елементи.
Съществуват два начина за обозначаване, които са по-удобни за визуализиране и анализ на действието на пермутацията. Първият от тях е т.нар. "Нотация на [[Коши]]":
: <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix};</math>
Горният запис е еквивалентен на:
: <math>\sigma(1)=2</math>
: <math>\sigma(2)=5</math>
Ред 32:
: <math>\sigma(4)=3</math>
: <math>\sigma(5)=1</math>
И означава, че пермутацията поставя елемент 1 на мястото на елемент 2, елемент 2 на мястото на елемент 5, елемент 3
Друг начин на записване представлява така наречената "циклична нотация". Пермутацията
: <math>\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix};</math>
от горния пример може да бъде записана в циклична нотация по следния начин:
:<math> (1 2 5)(3 4)</math>
Това отразява, факта, че пермутацията праща елемент 1 на мястото на елемент 2, елемент 2
Този запис е еквивалентен на горния, но разкрива по-ясно т.нар. "орбити" на пермутацията.
== Примери ==
Типичен пример за пермутация е размесването на карти за игра. Всяка една нова подредба е пермутация на началната.
Друг пример е разместването на буквите в дадена дума, напр. ''воал'' -> ''овал''.
Пермутациите се делят на два вида: четни и нечетни.
Пермутацията е четна, когато има четен брой инверсии, а нечетна-има нечетен брой инверсии.
Ред 57:
P_n = n!,
P_n+1 = n!(n+1) = (n+1)! </math>
== Вижте също ==
| |||