Пермутация

Пермутация се нарича всяка редица от елементи. Терминът „редица“ е по-общ: използва се във всички дялове на математиката. Терминът „пермутация“ има по-ограничена употреба: използва се предимно в комбинаториката. В комбинаториката се разглеждат различни видове съединения, най-известни от които са комбинациите, вариациите и пермутациите. Комбинациите са множества или мултимножества, а вариациите и пермутациите са редици. Една отделно взета редица може да бъде както вариация, така и пермутация; разликата между двата вида придобива смисъл едва когато се постави въпросът за пораждане на всички пермутации или вариации на дадена съвкупност от елементи: две пермутации се различават само по реда на елементите си, като задължително всяка от тях съдържа всички дадени елементи, докато две вариации се различават било по избраните елементи, било по техния ред.

Пермутациите могат да бъдат със или без повторение според това дали съдържат повтарящи се елементи.

Определение

Пермутация на $n$ елемента без повторение се нарича произволна редица, в която всеки от тези елементи се среща само веднъж. Броят на различните пермутации е равен на $P_{n}=n!=1.2.3...n$ (удивителната е знакът за факториел). Две пермутации без повторение на едно и също множество от елементи се различават само според реда на елементите си.

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

$f(a)=b,$

$f(b)=c,$

$f(c)=a,$

то $f$ е пермутация на елементите на $A$.

Пермутациите без повторение над наредено множество се делят на четни и нечетни според броя на инверсиите, които съдържат. Инверсия се нарича всяка двойка от елементи, в която по-големият елемент предхожда по-малкия.

Пермутация с повторение се нарича произволна редица, в която всеки от дадените елементи, два по два различни, се среща точно определен брой пъти и поне един елемент се повтаря. Броят на различните пермутации с повторение е равен на $(k_{1}+k_{2}+...+k_{r})!/(k_{1}!k_{2}!...k_{r}!),$ където първият елемент на множеството се среща в пермутацията $k_{1}$ пъти, вторият — $k_{2}$ пъти и т.н. Две пермутации с повторение на едно и също множество от елементи и с една и съща наредена $r$‑торка $(k_{1},k_{2},...,k_{r})$ се различават само според реда на елементите си. Всеки елемент на пермутация с повторение се брои толкова пъти, колкото пъти участва в нея, тоест броят на елементите на пермутацията е $n=k_{1}+k_{2}+...+k_{r},$ където $r$ е броят на различните елементи; а формулата за броя на пермутациите на $n$ елемента с повторение се записва още така: $n!/(k_{1}!k_{2}!...k_{r}!).$

Нотация

Примерът към определението показва, че пермутация може да се задава поелементно. Има две обозначения, които са по-удобни за онагледяване и анализ на пермутациите. Първото от тях е предложено от Коши:

$\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, като тези два елемента образуват друг цикъл.

В математиката е прието ненаредените съвкупности, т.е. множествата и мултимножествата, да се записват във фигурни скоби (например A = {x; y; z}), а наредените съвкупности, т.е. редиците, да се записват в кръгли или ъглови скоби. Например пермутацията $\sigma$, определена по-горе, може да се запише още така:
$\sigma =\;<2\;5\;4\;3\;1>$ или $\sigma =(2\;5\;4\;3\;1).$
Записът с кръгли скоби е двусмислен: той може да означава също пермутация, състояща се от единствен цикъл. В комбинаториката е прието при записване на пермутации всеки чифт кръгли скоби да огражда един цикъл на пермутацията.

Примери

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

Друг пример е разместването на букви в дадена дума (анаграма): воал — овал.

Играта 15 на Сам Лойд започва с произволна пермутация на петнайсет плочки, от която чрез серия от ходове трябва да се получи едно определено разположение. Това е възможно тогава и само тогава, когато началната пермутация е четна.

Играта 15 е само една от голям клас подобни главоблъсканици, известни като пермутационни игри. При всички тях трябва чрез определено множество от ходове да се разместват някакви елементи до получаването на предварително определено разположение. Най-известен представител на този тип главоблъсканици е кубът на Рубик.

Източници

1. Г. Брадистилов, Е. Божоров, Г. Тотов, С. Манолов, Висша математика, част I, С. Техника, 1965 г.
2. Димитър Вакарелов, Игра и математика, Народна просвета, 1986 г.

Вижте също

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

Тази статия, свързана с математика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.