Лемма Бёрнсайда и Теорема Пойа
Определение: |
Классом эквивалентности | элемента называется подмножество элементов, эквивалентных .
Пусть нам дано множество всех представлений комбинаторного объекта, тогда для любого элемента из этого множества можно выделить подмножество(возможно, пустое),такое что все элементы этого подмножества будут эквивалентны . Следовательно, множество всех представлений разбивается на классы эквивалентности. Лемма Бёрнсайда позволяет посчитать в некотором множестве, основываясь на некоторой его внутренней симметрии, количество классов эквивалентности. Док-во этой леммы, приведенное ниже, опирается на следующие определения:
Определение: |
Инвариантная перестановка — такая перестановка, которая по условию задачи не меняет сам объект, а только его представление. |
Заметим, что произведение любых инвариантных перестановок тоже является инвариантной перестановкой.
Определение: |
Неподвижной точкой | для перестановки называется такой элемент, который инвариантен относительно этой перестановки.
Содержание
Лемма Бёрнсайда
Лемма (Бёрнсайд): |
Количество классов эквивалетности равно сумме количеств неподвижных точек по всем перестановкам из группы , делённой на размер этой группы:
. Где — количество неподвижных точек для перестановки . |
Доказательство: |
Рассмотрим сумму в числителе дроби справа: — это ничто иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества , а внутри нее поставить величину — количество перестановок, относительно которых объект инвариантен:
Теперь зафиксируем произвольный элемент . С одной стороны, он встречается в своём столбце ровно раз (по самому определению). С другой стороны, все столбцы внутри одного класса эквивалентности одинаковы как мультимножества. Следовательно, внутри каждого столбца данного класса эквивалентности любой элемент встречается ровно раз.Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, (это получается, просто умножив количество столбцов на их размер), а с другой стороны — сумму величин по всем (это следует из всех предыдущих рассуждений): |
Теорема Пойа
Лемма Бёрнсайда лежит в основе доказательства теоремы Пойа.
Теорема (Пойа): |
,где — кол-во различных классов эквивалентности, - кол-во циклов в перестановке , — кол-во различных состояний одного элемента. |
Доказательство: |
Для доказательства этой теорем достаточно установить следующее равенство
|