Суббота, 10.12.2016, 02:07
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 7
Гостей: 7
Пользователей: 0
» »
11:18
Произведение перестановок

Как найти произведение перестановок

Перестановка порядка n это биективное отображение конечного множества из n элементов  в себя.

Таблица вида  

, что означает перестановку ,

Также можно для удобства переставлять столбцы местами:

Для наглядности, ту же перестановку можно изобразить картинкой вида

Пример вычисления произведения перестановок: если

При помощи обычного определения удобно вычислять произведение так: в перестановке σ переставляем столбцы так, что первая строчка в σ совпадает с последней строчкой в τ . Тогда произведением будет перестановка, у которой первая строчка — стандартная, а вторая строчка — это вторая строчка из σ.

Пример 1:

Пример 2. Найти произведение перестановок можно и так

Первая перестановка переводит один в два, а вторая два в семь, значит произведение переводит один в семь и т.д.

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

Например: στ= (1,2,4,3) · (1,3) = (2,4,3)

При этом произведение получается так: для каждого элемента от 1 до 4 надо пройти по циклам в левой части и проследить куда он переходит.

В частности, 3 сначала переходит в 1 (цикл (1 , 3)),

а затем 1 в 2 (цикл(1 , 2 , 4 , 3)).
Значит в произведении 3 будет переходить в 2.

Умножение перестановок некоммутативно:  τσ ≠ στ.

Следовательно решение уравнений вида:  τx = σ,  xτ = σ

x = τ-1σ,   x = στ-1

 

Категория: Комбинаторика | Просмотров: 1771 | Добавил: Admin | Теги: перестановки | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .