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

У математиці і зокрема в теорії груп і комбінаториці лема Бернсайда  — результат, що визначає кількість орбіт при дії певної групи на деякій множині. Часто також використовуються назви обчислювальна теорема Бернсайда, лема Коші-Фробеніуса. Названа на честь англійського математика Вільяма Бернсайда, хоча була відома і до нього.

Твердження леми

Нехай ${\displaystyle G}$  — скінченна група, що діє на деякій множині ${\displaystyle X}$. Для кожного ${\displaystyle g\in G}$ позначимо ${\displaystyle X^{g}=\{x\in X|gx=x\}}$. Лема Бернсайда дає формулу числа орбіт групи ${\displaystyle G}$, що позначається ${\displaystyle |X/G|}$:

${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.}$

Доведення

Спершу використовуючи два способи обчислення маємо:

${\displaystyle \sum _{g\in G}|X^{g}|=|\{(g,x)\in G\times X:g\cdot x=x\}|=\sum _{x\in X}|G_{x}|}$

де ${\displaystyle G_{x}}$  - стабілізатор елемента x. Далі враховуючи, що кількість елементів групи G рівна добутку кількості елементів стабілізатора і орбіти x можна записати:

${\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|\operatorname {orb} _{G}(x)|}}}$

розглянувши окремо деяку орбіту B, в множині X одержуємо:

${\displaystyle \sum _{x\in B}{\frac {1}{|\operatorname {orb} _{G}(x)|}}=|B|{\frac {1}{|B|}}=1}$

зважаючи, що X є об'єднанням таких орбіт звідси випливає:

${\displaystyle \sum _{x\in X}{\frac {1}{|\operatorname {orb} _{G}(x)|}}=|X/G|}$

знову пригадуючи інший спосіб обчислення остаточно одержуємо:

${\displaystyle \sum _{g\in G}|X^{g}|=|G|\cdot |X/G|\Leftrightarrow |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|,}$

що завершує доведення.

Приклад застосування

Формула Бернсайда може бути використана для обчислення незалежних від поворотів розфарбувань граней куба.

Нехай X множина всіх 3^6 можливих розфарбувань граней куба в три кольори, а G  - група поворотів куба, що діє на X. Два елементи X належать до однієї орбіти, якщо один одержується з іншого за допомогою деякого повороту. Тож для обрахунку різних кубів треба обчислити кількість орбіт у множині X під дією групи G. Для цього визначимо кількість незмінних елементів для кожного з 24 поворотів і використаємо лему Бернсайда.

Куб з кольоровими гранями

• одиничний елемент при якому усі 3^6 елементів X залишаються незмінними
• шість поворотів на 90 градусів навколо осей, що з'єднують центри протилежних граней, при кожному 3^3 елементів X залишаються незмінними
• три повороти на 180 градусів навколо осей, що з'єднують центри протилежних граней, при кожному 3^4 елементів X залишаються незмінними
• вісім поворотів на 120 градусів навколо осей, що з'єднують протилежні вершини, при кожному 3^2 елементів X залишаються незмінними
• шість поворотів на 180 градусів навколо осей, що з'єднують центри протилежних ребер, при кожному 3^3 елементів X залишаються незмінними

Тому згідно з формулою Бернсайда:

${\displaystyle {\frac {1}{24}}\left(3^{6}+6\times 3^{3}+3\times 3^{4}+8\times 3^{2}+6\times 3^{3}\right)=57.}$

Отже, загальна кількість різних з урахуванням поворотів кубів, грані яких розфарбовані в три кольори, рівна 57. Загалом, якщо грані розфарбовані в n кольорів, то справедлива формула:

${\displaystyle {\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right)}$

Література

• Курош А. Г. Теория групп. — 3-е изд. — Москва : Наука, 1967. — 648 с. — ISBN 5-8114-0616-9.(рос.)