7.9. Теория перечисления Пойа

Введем следующие обозначения.

конечное множество.

конечная группа, действующая на конечное множество качественных признаков (цвета). множество функций; каждая функция/определяет качественные признаки элементов множество весов. весовая функция, назначает веса признакам — сумма весов элементов или , где число элементов с весом множество перечень относительно весовой функции

Рассмотрим введенные понятия на следующем примере, к которому ниже не раз будем возвращаться. Пусть вершины правильного треугольника (рис. 7.4). Треугольник нанизан на вертикальную ось, вокруг которой он свободно вращается. множество из двух красок. Найти количество различных раскрасок вершин треугольника.

Рис. 7.4

На действует группа самосовмещений где тождественное совмещение, а поворот вокруг оси на поворот на 240°.

и их произведения) - множество весов.

множество раскрасок. В треугольнике три вершины и каждую допускается окрашивать в любой из двух цветов следовательно, всего функций 23. Такое количество раскрасок будет, если треугольник сделать неподвижным (рис. 7.4). Если допустить вращение, то различные раскраски неподвижного треугольника становятся одинаковыми для вращающегося треугольника. Приведем пример трех раскрасок:

Очевидно, что для решаемой задачи раскраски совпадают.

Назначим краскам веса: и

Замечание. Отметим, что назначенные веса элементов и со позволяют сравнивать признаки количественно, забывая, в какой то степени, о качественном их содержании.

• Определение. Для каждой функции определим вес

В нашем примере

Определение. Группа действуя на индуцирует (наводит, создает, определяет) свое действие на множество функций Положим это рассматривается

В нашем примере рассмотрим действие элемента на

Таким образом, элемент группы а переводит или, в принятых обозначениях,

Определение. Положим если Такие определяют одинаковые раскраски элементов

Рис. 7.5

Введенная эквивалентность функций есть отношение эквивалентности, которое порождает разбиение множества элементов на непересекающиеся классы эквивалентности (рис. 7.5): где количество классов эквивалентности. Каждый класс эквивалентности определяет отдельную раскраску элементов Таким образом, количество различных раскрасок равно Для определения воспользуемся леммой

7.7.1 Бернсайда: в данном случае

Вернемся к нашему примеру на рис. 7.4 и найдем для него число удовлетворяют откуда это такие раскраски вершин, которые допускают совмещение с эквивалентной из раскрасок вращением треугольника на 120°. Это возможно, если все вершины либо белые, либо черные. Итак, Подобным образом устанавливается, что и Следовательно,

Утверждение 7.9.1. Если то т.е. эквивалентные функции имеют одинаковые веса. Доказательство. верно так как действует на это

подстановка. Теперь Имеем тогда Отсюда

Определение. Последнее утверждение позволяет определить вес каждого класса эквивалентности в разложении как где Определение корректно, так как каждый класс состоит из эквивалентных функций веса которых совпадают.

• Теорема 7.9.1 Пойа. где число классов эквивалентности с весом со цикловой индекс группы действующей на множестве Отметим, что

Доказательство. Пусть разбиение множества на непересекающиеся подмножества:

где

• Определение. Говорят, подчинена разбиению множества и записывают если постоянна на каждом подмножестве из разбиения: где . Функция подчиненная разбиению взаимно однозначно определяется набором где

Все такие наборы составляют множество:

где Полагая веса элементов равными и вес

равным произведению весов имеем где подчинена разбиению.

Для множества выполнены все условия правила обобщенного произведения, тогда сумма весов элементов данного множества, а значит, и сумма весов всех функций составит вследствие Следовательно, или

Пусть разложение на независимые циклы, где характеристиками Запишем разложение на независимые циклы в виде

где цикл длины

Обозначим разбиение множества на через Элементы одного цикла при умножении на переходят последовательно по циклу в элементы того же цикла. Указанное свойство позволяет заключить, что

Пример. Пусть тогда

Определение. Функция называется неподвижной относительно если

Утверждение 7.9.2. Функция неподвижна относительно тогда и только тогда, когда подчинена разбиению

Доказательство. Пусть принадлежат одному циклу. Следовательно, Тогда где каждый переход

обусловлен неподвижностью Таким образом,

Пусть тогда и свойство циклов. Имеем или следовательно, тогда есть неподвижная относительно

Запишем сумму весов подчиненных разбиению в следующем виде где количество функций, подчиненных разбиению с весом

Составим множество всех функций, неподвижных относительно с весом Утверждение 7.9.2 позволяет записать Величина число классов эквивалентности с весом на которые распадается множество функций под действием группы По лемме Бернсайда, Умножив последнее равенство на и просуммировав по всем весам из получим, что

Сумма сумма весов функций, подчиненных разбиению

Так как