Чётность перестановки

Среда, 8 июля 2009 г.
Рубрика: Перестановки. Определитель
Просмотров: 21594
Подписаться на комментарии по RSS

Теорема. Любая транспозиция соседних элементов перестановки меняет четность перестановки на противоположную.

Доказательство. Пусть дана перестановка , в которой мы выполним транспозицию (i j) и получим перестановку . Сразу заметим, что все пары, которые образовывали инверсию в старой перестановке, образуют инверсию и в новой, кроме возможно одной пары: (i, j). Если эта пара давала инверсию в старой перестановке, то в новой уже нет и число инверсий уменьшается на 1. Если же эта пара не образовывала инверсию в старой перестановке, то в новой образует инверсию и число инверсий увеличивается на 1. В любом случае, число инверсий изменяется на 1, а следовательно, меняется четность перестановки.

Теорема доказана.

Теорема. Любая транспозиция любых двух элементов перестановки меняет четность перестановки на противоположную.

Доказательство. Пусть выполняется транспозицию (i j) и пусть между элементами i и j находится m других элементов. Легко видеть, что такую транспозицию можно выполнить за  транспозицию соседних элементов, откуда и следует теорема.

Теорема доказана.

Теорема. Любую перестановку можно получить из начальной перестановки последовательным выполнением конечного числа транспозиций, причем это количество транспозиций есть число четное, если данная перестановка четна, и нечетное в противном случае.

Доказательство. Очевидно в свете следующего примера.

Пример.

.

Здесь, перестановка  приведена к начальной за

4 транспозиции и она четная, т.к. .

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

Теорема. Количество четных перестановок множества из  элементов равно количеству нечетных и равно .

Доказательство. Каждая перестановка либо четная, либо нечетная. Поэтому общее количество четных перестановок неизменно. Так же и количество нечетных перестановок есть число фиксированное. Во всех перестановках выполним одну и ту же транспозицию, например, (1 2). Все четные перестановки станут нечетными и наоборот, все нечетные станут четными. Следовательно, четных и нечетных перестановок одинаковое количество.

Теорема доказана.

Замечание. Предлагается следующая интерпретация к предыдущей теореме.

Пусть на некоторой вечеринке находится какое-то количество людей, причем все женщины в шляпках, а мужчины в масках. Допустим, что в некоторый момент времени, каждый мужчина должен отдать женщине свою маску и получить от нее головной убор. Каково должно быть соотношение мужчин и женщин, чтобы каждый мужчина получил шляпку, а каждая женщина – маску?

Ответ очевиден.

twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru rutvit.ru myspace.com technorati.com digg.com friendfeed.com pikabu.ru blogger.com liveinternet.ru livejournal.ru memori.ru google.com bobrdobr.ru mister-wong.ru yahoo.com yandex.ru del.icio.us

Оставьте комментарий!