Перестановки, Объясните [перемещено] Опции

[Cheburashka]

В общем, достаточно давно я встретился с такой сложной темой (для меня) как перестановки. Сколько я не искал литературы на эту темы, но ничего стоющего не нашёл. Поэтому обратился именно к Вам.

Не могли бы Вы объяснить в чём основной смысл, и как они выполняются?

Сообщение отредактировано: Lapp - 17.07.2009 3:00

[Cheburashka]

В принципе всё выше сказанное мне становится понятным... Я раньше не мог понять во многих задачах как выполняются перестаноки в основном из-за того что их выписывают в лексикографическом порядке.
Но в данной теме есть очень много понятий которые мне не ясны.
К примеру:

Циклическим сдвигом на k перестановки p1, p2, ... , pn называется последовательность, p_k+1, p_k+2, ... , p_n, p₁, ... , p_k. Отметим, что любой циклический сдвиг перестановки также является перестановкой. (пример - 3 2 1. Ответ -1 3 2)

В данном случае мне не понятна сама последовательность, и чем в данном случае является k.

Сообщение отредактировано: Сергей Меркурьев - 18.07.2009 15:27

[Lapp]

В данном случае мне не понятна сама последовательность, и чем в данном случае является k.

Тут производятся операции над операциями, то есть над перестановками. То есть добавляется еще один уровень. Было множество, пример:
a b c d e f g.
Над ним были операции (перестановки), пример:
2 4 3 5 1 7 6.
Теперь есть еще и операция над перстановками. Она выражается числом k, означающим насколько нужно сдвинуть цифры в перестановке направо. Например, при к=2 приведенная выше перестановка превращается в такую:
7 6 2 4 3 5 1 .
Слова о том, что циклический сдвиг снова является перестановкой означают следующее. Из определения перестановки следует, что не всякий набор чисел есть перестанока. Например, набор:
2 2 2 1 1 1 3
- перестановкой не является. В перестаноке все числа должны быть разными. Но ясно, что если они были разными, то они останутся разными и после циклического сдвига как операции над перестановкой при любом k. И, следовательно, результат такого сдвига можно трактовать как перестановку. Вообще говоря, это необходимое условие для действия над объектами, чтобы это действие называлось операцией: оно не должно выводить объект за пределы пространства этих объектов.