Перебор случаев

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой Перестановку можно интерпретировать как отображение множества цифр в себя. Например, тот факт, что первая буква перешла на третье место, можно записать как а также изобразить стрелочкой из 1 в 3:

Видно, что если бы мы перестановку применяли многократно, то буквы на 2-й и 6-й позициях постоянно менялись бы местами, а буквы на позициях 1, 3, 4, 5 переставлялись бы по циклу. Поэтому перестановка может символически быть записана в виде произведения циклов:

Запись отражает цикловую структуру перестановки показывая, что в ней один цикл длины 4 и один цикл длины 2.

Посмотрим теперь более детально на то, что произойдет, если по правилу переставить буквы еще раз. Так 1 при первом применении правила перешла в 3: а при повторном применении 3 перешла в 4: Значит, в результате двойной перестановки 1 переходит в 4. Будем это записывать как или же Поэтому правило двойной перестановки букв, представляющее собой квадрат перестановки выглядит так:

Заметим, что после повторной перестановки 2 и 6 вернутся на свои места, то есть цикл распадется на два тривиальных цикла и а цикл превратится в два цикла и Таким образом, при повторном применении перестановки циклы четной длины распадаются на два цикла, длины каждый. Несложно проверить, что при этом циклы нечетной длины сохраняются. Справедливо утверждение.

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

Рассмотрим первую комбинацию уеqwrt из пункта а). Она получена из qwerty перестановкой которая представляет собой цикл длины 6. Поскольку циклов четной длины здесь нечетное количество (всего один), то, согласно утверждению, такая комбинация двойной перестановкой букв получиться не могла. Аналогично исследуются и остальные комбинации в пункте а).

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

• Это перестановка, оставляющая все на своих местах (тождественная перестановка). Она единственна.
• Мы должны выбрать 5 элементов из шести, чтобы составить цикл дины 5. Это можно сделать 6-ю способами. Из пяти элементов цикл длины 5 можно организовать способами (действительно, организуем цикл из пяти элементов элемент может перейти в любой из четырех (т.к. в себя нельзя), элемент переходит в один из оставшихся трех и т.д. В итоге получаем способов). Таким образом, здесь перестановок.
• Выбрать два элемента из шести для первого цикла длины 2 можно способами. Для второго цикла длины 2 есть способа. Итого От порядка следования циклов результат не зависит, поэтому 90 еще следует разделить на два. Всего 45 перестановок с такой структурой.
• Здесь мы 6 элементов десятью способами разбиваем на две тройки и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.
• Здесь мы двадцатью способами выбираем тройку и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.

В итоге, имеется перестановок длины 6, представляющих собой полный квадрат.