Лема Бернсайда / теорема Поя

Лема Бернсайда

Лему Бернсайда сформулював і довів Бернсайд у 1897 році, але історично її вже відкрив у 1887 році Фробеніус, а ще раніше, у 1845 році, — Коші. Тому її іноді також називають лемою Коші — Фробеніуса.

Лема Бернсайда дозволяє нам підрахувати кількість класів еквівалентності в множинах, спираючись на внутрішню симетрію.

Коли підходить цей алгоритм?

• Чи рахуємо об'єкти з точністю до симетрії — коли розфарбування/конфігурації, що переходять одна в одну поворотом, відображенням чи перестановкою, вважаються однаковими?
• Чи можна описати ці симетрії як групу перестановок представлень (повороти намиста, симетрії многокутника тощо)?
• Чи звичайний підрахунок дає завищену відповідь через дублікати-симетрії? (якщо симетрій немає → Біноміальні коефіцієнти або Принцип включення-виключення)

Об'єкти та представлення

Нам слід чітко розрізняти кількість об'єктів і кількість представлень.

Різні представлення можуть відповідати тим самим об'єктам, але, звісно, будь-яке представлення відповідає рівно одному об'єкту. Відповідно множина всіх представлень розбивається на класи еквівалентності. Наше завдання — обчислити кількість об'єктів, або, що те саме, кількість класів еквівалентності. Наступний приклад зробить різницю між об'єктом і представленням зрозумілішою.

Приклад: розфарбовування бінарних дерев

Припустимо, маємо таку задачу. Нам треба підрахувати кількість способів розфарбувати кореневе бінарне дерево з $n$ вершинами двома кольорами, де в кожній вершині ми не розрізняємо лівого і правого нащадків.

Тут множина об'єктів — це множина різних розфарбувань дерева.

Тепер визначимо множину представлень. Представлення розфарбування — це функція $f(v)$, яка присвоює кожній вершині колір (тут ми використовуємо кольори $0$ і $1$). Множина представлень — це множина, що містить усі можливі функції такого виду, і її розмір, очевидно, дорівнює $2^n$.

Водночас ми вводимо розбиття цієї множини на класи еквівалентності.

Наприклад, припустимо, що $n = 3$, а дерево складається з кореня $1$ та його двох нащадків $2$ і $3$. Тоді наступні функції $f_1$ і $f_2$ вважаються еквівалентними.

$$\begin{array}{ll} f_1(1) = 0 & f_2(1) = 0\\ f_1(2) = 1 & f_2(2) = 0\\ f_1(3) = 0 & f_2(3) = 1 \end{array}$$

Інваріантні перестановки

Чому ці дві функції $f_1$ і $f_2$ належать до одного класу еквівалентності? Інтуїтивно це зрозуміло — ми можемо переставити нащадків вершини $1$, вершини $2$ і $3$, і після такого перетворення функції $f_1$ вона збігатиметься з $f_2$.

