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

Тогда у числа, в которое

Тогда у числа, в которое

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

1,213,) , 113^ , 132^ , 123и , 131^ .

б)  Рассмотрим варианты того, куда может переходить единица в цикле длины 57. Для этого имеется 56 вариантов (все числа кроме самой единицы). Тогда у числа, в которое перешла единица, есть 55 вариантов перехода (все числа, кроме себя и единицы), у следующего будет 54 варианта, и так далее. Значит, ответ 56!.

в) В 55 имеется С| = 10 транспозиций (т. е. циклов длины 2): (1 2), (13), (14), (15), (2 3), (2 4), (2 5), (3 4), (3 5), (45).

Кроме того, в 55 имеется (3 — 1)! ■ С| = 2 ■ 10 = 20 циклов длины 3: (123), (321); (124), (421); (125), (521); (134), (431); (135), (5 3 1); (145), (5 41); (2 3 4), (43 2); (2 3 5), (5 3 2); (2 45), (5 42); (3 45), (5 43).

Еще имеется (4 — 1)! ■ С4 = 3! ■ 5 = 30 циклов длины 4 (здесь в качестве упражнения их также можно выписать).

И, наконец, циклов длины 5 будет 4! ■ С| = 24. Получаем ответ:

10  + 20 + 30 + 24 = 84.

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

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

произведение транспозиций, пересекающихся по одному элементу есть цикл длины 3, а произведение непересекающихся транспозиций циклом не является.

Определение 6. Циклы с непересекающимися носителями называ­ются независимыми.

Задача 9*. а) Докажите, что любая подстановка представляется в виде произведения независимых циклов.

б) Докажите, что любая подстановка представляется в виде про­изведения транспозиций.

в) Докажите, что любая подстановка из Бп представляется в виде произведения не более чем п — 1 транспозиции.

г) Верно ли, что любая подстановка из Бп представляется в виде произведения независимых транспозиций?

Набросок решения. а) Утверждение этой задачи наглядно очевидно из графической записи подстановки.