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

раз складаємо число з самим собою). Тому кількість орбіт можна обчислити за формулою . Підставивши сюди формулу для довжини орбіти, отримаємо . Використовуючи формулу із зауваження1, отримаємо , що й потрібно було довести. 

Теорема 8. (ваговий вигляд)

де - вага орбіти  (вага будь-якого його представника), - вага елемента.

 

Перш ніж розв’язати «задачу про намиста» нам потрібно сформулювати та довести теорему Рефілдера-Пойа, на основі якої ґрунтується розв’язання. В свою чергу доведення цієї теореми ґрунтується на основі леми Бернсайда.

  1. Теорема Рефілдера-Пойа

Означення 10. Нехай:

— група підстановок на множині

— скінчена група підстановок на зліченій множині Y, що містить не менше двох елементів;

— вагова функція, визначена на Y, зі значеннями у множині невід’ємних цілих чисел і така, що при довільному невід’ємному цілому j кількість cj його прообразів скінчена: .

Уведемо такі поняття.