Извлечение квадратного корня из перестановки чисел: выводим новую(?) формулу12.10.2024 11:45

В этой статье мы исследуем проблему извлечения квадратного корня из перестановки p, иными словами задачу нахождения такой перестановки x, что x * x = p. Будет сформулирован критерий возможности извлечения квадратного корня, алгоритм нахождения корней и формула их подсчёта в общем виде. Автор не смог найти подтверждение полученной формулы в авторитетных источниках, поэтому читатель может сам оценить корректность моих рассуждений.

Действующие лица

Пусть дана перестановка $p = \{2, 4, 3, 1\}$ . Если ее применить на последовательность из четырёх объектов $s = \{n_1, n_2, n_3, n_4\}$ , то 1 переходит в 2, 2 в 4 и т.д. Над перестановкой расставляем верхние индексы и смотрим кто куда переходит. Тогда $p \circ s = \{n_2, n_4, n_3, n_1\}$ .

Для каждой перестановки можно записать ее цикловую структуру. Для этого снова пишем над верхние индексы и смотрим куда переходит 1. 1 переходит в 2, следовательно пока пишем так: $p = (12 \dots$ . 2 переходит в 4, 4 переходит в 1, 1 переходит в 2. Цикл замкнулся, его длина 3, т.е. это 3-цикл. А 3 переходит в 3, образуя 1-цикл. Итого: p = (124)(3) , но 1-циклы обычно опускают.

Назовем паспортом перестановки такой словарь (в терминах Python), где ключами выступают длины циклов существующих в перестановке, а значениями — количество циклов такой длины. Паспорт для запишется так: {1: 1, 3: 1}.

Перестановка $\hat{p} = \{4, 1, 3, 2\} = (142)(3)$ тоже 3-цикл и имеет такие же свойства (порядок, четность и количество корней), как и p. Поэтому для группы перестановок длины (обозначается S_n ) имеет смысл рассматривать «посольство» от каждой возможной цикловой структуры, а не все сразу.

Корневые карты

Для начала попробуем проанализировать проблему поиска корней эмпирически. Составим корневую карту (ориентированный граф), где вершины — это цикловые структуры, а А и Б соединяются ребром, если при извлечении корня из перестановки А можно получить перестановку с цикловой структурой Б.

Карта для группы S5

Зеленым цветом показаны четные перестановки, желтым — нечётные. Вершина () — это нейтральный элемент, перестановка, полностью состоящая из 1-циклов, которая ничего не переставляет. Обратим внимание на вершину (3). Из нее выходит ребро в само себя и ребро в (2, 3). То есть при извлечении корня из любой перестановки с структурой 3-цикл, получится несколько ответов: как минимум будет 1 3-цикл и 1 (2, 3)-цикл.

Карта для группы S6

Подметим закономерность с нейтральным элементом (). На обоих графах он соединён ребрами с 2-циклами. И так будет продолжаться и дальше. Дело в том, что есть понятие порядка: такое наименьшее , что p^n = e ( — нейтральная перестановка). Порядок для перестановки считается как НОК (наименьшее общее кратное) от длины его цикловых структур. Так и получается, что 2-циклы разной длины при возведении в квадрат всегда будут давать нейтральную перестановку.

На картах можно заметить и другие паттерны, однако перейдем уже к менее эмпирической части нашего рассказа.

Реверсивная психология

Мы уже выяснили, что нам важна цикловая структура. Понаблюдаем за поведением перестановок при обратной операции — возведении в квадрат. Нам достаточно проанализировать поведение цикла, так как пусть $p = c_1 \cdot \ldots \cdot c_n$ , а $p^2 = c_1^2 \cdot \ldots \cdot c_n^2$ ввиду того что непересекающиеся циклы коммутируют.

Запишем цикл в общем виде как $c = (x_1x_2 \ldots x_k)$ . Квадрат цикла c^2 переведет x_1 в x_3 , x_2 в x_4 и т.д. В общем виде: $x_i \rightarrow x_{(i+2) mod \ k}$ . Но возможны два случая, обратим внимание на чётность длины цикла :

Если k нечётное, то квадрат также будет -циклом. Если чётное, то квадрат разобьется на два цикла: $c^2 = (x_1x_3 \ldots x_{k-1})(x_2x_4 \ldots x_k)$ .

Теперь применим полученные знания в обратную сторону. Из одного цикла нечетной длины корень всегда можно извлечь, причём однозначно. Но пара циклов одинаковой длины при извлечении корня схлопнутся в новый цикл длины . В этом моменте и берется неоднозначность при извлечении корня — существует же несколько способов выбрать пару.

Обратите внимание и на другой факт: если в исходной перестановке есть хоть один случай, когда нечетное количество циклов четной длины, то из него нельзя извлечь корень. Поскольку при разбиении на двойки, одному из циклов четной длины не найдется пары, и тогда непонятно, как он вообще здесь появился, если мы предполагаем, что p = x^2. Так, мы формулируем критерий извлечения квадратного корня: каждый цикл четной длины должен входить в перестановку четное количество раз.

При выводе формулы будем полагать, что этот критерий соблюдается.

Выводим формулу

Подчеркнем еще раз важное отличие между циклами четной и нечетной длины. Когда мы будем формировать пары, то для циклов нечетной длины могут остаться свободные члены. Более того, количество пар может варьироваться от 0 до $\lfloor \frac{n}{2} \rfloor$ (округление вниз), где — количество циклов одинаковой длины. Для простоты будет пользоваться Python-обозначением n // 2. Для циклов четной длины такой свободы выбора нет — каждый должен найти себе пару.

Составил таблицу истинного числа корней (данные получены перебором на Python)

Чтобы дальнейшие заключения не выглядели слишком умозрительными, то я приведу таблицу с количеством корней. Вы сейчас можете прикинуть — понимаете ли вы алгоритм или нет.

Переформулирую задачу на язык комбинаторики: найти количество пар из n элементов, где порядок между и внутри парами не важен. Обозначим этот ответ за A(k, n) , выразить его не проблема.

Обратим внимание на извлечение корня из (3,3)-цикла в S_7 .

Результат перебора программой

Первый случай это извлечения корня из нечетных циклов. Другие три — комбинация 3-циклов для получения 6-цикла. Она может быть проведена 3 способами (нужно выбрать, что будет идти после 1, т.е. равна длине цикла, выбираем 1 раз). Эти выборы необходимо учесть в итоговой формуле.

Мы готовы записать результат.

пришлось вставить скрин, так как Хабр лагает

Первый множитель отражает циклы с нечетной длиной, у которых есть свобода выбора — объединяться в пары или нет. Второй множитель это циклы с четной длиной, последнее слагаемое первой суммы. Это выражение записано для одной пары ключ-значение в паспорте перестановки. Общее количество корней это произведение для каждой существующей пары. Код на Python, считающий количество корней (необходимо реализовать класс Permutation с методом pasport):

def find_amountofsquareroots(perm: Permutation):
    def member_of_sum(n, cyclen, k):
        return (math.factorial(n) * cyclen ** k) // (math.factorial(k) * (2 ** k) * math.factorial(n - 2 * k))

    def odd_count(n, cyclen):
        total_sum = 0
        for k in range(0, n // 2 + 1):
            total_sum += member_of_sum(n, cyclen, k)

        return total_sum

    def even_count(n, cyclen):
        assert n % 2 == 0, 'для извлечения корня m должно быть четным'
        return member_of_sum(n, cyclen, n // 2)

    psp = perm.passport()
    answer = 1
    for cycle_len, cnt in psp.items():
        if cycle_len % 2 != 0:
            answer *= odd_count(cnt, cycle_len)
        else:
            if cnt % 2 == 0:
                answer *= even_count(cnt, cycle_len)
            else:
                answer = 0
                break
    return answer

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

Habrahabr.ru прочитано 26689 раз