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

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

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

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

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

Доведення

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

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

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

$\sum _{x\in X}|G_x|=\sum _{x\in X}\frac{|G|}{|{\mathrm{orb}}_G(x)|}$

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

$\sum _{x\in B}\frac{1}{|{\mathrm{orb}}_G(x)|}=|B|\frac{1}{|B|}=1$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Література

• Шаблон:Курош.Теорія груп