 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Перестановки конечного множества
|
|
Определение 1. Всякое взаимно однозначное отображение множества D на себя называется перестановкой множества D.
Пусть D конечное множество из n элементов D = { а 1, ..., аn } = { ai }, где i = 1, 2, ..., n. Отображение f есть перестановка для множества D, если f (ai) = aj,где ai Î D и aj Î D, i = 1, 2, ..., n, j = 1, 2, ..., n. Если i = j, то f (ai) = ai и имеет место тождественное отображение (f = е). Таким образом, тождественное отображение всегда есть перестановка.
Число различных перестановок множества D из n элементов равно n! (n факториал). n! = 1 · 2 · 3 ·... · n – произведение n последовательных натуральных чисел, начиная с единицы.
Определение 2. Перестановка, в которой изменены места лишь двух элементов множества, называется транспозицией.
a 1, a 2, ..., ai, ..., aj, ..., an
tij = a 1, a 2, ..., aj, ..., ai, ..., an
Всякая перестановка может быть получена из основной путем последовательных транспозиций. Выбор основной перестановки совершенно произволен. Для определенности назовем основной a 1, a 2, ..., an и рассмотрим произвольную перестановку f этого множества аi ¢ = f (ai), i = 1, 2, ..., n, но аi ¢ есть один из элементов a 1, a 2, ..., an и значит аi ¢ = 
, где m 1, m 2, ..., mn − значения некоторой перестановки множества 1, 2, ..., n, первых n натуральных чисел. Таким образом, следующие две перестановки эквивалентны:
~ 
.
Если в перестановке m 1, …, mn найдетсятакая пара(mj, mi), что i > j, а mi < mj, то говорят, что такая пара образует инверсию
Определение 3. Общее число инверсий, образуемых всевозможными парами перестановки m 1, m 2, ..., mn , называется числом инверсий этой перестановки.
Перестановка f называется четной, если число ее инверсий n (f) четное; в противном случае она называется нечетной.
Например, в перестановке
число инверсий равно: (2); (0); (2); (2); (1);(1)− общее число инверсий n (f) = 8. Перестановка f четная.
Теорема. При транспозиции четность перестановки изменяется, т.е. транспозиция − нечетная перестановка.
Доказательство.
tij = 
n (tij) = (j – i) + (j – i – 1) = 2(j – i) – 1– нечетное число.
Здесь: (j – i) − число инверсий для числа j после того, как его переставили;(j – i – 1) – число инверсий для всех чисел, расположенных после j и стоящихперед i. Для всех же остальных чисел число инверсий не изменилось.
Дата публикования: 2015-02-20; Прочитано: 484 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
