Лемма 4. n элементтен жасалған орын ауыстырулардың саны n!-ға тең болады.
Дәлелдеуі: n=1 орын ауыстырулар саны n!=1.
n=2→n!=2;
n=3→n!=6;
n-1 үшін лемма дұрыс деп есептеп, n үшін дәлелдейік.
 орын ауыстыруындағы  -ң орнына ретімен 1, 2, …, n қойып орын ауыстыруларды санайық:
 бұлардың саны n –ге тең әрбір орын ауыстыруға кіретін n-1 элементтен тұратын орын ауыстырулардың саны (n-1)!- ға тең. Сонда n элементтен тұратын орын ауыстырулар саны n(n-1)!=n(n-1)! болады.
Анықтама. i, j екілігі α орын ауыстыруында инверсия құрайды деп аталады, егер i>j болса немесе i символы j символынан бұрын кездесетін болса; inv(α) арқылы α орын ауыстыруындағы инверсиялардың санын белгілейміз.
Анықтама. Oрын ауыстыруы жұп деп аталады, егер жұп болса, тақ деп аталады, егер тақ болса.
Мысал: (1, 2, 3)- инверсия құрамайды –жұп; inv=0;
(2, 1, 3)-2, 1- инверсия құрайды- тақ; inv=1;
(2, 3, 1)-3,1 және 2,1 инверсия құрайды –жұп; invһ2.
Анықтама. Орын ауыстырудағы 2 символдың орындарын алмастыратын амалды транспозиция деп атайды.
Лемма. Транспозиция орын ауыстырудың жұптығын өзгертеді.
1) Транспозиция орын ауыстырудағы қатар тұрған i. j символдарының орындарын алмастыратын болсын, онда 
i символы мен j символы енбейтін инверсиялар толық сақталады.
Егер   мен  жұптығы әр түрлі.
Онда орын ауыстыруын  орын ауыстыруынан қатар тұрған 2 символдық транспозициясы арқылы келесі түрде алуға болады:
 k рет транспозиция қолданылады.
 -1 рет
 k рет.
Достарыңызбен бөлісу: |
