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

[Cheburashka]

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

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

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

[Cheburashka]

С обычным понятием перестановки мне всё понятно (хотя формулу мне так и не удалось вывести).

sheka, Ну это я понимаю. А вот как быть к примеру вот с таким:

"Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.

Обратной перестановкой к перестановке π называется такая перестановка π^-1, что ππ^-1 = π^-1π = ε, где ε – тождественная перестановка. "

(И пример - 2 3 1. Ответ - 3 1 2).
Вот с этим я вообще разобраться не могу...

[Lapp]

(И пример - 2 3 1. Ответ - 3 1 2).
Вот с этим я вообще разобраться не могу...

Все нужно проделать, и сразу станет ясно. Смотри..
Есть упорядоченное множество:

a b c

Берем перестановку из этого примера:

2 3 1

Действуем, как она указывает:
на первое место ставим второй элемент (b),
на второе место ставим третий элемент (с ),
на третье - первый (a).
В результате имеем:

b c a

Теперь мы имеем множество в новом порядке. Вопрос: какой должна быть перестановка, чтобы вернуться к старому порядку? Конструируем эту перестановку:
на первое место надо поставить a, а оно у нас имеет номер 3,
на второе место надо поставить b, а оно у нас имеет номер 1,
на третье место надо поставить c, а оно у нас имеет номер 2.
Записываем это в виде перестановки:

3 1 2

Это и есть ответ.
Ясно?

-----------------------

С формулой все просто. Я немного уточню, что sheka (извиняюсь, первоначально было amega) сказал.
Пусть число перестановок для множества из N шаров равно числу П(N). Попробуем на основании этого выяснить, чему равно число перестановок множества из N+1 шаров. Будем действовать за N+1 шагов:

1. Поставим на первое место шар номер 1. Остальные образуют множество из N шаров, его число перестановок равно П(N).
2. Поставим на первое место шар номер 2. Остальные образуют множество из N шаров, его число перестановок равно П(N).
3. Поставим на первое место шар номер 3. Остальные образуют множество из N шаров, его число перестановок равно П(N).
....
N. Поставим на первое место шар номер N. Остальные образуют множество из N шаров, его число перестановок равно П(N).
N+1. Поставим на первое место шар номер N+1. Остальные образуют множество из N шаров, его число перестановок равно П(N).

В результате на первом месте побывали все шары, причем по одному разу. Остальные шары расставлялись всеми возожными способами. Значит, мы выполнили все перестановки. Для того, чтобы найти их число, нужно сложить числа перестановок на всех шагах. В каждом из них П(N), всего шагов N+1. Следовательно, общее число перестановок равно:

П(N+1) = (N+1)*П(N)

Уже отсюда видно, что смахивает на факториал (но еще остается возможность включения некоторого коэффициента). Чтобы в этом убедиться, нужно рассмотреть начало: число перестановок множества из 1 шара равно 1. Это как раз совпадает с факториалом. Следовательно:

П(N) = N!

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