577
правок
Изменения
Нет описания правки
Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}}
Иными словами, количество способов пометить вершины графа можно вычислить, зная количество и порядки групп помеченных графов, изоморфных друг другу (внутри одной группы). Например, для дерева-цепочки, состоящей из двух и более вершин, такая группа включает два элемента: тождественную перестановку и отражение относительно середины. Следовательно, ее порядок равен двум.
Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их <tex>16</tex>. Среди них <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}</tex>. Порядок группы <tex>\Gamma(P_{4})</tex>, как было сказано выше, равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>, то имеем <tex dpi = "160">\frac{4!}{|\Gamma(P_{4})|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\Gamma(K_{1, 3})|} = 4</tex>.
{| cellpadding="2"
| || [[Файл:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]
|}
== Теорема перечисления Пойа ==
