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

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

ОпределениеРедактиране

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

Във висшата алгебра пермутация без повторение се дефинира формално като биекция от дадено множество в същото множество. Ако например имаме множеството   и функцията   за която

 
 
 

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

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

Пермутация с повторение се нарича произволна редица, в която всеки от дадените елементи, два по два различни, се среща точно определен брой пъти и поне един елемент се повтаря. Броят на различните пермутации с повторение е равен на   където първият елемент на множеството се среща в пермутацията   пъти, вторият —   пъти и т.н. Две пермутации с повторение на едно и също множество от елементи и с една и съща наредена  ‑торка   се различават само според реда на елементите си. Всеки елемент на пермутация с повторение се брои толкова пъти, колкото пъти участва в нея, тоест броят на елементите на пермутацията е   където   е броят на различните елементи; а формулата за броя на пермутациите на   елемента с повторение се записва още така:  

НотацияРедактиране

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

 

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

 
 
 
 
 

Това означава, че пермутацията поставя елемент 1 на мястото на елемент 2, елемент 2 на мястото на елемент 5, елемент 3 на мястото на елемент 4, елемент 4 на мястото на елемент 3, елемент 5 на мястото на елемент 1.

Друг начин на записване се основава на свойството, че всяка пермутация без повторение се представя по единствен начин като съвкупност от независими цикли. Например пермутацията

 

се разлага на цикли така:

 

Този запис отразява факта, че пермутацията изпраща:

— елемент 1 на мястото на елемент 2, елемент 2 на мястото на елемент 5, елемент 5 на мястото на елемент 1, като тези три елемента образуват един цикъл;

— елемент 3 на мястото на елемент 4 и елемент 4 на мястото на елемент 3, като тези два елемента образуват друг цикъл.

ПримериРедактиране

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

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

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

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

ИзточнициРедактиране

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

Вижте същоРедактиране