Доказательства свойств перестановок (четные и нечетные)

[Folo4ka]

Здравствуйте.

Есть пара вопросов:
1) Есть свойство перестановок - кол-во четных перестановок = кол-ву нечетных и равно n!/2
Как это доказать?

2) Есть перестановки прямым и обратным способом
- прямой: iй элемент - в начало, i+1 - в конец (1234 -> 1342, 2143, 3124)
- обратный: iй элемент - в конец, i+1 - в начало (1234 -> 2341, 3142, 4123)

В зависимости от мощности перестановки одно из множеств получаемым одним из этих способов будет состоять только из четных перестановок (при n=4, множество перестановок прямым способом будет содержать n!/2=24/2=12 перестановок и все четные). Как доказать что в любом (общем случае, мощность=n) в неполное множество с n!/2 перестановками входят именно четные перестановки, а никакие-то другие. (я это определил в ручную на примере, а как это доказать для общего случая - незнаю)

[ewert]

Folo4ka в сообщении #549055 писал(а):

1) Есть свойство перестановок - кол-во четных перестановок = кол-ву нечетных и равно n!/2
Как это доказать?

Ибо есть между ними биекция: каждая чётная перестановка переходит в соотв. нечётную (и наоборот) транспозицией первой пары элементов.

[Null]

У вас уже была эта задача http://dxdy.ru/topic55188.html.

По существу: У вас есть 2 операции. Попробуйте перемножая их получить перестановку как можно сильнне совпадающую с нужной.

[Folo4ka]

спасибо за подсказку с биекцией

а знает кто, что такое четность (кол-во инверсии) элементов слева и справа от перестанавляемых эл-тов?

[bot]

Это Вы читаете про смену чётности при перестановке двух рядом (для начала) стоящих элементов? Здесь знать не надо - надо понимать по-русски.

[Folo4ka]

я знаю что такое четность перестановки... и знаю что каждая транспозиция меняет четность...
но есть еще какое-то явление... четность эл-тов слева и справа от 2х переставляемых эл-тов перестановки. и это как-то связано с четностью всей перестановки...

мне об этом говорит преподаватель... но в литературе я не могу найти понятия "четность слева" или справа, и поэтому не могу понять что он имеет в виду. но говорит, чтобы я это использовал =)

[ewert]

Folo4ka в сообщении #549973 писал(а):

но в литературе я не могу найти понятия "четность слева"

В нормальной литературе и нет такого "понятия".

Можно лишь говорить о чётности количества инверсий "слева". Но не нужно -- проку с этого никакого. Поскольку ключевое утверждение тут -- что чётность количества инверсий по всей перестановке вообще меняется на противоположную при каждой транспозиции. При транспозиции двух соседних элементов это тривиально, а общее утверждение сводится к тому, что любая транспозиция может быть получена как комбинация нечётного количества соседних, что тоже достаточно очевидно.