Таблицы Брадиса

Значит, при их композиции 1

Значит, при их композиции 1

Элементы математики в задачах - Г. А. Мерзон

Г123Л Г12345Л Г12345Л Г1234567Л записанныхканонически:                                                  , [12345] , [21354,), 17654321,) -

102                         Подстановки 1. Ходим по циклу

Определение 2. Произведением подстановок а, Ъе5п называется их композиция как отображений: а ◦ Ъ. Обозначение: аЪ.

Ш Здесь нужно помнить о том, что подстановки — это отображения из множества {1, 2,..., п} в себя (см. листок «Теория множеств 2»). Когда мы записываем композицию двух отображений, они записыва­ются как бы «в обратном порядке». Это удобно запоминать, мысленно приписав справа (х): получится аЪ(х). При этом, находя образ числа х, мы сначала вычисляем Ъ(х), а потом применяем к результату под­становку а и получаем а(Ъ(х)) = аЪ(х).

Ш Разберем два способа перемножения подстановок на конкретном примере. Пусть мы хотим вычислить произведение двух перестано­вок, записаных в канонической форме. Например, вычислим произ- 12345 Л А2345Л

ведение (43521) (2345^. Мы будем вычислять каноническую форму

произведения, постепенно заменяя на цифры значки «*» в подстанов- (12345Л

ке~результате [*****) .

Заметим, что в правой подстановке 1 переходит в 2, а затем в левой подстановке 2 переходит в 3. Значит, при их композиции 1 переходит в 3 и мы пишем вместо первой звездочки число 3. Аналогично дей­ствуем дальше:

(12345Л (12345 Л П2345Л П 2345 Л П2345Л П 2345 Л ^****^ ^ ^3***^ ^ ^35**^ ^ ^352*^ ^ ^3521*/ ^ ^3521+)'

Опишем второй способ, позволяющий в ряде случаев сократить вычисления. Допуетим, нам надо посчитать произведение подстано- /^12345Л А5342Л

вок (4352^ (2145^. Приведем первую подстановку к такому виду,

чтобы ее первая строка оказалась такой же, как и вторая стро­ка второй подстановки. В данном случае это будет выглядеть так: (12345Л (21453Л .