Але формально це означає, що існує інваріантна перестановка $\pi$ (тобто перестановка, яка не змінює сам об'єкт, а лише його представлення), така, що:

$$f_2 \pi \equiv f_1$$

Отже, виходячи з означення об'єктів, ми можемо знайти всі інваріантні перестановки, тобто всі перестановки, які не змінюють об'єкт при застосуванні перестановки до представлення. Тоді ми можемо перевірити, чи дві функції $f_1$ і $f_2$ еквівалентні (тобто чи відповідають вони тому самому об'єкту), перевіривши умову $f_2 \pi \equiv f_1$ для кожної інваріантної перестановки (або, що те саме, $f_1 \pi \equiv f_2$). Якщо знайдеться хоча б одна перестановка, для якої умова виконується, то $f_1$ і $f_2$ еквівалентні, інакше вони не еквівалентні.

Знаходження всіх таких інваріантних перестановок щодо означення об'єкта є ключовим кроком для застосування як леми Бернсайда, так і теореми Поя. Зрозуміло, що ці інваріантні перестановки залежать від конкретної задачі, і їх знаходження — суто евристичний процес, що ґрунтується на інтуїтивних міркуваннях. Однак у більшості випадків достатньо вручну знайти кілька «базових» перестановок, за допомогою яких можна породити всі інші перестановки (і цю частину роботи можна перекласти на комп'ютер).

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

Формулювання леми

Для формулювання леми нам потрібне ще одне означення з алгебри. Нерухома точка $f$ для перестановки $\pi$ — це елемент, який є інваріантним щодо цієї перестановки: $f \equiv f \pi$. Наприклад, у нашому прикладі нерухомими точками є ті функції $f$, які відповідають розфарбуванням, що не змінюються при застосуванні до них перестановки $\pi$ (тобто вони не змінюються у формальному сенсі рівності функцій). Позначимо через $I(\pi)$ кількість нерухомих точок для перестановки $\pi$.

Тоді лема Бернсайда звучить так: кількість класів еквівалентності дорівнює сумі кількостей нерухомих точок щодо всіх перестановок із групи $G$, поділеній на розмір цієї групи:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

Хоча сама лема Бернсайда не така зручна для використання на практиці (незрозуміло, як швидко шукати значення $I(\pi)$), вона найчіткіше розкриває математичну суть, на якій ґрунтується ідея обчислення класів еквівалентності.

Доведення леми Бернсайда

Наведене тут доведення леми Бернсайда не є важливим для практичних застосувань, тому його можна пропустити при першому читанні.

Це доведення — найпростіше з відомих, і воно не використовує теорії груп. Доведення опублікував Kenneth P. Bogart у 1991 році.

Нам треба довести таке твердження:

$$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

Значення у правій частині — це не що інше, як кількість «інваріантних пар» $(f, \pi)$, тобто пар таких, що $f \pi \equiv f$. Очевидно, що ми можемо змінити порядок підсумовування. Нехай сума пробігає по всіх елементах $f$, і ми підсумовуємо значення $J(f)$ — кількість перестановок, для яких $f$ є нерухомою точкою.

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Щоб довести цю формулу, ми складемо таблицю зі стовпцями, позначеними всіма функціями $f_i$, і рядками, позначеними всіма перестановками $\pi_j$. А клітинки заповнимо значеннями $f_i \pi_j$. Якщо ми поглянемо на стовпці цієї таблиці як на множини, то деякі з них збігатимуться, а це означає, що відповідні функції $f$ для цих стовпців також еквівалентні. Таким чином, кількість різних (як множин) стовпців дорівнює кількості класів. До речі, з погляду теорії груп, стовпець, позначений $f_i$, є орбітою цього елемента. Для еквівалентних елементів орбіти збігаються, і кількість орбіт дає рівно кількість класів.

Отже, стовпці таблиці розкладаються на класи еквівалентності. Зафіксуймо клас і поглянемо на стовпці в ньому. По-перше, зауважимо, що ці стовпці можуть містити лише елементи $f_i$ класу еквівалентності (інакше деяка перестановка $\pi_j$ перемістила б одну з функцій до іншого класу еквівалентності, що неможливо, оскільки ми розглядаємо лише інваріантні перестановки). По-друге, кожен елемент $f_i$ траплятиметься однакову кількість разів у кожному стовпці (це теж випливає з того, що стовпці відповідають еквівалентним елементам). Звідси можемо зробити висновок, що всі стовпці в межах одного класу еквівалентності збігаються між собою як мультимножини.

Тепер зафіксуймо довільний елемент $f$. З одного боку, він трапляється у своєму стовпці рівно $J(f)$ разів (за означенням). З іншого боку, усі стовпці в межах одного класу еквівалентності однакові як мультимножини. Тому в межах кожного стовпця даного класу еквівалентності будь-який елемент $g$ трапляється рівно $J(g)$ разів.

Отже, якщо ми довільно візьмемо по одному стовпцю з кожного класу еквівалентності та підсумуємо кількість елементів у них, то отримаємо, з одного боку, $|\text{Classes}| \cdot |G|$ (просто помноживши кількість стовпців на кількість рядків), а з іншого боку — суму величин $J(f)$ для всіх $f$ (це випливає з усіх попередніх міркувань):

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Теорема Поя

Теорема Поя є узагальненням леми Бернсайда, і вона також дає зручніший інструмент для знаходження кількості класів еквівалентності. Слід зазначити, що цю теорему ще до Поя відкрив Редфілд у 1927 році, але його публікація лишилася непоміченою математиками. Поя незалежно дійшов тих самих результатів у 1937 році, і його публікація мала більший успіх.

Тут ми обговоримо лише частковий випадок теореми Поя, який виявиться дуже корисним на практиці. Загальна формула теореми обговорюватися не буде.

Позначимо через $C(\pi)$ кількість циклів у перестановці $\pi$. Тоді виконується наступна формула (частковий випадок теореми Поя):

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$$

$k$ — це кількість значень, які може приймати кожен елемент представлення; у випадку розфарбовування бінарного дерева це було б $k = 2$.

Доведення

Ця формула є прямим наслідком леми Бернсайда. Щоб її отримати, нам лише треба знайти явний вираз для $I(\pi)$, який фігурує в лемі. Нагадаємо, що $I(\pi)$ — це кількість нерухомих точок у перестановці $\pi$.

Отже, розгляньмо перестановку $\pi$ і деякий елемент $f$. Під час застосування $\pi$ елементи в $f$ переміщуються вздовж циклів перестановки. Оскільки в результаті має вийти $f \equiv f \pi$, елементи, яких торкається один цикл, мають бути всі рівні. Водночас різні цикли незалежні. Таким чином, для кожного циклу перестановки $\pi$ ми можемо обрати одне значення (серед $k$ можливих), і так ми отримуємо кількість нерухомих точок:

$$I(\pi) = k^{C(\pi)}$$

Застосування: розфарбовування намист

Задача «Намисто» — одна з класичних комбінаторних задач. Завдання полягає в тому, щоб підрахувати кількість різних намист із $n$ намистин, кожну з яких можна пофарбувати в один із $k$ кольорів. Порівнюючи два намиста, їх можна обертати, але не перевертати (тобто дозволено циклічний зсув).

У цій задачі ми можемо одразу знайти групу інваріантних перестановок:

$$\begin{align} \pi_0 &= 1 2 3 \dots n\\ \pi_1 &= 2 3 \dots n 1\\ \pi_2 &= 3 \dots n 12\\ &\dots\\ \pi_{n-1} &= n 1 2 3\dots\end{align}$$

Знайдімо явну формулу для обчислення $C(\pi_i)$. Спершу зауважимо, що перестановка $\pi_i$ має на $j$-й позиції значення $i + j$ (взяте за модулем $n$). Якщо перевірити циклічну структуру для $\pi_i$. Ми бачимо, що $1$ переходить у $1 + i$, $1 + i$ переходить у $1 + 2i$, який переходить у $1 + 3i$ і так далі, доки ми не дійдемо до числа виду $1 + k n$. Аналогічні твердження можна зробити і для решти елементів. Звідси бачимо, що всі цикли мають однакову довжину, а саме $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$. Таким чином, кількість циклів у $\pi_i$ дорівнюватиме $\gcd(i, n)$.

Підставивши ці значення в теорему Поя, отримуємо розв'язок:

$$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$$

Можна лишити цю формулу в такому вигляді, а можна спростити її ще більше. Перетворімо суму так, щоб вона пробігала по всіх дільниках $n$. У початковій сумі буде багато еквівалентних доданків: якщо $i$ не є дільником $n$, то такий дільник можна знайти, обчисливши $\gcd(i, n)$. Тому для кожного дільника $d ~|~ n$ його доданок $k^{\gcd(d, n)} = k^d$ з'явиться в сумі кілька разів, тобто відповідь до задачі можна переписати як

$$\frac{1}{n} \sum_{d ~|~ n} C_d k^d,$$

де $C_d$ — кількість таких чисел $i$, для яких $\gcd(i, n) = d$. Ми можемо знайти явний вираз для цієї величини. Будь-яке таке число $i$ має вигляд $i = d j$ з $\gcd(j, n / d) = 1$ (інакше $\gcd(i, n) > d$). Тож ми можемо підрахувати кількість $j$ із такою поведінкою. Функція Ейлера дає нам результат $C_d = \phi(n / d)$, і тому ми отримуємо відповідь:

$$\frac{1}{n} \sum_{d ~|~ n} \phi\left(\frac{n}{d}\right) k^d$$

Застосування: розфарбовування тора

Доволі часто ми не можемо отримати явну формулу для кількості класів еквівалентності. У багатьох задачах кількість перестановок у групі може бути надто великою для ручних обчислень, і неможливо аналітично обчислити кількість циклів у них.

У такому разі нам слід вручну знайти кілька «базових» перестановок, щоб вони могли породити всю групу $G$. Далі ми можемо написати програму, яка згенерує всі перестановки групи $G$, підрахує кількість циклів у них і обчислить відповідь за формулою.

Розгляньмо приклад задачі про розфарбовування тора. Є картатий аркуш паперу $n \times m$ ($n < m$), деякі клітинки чорні. Потім з цього аркуша отримують циліндр, склеївши дві сторони довжиною $m$. Потім із циліндра отримують тор, склеївши два кола (верхнє і нижнє) без перекручування. Завдання — обчислити кількість різних розфарбованих торів, припускаючи, що ми не бачимо ліній склеювання, а тор можна повертати і перевертати.

Ми знову починаємо з аркуша паперу $n \times m$. Легко бачити, що наступні типи перетворень зберігають клас еквівалентності: циклічний зсув рядків, циклічний зсув стовпців і поворот аркуша на 180 градусів. Так само легко бачити, що ці перетворення можуть породити всю групу інваріантних перетворень. Якщо ми якось пронумеруємо клітинки паперу, то зможемо записати три перестановки $p_1$, $p_2$, $p_3$, що відповідають цим типам перетворення.

Далі лишається тільки згенерувати всі перестановки, отримані як добуток. Очевидно, що всі такі перестановки мають вигляд $p_1^{i_1} p_2^{i_2} p_3^{i_3}$, де $i_1 = 0 \dots m-1$, $i_2 = 0 \dots n-1$, $i_3 = 0 \dots 1$.

Таким чином, ми можемо записати реалізацію цієї задачі.

C++

using Permutation = vector<int>;

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation p(n*m), p1(n*m), p2(n*m), p3(n*m);
    for (int i = 0; i < n*m; i++) {
        p[i] = i;
        p1[i] = (i % n + 1) % n + i / n * n;
        p2[i] = (i / n + 1) % m * n + i % n;
        p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}

Python

# Перестановка — це список цілих: позиція i переходить у p[i].
def multiply(p, q):
    # Композиція: (p * q)[i] = p[q[i]].
    return [p[q[i]] for i in range(len(p))]


def count_cycles(p):
    n = len(p)
    visited = [False] * n
    cnt = 0
    for i in range(n):
        if not visited[i]:
            cnt += 1
            j = i
            while not visited[j]:
                visited[j] = True
                j = p[j]
    return cnt


def solve(n, m):
    # Нумеруємо клітинки аркуша n x m, будуємо три базові перестановки.
    p = list(range(n * m))
    p1 = [(i % n + 1) % n + i // n * n for i in range(n * m)]            # зсув рядків
    p2 = [(i // n + 1) % m * n + i % n for i in range(n * m)]            # зсув стовпців
    p3 = [(m - 1 - i // n) * n + (n - 1 - i % n) for i in range(n * m)]  # поворот на 180

    # Генеруємо всю групу як p1^i1 * p2^i2 * p3^i3, зберігаючи унікальні (кортежі).
    s = set()
    cur = p
    for _ in range(n):
        for _ in range(m):
            for _ in range(2):
                s.add(tuple(cur))
                cur = multiply(cur, p3)
            cur = multiply(cur, p2)
        cur = multiply(cur, p1)

    # Теорема Поя: сума k^C(pi) для всіх pi, поділена на розмір групи (k = 2).
    total = sum(1 << count_cycles(list(perm)) for perm in s)
    return total // len(s)

TypeScript

// Перестановка — це масив чисел: позиція i переходить у p[i].
type Permutation = number[];

function multiply(p: Permutation, q: Permutation): Permutation {
    // Композиція: (p * q)[i] = p[q[i]].
    return q.map((qi) => p[qi]);
}

function countCycles(p: Permutation): number {
    const visited = new Array(p.length).fill(false);
    let cnt = 0;
    for (let i = 0; i < p.length; i++) {
        if (!visited[i]) {
            cnt++;
            let j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = p[j];
            }
        }
    }
    return cnt;
}

function solve(n: number, m: number): number {
    // Нумеруємо клітинки аркуша n x m, будуємо три базові перестановки.
    const N = n * m;
    const idx = Array.from({ length: N }, (_, i) => i);
    let cur: Permutation = idx;
    const p1 = idx.map((i) => ((i % n) + 1) % n + Math.floor(i / n) * n);            // зсув рядків
    const p2 = idx.map((i) => ((Math.floor(i / n) + 1) % m) * n + (i % n));          // зсув стовпців
    const p3 = idx.map((i) => (m - 1 - Math.floor(i / n)) * n + (n - 1 - (i % n)));  // поворот на 180

    // Генеруємо всю групу й зберігаємо унікальні перестановки (як рядки-ключі).
    const s = new Set<string>();
    for (let i1 = 0; i1 < n; i1++) {
        for (let i2 = 0; i2 < m; i2++) {
            for (let i3 = 0; i3 < 2; i3++) {
                s.add(cur.join(","));
                cur = multiply(cur, p3);
            }
            cur = multiply(cur, p2);
        }
        cur = multiply(cur, p1);
    }

    // Теорема Поя: сума k^C(pi), поділена на розмір групи (k = 2).
    let total = 0;
    for (const k of s) {
        const perm = k.split(",").map(Number);
        total += 1 << countCycles(perm);
    }
    return Math.floor(total / s.size);
}

Go

// Перестановка — це зріз int: позиція i переходить у p[i].
type Permutation []int

func multiply(p, q Permutation) Permutation {
    // Композиція: (p * q)[i] = p[q[i]].
    r := make(Permutation, len(p))
    for i := range q {
        r[i] = p[q[i]]
    }
    return r
}

func countCycles(p Permutation) int {
    visited := make([]bool, len(p))
    cnt := 0
    for i := range p {
        if !visited[i] {
            cnt++
            for j := i; !visited[j]; j = p[j] {
                visited[j] = true
            }
        }
    }
    return cnt
}

func key(p Permutation) string {
    var b strings.Builder
    for _, v := range p {
        fmt.Fprintf(&b, "%d,", v)
    }
    return b.String()
}

func solve(n, m int) int {
    // Нумеруємо клітинки аркуша n x m, будуємо три базові перестановки.
    N := n * m
    cur := make(Permutation, N)
    p1 := make(Permutation, N)
    p2 := make(Permutation, N)
    p3 := make(Permutation, N)
    for i := 0; i < N; i++ {
        cur[i] = i
        p1[i] = (i%n+1)%n + i/n*n           // зсув рядків
        p2[i] = (i/n+1)%m*n + i%n           // зсув стовпців
        p3[i] = (m-1-i/n)*n + (n - 1 - i%n) // поворот на 180
    }

    // Генеруємо всю групу, зберігаючи унікальні перестановки.
    s := make(map[string]Permutation)
    for i1 := 0; i1 < n; i1++ {
        for i2 := 0; i2 < m; i2++ {
            for i3 := 0; i3 < 2; i3++ {
                s[key(cur)] = cur
                cur = multiply(cur, p3)
            }
            cur = multiply(cur, p2)
        }
        cur = multiply(cur, p1)
    }

    // Теорема Поя: сума k^C(pi), поділена на розмір групи (k = 2).
    sum := 0
    for _, perm := range s {
        sum += 1 << countCycles(perm)
    }
    return sum / len(s)
}

Задачі для практики

• CSES - Counting Necklaces
• CSES - Counting Grids
• Codeforces - Buildings
• CS Academy - Cube Coloring
• Codeforces - Side Transmutations
• LightOJ - Necklace
• POJ - Necklace of Beads
• CodeChef - Lucy and Flowers
• HackerRank - Count the Necklaces
• POJ - Magic Bracelet
• SPOJ - Sorting Machine
• Project Euler - Pizza Toppings
• ICPC 2011 SERCP - Alphabet Soup
• GCPC 2017 - Buildings

Відеоматеріали