Изменения

  {{Определение|definition='''Классом эквивалентности''' <tex>C(a)</tex> элемента <tex>a</tex> называется подмножество элементов, эквивалентных <tex>a</tex>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.}} '''Пример''':Пусть нам дана циклическая перестановка <tex>a = \{0Если это отношение является отношением "с точностью до действия элементом группы", 1, 2, 3\}</tex>.то такой подсчет можно провестиТогда <tex>C(a) = \{\{0, 1, 2, 3\}, \{3, 0, 1, 2\}, \{2, 3, 0, 1\}, \{1, 2, 3, 0\}\}</tex>  Пусть нам дано множество всех представлений комбинаторного объекта, тогда для любого элемента <tex>a</tex> из этого множества можно выделить подмножество(возможно, пустое),такое что все элементы этого подмножества будут эквивалентны <tex>a</tex>. Следовательно, множество всех представлений разбивается на классы эквивалентностис помощью Леммы Бернсайда. Лемма Бёрнсайда позволяет посчитать в некотором множестве, основываясь на некоторой его внутренней симметрии, количество классов эквивалентности. Док-во этой леммы, приведенное ниже, опирается на следующие определения:

Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. '''Инвариантная перестановкаНеподвижной точкой''' {{---}} такая перестановкадля элемента <tex>g</tex> называется такой элемент <tex>x</tex>, которая по условию задачи не меняет сам объект, а только его представлениедля которого <tex>gx=x</tex>.

|statement=Количество Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Тогда число классов эквивалетности эквивалентности равно сумме количеств числа неподвижных точек по всем перестановкам из элементам группы <tex>G</tex> , делённой на размер этой группы:

<tex> C = </tex> <tex dpi = "180">\frac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>. Где <tex>I(k)</tex> {{---}} количество неподвижных точек для перестановки элемента <tex>k</tex>.