Лема бернсайда. задача про намиста
21

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

  1. Задача про намиста

Задача.

Знайти кількість намист, що складаються з n бусинок двох кольорів. Намиста, що співпадають при повороті, вважаються однаковими.

Розвязання

Нехай множина відповідає номерам бусинок в намисті, а - множині можливих кольорів. Вагову функцію . В множині існує один елемент ваги нуль і один ваги один, тобто і .

Звідки слідує, що .

Нехай - множина всіх функцій з в . Будь-яка функція задає деяке намисто, і навпаки, кожне намисто задається деякою функцією з . При цьому вага функції рівна кількості бусинок кольору 1, у відповідному намисті.

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

Цикловий індекс групи рівний   , де - функція Ейлера, - НСД(); - дільник .