2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Доказательства свойств перестановок (четные и нечетные)
Сообщение16.03.2012, 20:37 
Здравствуйте.

Есть пара вопросов:
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 перестановками входят именно четные перестановки, а никакие-то другие. (я это определил в ручную на примере, а как это доказать для общего случая - незнаю)

 
 
 
 Re: Док-ва свойств перестановок
Сообщение16.03.2012, 20:59 
Folo4ka в сообщении #549055 писал(а):
1) Есть свойство перестановок - кол-во четных перестановок = кол-ву нечетных и равно n!/2
Как это доказать?

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

 
 
 
 Re: Док-ва свойств перестановок
Сообщение16.03.2012, 22:10 
У вас уже была эта задача http://dxdy.ru/topic55188.html.

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

 
 
 
 Re: Док-ва свойств перестановок
Сообщение17.03.2012, 10:00 
спасибо за подсказку с биекцией

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

 
 
 
 Re: Док-ва свойств перестановок
Сообщение17.03.2012, 11:52 
Аватара пользователя
Это Вы читаете про смену чётности при перестановке двух рядом (для начала) стоящих элементов? Здесь знать не надо - надо понимать по-русски.

 
 
 
 Re: Док-ва свойств перестановок
Сообщение19.03.2012, 13:58 
я знаю что такое четность перестановки... и знаю что каждая транспозиция меняет четность...
но есть еще какое-то явление... четность эл-тов слева и справа от 2х переставляемых эл-тов перестановки. и это как-то связано с четностью всей перестановки...

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

 
 
 
 Re: Док-ва свойств перестановок
Сообщение19.03.2012, 15:09 
Folo4ka в сообщении #549973 писал(а):
но в литературе я не могу найти понятия "четность слева"

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

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group