Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Подстановки и перестановки n-степени



Пусть дан отрезок натурального ряда {1,2,…,n}. Назовем перестановкой порядка n любое расположение элементов этого множества.

Обозначим через Pn – число перестановок порядка n. Можно показать, что Pn=n!, n!=(n-1)…2*1

P3=3!=3*2*1=6

Пусть дана перестановка порядка n: n1, n2,…nk…nj…nn

nk, nj совершают инверсию nk>nj

ОПРЕДЕЛЕНИЕ:

Перестановку называют четной (нечетной), если общее число инверсий совершаемых всеми символами этой перестановки четно (нечетно).

ЛЕММА:

Если в перестановке поменять местами любые 2 символа, то четность перестановки изменяется на противоположную.

ОПРЕДЕЛЕНИЕ:

Подстановкой называют взаимноодназначное отображение множества {1,2,…,n} на себя.

Подстановки принято записывать:

Отметим что разных подстановок существует n!

Среди разнообразных форм записи одной и той же подстановки будем выделять каноническую, которая характеризуется тем, что первая строка записана в естественном порядке.

ОПРЕДЕЛЕНИЕ:

Подстановка называется четной (нечетной) если ее строки имеют одинаковую (разную) четность.





Дата публикования: 2015-07-22; Прочитано: 424 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...