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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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


Твердження леми[ред.ред. код]

Нехай 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|}{|\operatorname{orb}_G(x)|}

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

\sum_{x \in B} \frac{1}{|\operatorname{orb}_G(x)|} = |B| \frac{1}{|B|} = 1

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

\sum_{x \in X} \frac{1}{|\operatorname{orb}_G(x)|} = |X/G|

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

\sum_{g \in G} |X^g| = |G|\cdot|X/G| \Leftrightarrow |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|,

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

Приклад застосування[ред.ред. код]

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

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

Куб з кольоровими гранями
  • одиничний елемент при кому усі 36 елементів X залишаються незмінними
  • шість поворотів на 90 градусів навколо осей, що з'єднують центри протилежних граней, при кожному 33 елементів X залишаються незмінними
  • три повороти на 180 градусів навколо осей, що з'єднують центри протилежних граней, при кожному 34 елементів X залишаються незмінними
  • вісім поворотів на 120 градусів навколо осей, що з'єднують протилежні вершини, при кожному 32 елементів X залишаються незмінними
  • шість поворотів на 180 градусів навколо осей, що з'єднують центри протилежних ребер, при кожному 33 елементів X залишаються незмінними

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

 \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 кольорів, то справедлива формула:

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

Література[ред.ред. код]