Какво трябва да знаем:
Взаимно-еднозначни изображения
Мултипликативна и адитивна група 		Съдържание на висша математика I част

Пермутации


Да означим с (n) множеството {1,2,3, . . . , n}
Дефиниция:

Всяко взаимно-еднозначно изображение от множеството (n) в себе си

се нарича пермутация от n-ти ред.

Да означим с Pn множеството от пермутациите от n - ти ред.
Пермутациите се означават с директно изобразяване на функцията.


Пермутация от n - ти ред

В горния ред са елементите на (n) а в долния - техните образи.


Пермутация от n - ти ред

Обратната пермутация на p се означава , както е обикновено при изображенията, с p-1 .
Тя се получава като се подредят стълбовете в разширения запис на p така, че елементите от долния ред се подредят в естествен ред.


Пермутация от n - ти ред

Пермутацията p-1 е обратното изображение.


Пермутация - обрятна на p.

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


Пермутация от n - ти ред
Пример:


Пермутация от 4 - ти ред



Пермутация от n - ти ред

Ето и съкратения запис:
p = ( 2 4 1 3 )
p-1 = ( 3 1 4 2 )
Теорема 1
Броят на пермутациите от n елемента се означава с |Pn | и е равен на n!
n! се чете “n – факториел”.
n!=1.2.3.….n при което 0!=1 , 1!=1, 2!=2, 3!=6 и т.н.

Доказателство:
Да си представим n места, на всяко от които можем да поставим един от елементите от 1 до n , но без повторения.


Пермутация от n - ти ред

На първото място можем да поставим произволен елемент от множеството (n). За това имаме n възможности.
На второто място, изключвайки елемента, поставен на първо място имаме n-1 възможности.
За третото място n-2.
Продължавайки аналогично, за n –тото място ще имаме само 1 възможност.
Или общо n.(n-1).(n-2). ….1 = n! възможности.

Дефиниция
За пермутацията p казваме, че елементите a i и a j са в инверсия, ако i < j но a i > a j .
Неравенството i < j показва, че елемента a i е отляо на a j .
А неравенството a i > a j - че двата елемента са в обратен ред.
Пример
Намерете броят на инверсиите в пермутацията p4 = ( 2 4 1 3 )
Инверсиите са: 2,1 4,1 4,3.
Пермутацията p4 има 3 инверсии.
Дефиниция
Ако p има четен брой инверсии, казваме, че p е четна пермутация.
Иначе p се нарича нечетна.
Дефиниция
Със символа [p] се означава четността на пермутацията p.


Четност на пермутация
Теорема 2
Ако разместим местата на два елемента от пермутацията p = (a 1 a 2 a 3 ... a n-1 a n) , то тя променя своята четност.
Доказателство:
Първоначално ще считаме, че елементите, които разместваме - A и B са съседни.


Елементите, които ще разместваме са един до друг.

След размяната получанаме:


Ако елементите A и B не са в инверсия, те попадат в такава при рязмяната и обратно.
Положението им спрямо останалите елементи не се променя.
Нека сега A и B са в произволно положение и между тях има k елемента.
След размяната получанаме:



Чрез k размени ще докараме елемента B отдясно на A.
След размяната получанаме:


Чрез още k+1 размени ще разменим местата на A и B.
След размяната получанаме:


От доказаното в първата част на теоремата така ще променим четността на p 2k+1 - нечетен брой пъти.
Ако p е била четна ще стане нечетна и обратно.
Теорема 3
Броят на четните пермутации е равен на броя на нечетните.
Доказателство:
Нека P0,n е подмножеството на четните пермутации от Pn а P1,n - подмножеството на нечетните.
Ще установим взаимно-еднозначно изображение j между двете множества P0,n и P1,n .
Ако дефинираме .
  1. j е коректно дефинирано, защото на всяко p от P0,n съответсва точно определен образ от P1,n .
  2. j е инективно, защото не е възможно два елемента от P0,n да се изобразят в един елемент от P1,n .
  3. j е сюрективно, защото всеки елемент от P1,n притежава първообраз от P0,n .
Колчем между двете крайни множества съществува взаимно-еднозначно изображение, те имат еднакъв брой елементи.
Теорема 4
Четността на една пермутация е равен на четността на нейната обратна. [ p ] = [ p-1 ].
Доказателство:
След размяната получанаме:


Да разпишем подробно пермутацията p и да разместим стълбовете и така, че в долния ред елементите да се подредят в естествен ред.
Броят на разместванията определят четността [p].
p придобива вида:
След размяната получанаме:


След размяната получаваме:


Същия брой размествания подреждат долния ред на p-1 .
Следователно p и p-1 имат еднаква четност.
Задача:
Намерете всички пермутации от трети ред, обратните им и тяхните четности.

Какво ще научим:
Детерминанти ( Пиша.)