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

ЧЛ 2 п

ЧЛ 2 п

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

ЧЛ ]2" ]п;

(12 "п), следуя одному из описанных способов.

б)  Решение задачи следует из аналогичного свойства отображе­ний (листок «Теория множеств 2»).

в) Если подстановка а имеет вид (І.1 !.2'' ' V ), то в качестве Ь нужно

чл }2.. 'Ь;

взять подстановку вида ^І1 і2 ''' Іп^. Теперь легко проверить напрямую, что подстановка Ь удовлетворяет условию задачи.

Полезно понимать, как по графу подстановки построить граф об­ратной к ней.

ственной

.п

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

Определение 4. Пусть 1 ^ [, ] ^ п, [ = Подстановка а такая, что а(0 = }, а(}) = {, а(к) = к при к = I, }, называется транспозицией. Обозначение: (£_/).

Определение 5. Пусть 11,12,1к — различные элементы множества {1,2,..., п}. Подстановка а, сдвигающая элементы 11,12, ..., 1к, то есть такая, что а(^) = ^+1 для любого ] е {1, 2, ..., к — 1}, а([к) = 11 и а(&) = = 5 при 5 е {4, ^2, •••> *к}> называется циклом длины к. Обозначение: (1112..лк). Множество {11, ..., 1к} называется носителем цикла, а число к — длиной цикла.

Задача 8. а) Какие из подстановок задач 1 и 2 являются циклами, а какие — транспозициями?

б) Сколько циклов длины 57 в 557?

в) Сколько циклов и сколько транспозиций в 55?

г) При каких условиях произведение двух транспозиций является циклом?

д*) При каких условиях произведение двух циклов является цик­лом?

Решение. Не будем упоминать в перечислении тождественную под­становку— «цикл длины 1», присутствующую в каждом 5п.

Л ^                                      -                                         (514632^

а)  Среди подстановок первой задачи лишь один цикл: (164253 ) -

В 5Х циклов нет. В 52 только один цикл — (12). В 53 пять циклов: (123е (123е (123е (123е (123е