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

Из пункта а следует, что

Из пункта а следует, что

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

Прежде чем переходить к формальному доказательству, следует разобрать несколько примеров, чтобы разобраться в том, что проис­ходит. Рассмотрим, например, подстановку

^ ~ ( 35497826?) ~ (1349)'(257) *(68).

~0~                    Теперь ясно как доказывать утверждение задачи в общем случае.                                 ~0~

Возьмем произвольный элемент (можно начать с единицы), и рас­смотрим последовательность 1, а(1), а(а(1)), ... Эта последователь­ность обязательно замкнется, так как множество возможных значе­ний конечно.

Тонкий момент: почему последний элемент перейдет в единицу (а не в какой-то другой элемент цепочки)? Это следует из того, что подстановка — биективное отображение.

Итак, подстановка а содержит замкнутый цикл {1, а(1),... }. Возь­мем теперь произвольный элемент Ь, не лежащий в этом цикле и рассмотрим последовательность Ь, а(Ь), а(а(Ь)),..., которая даст еще один цикл, и так далее, пока вся подстановка не разобьется на циклы.

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

Полезно рассмотреть какой-нибудь пример:

(12142679 = (16) ■ (1 5) ■ (12) ■ (1 4) ■ (17) ■ (1 9) ■ (18) ■ (1 3).

В общем случае (і1 і2...ік) = (ікік—1)...(із і2)(і2 У-

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

в)      Утверждение следует из предыдущих пунктов. Из пункта а) сле­дует, что каждая подстановка из Бп представима в виде произведения независимых циклов, суммарная длина которых не превышает п. А каждый цикл длины п, в свою очередь, как следует из пункта б), представим в виде произведения п — 1 транспозиции.