577
правок
Изменения
→Теорема перечисления Пойа
|proof=
Уже упоминалось о том, что порядок <tex>|A|</tex> группы <tex>A</tex> равен <tex>|A(x)| \cdot |\Theta(x)|</tex> для любого <tex>x \in X</tex>, где <tex>A(x)</tex> {{---}} стабилизатор элемента <tex>x</tex>. Так как весовая функция постоянна на элементах данной орбиты, то справедливо равенство <tex>|\Theta_{i}| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}\omega(x)</tex> для каждой орбиты <tex>\Theta_{i}</tex>. Домножив второе равенство на первое и сократив, получаем <tex>|A| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>. Суммируя по всем орбитам, находим <tex>|A|\sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{i=1}^n \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>, откуда непосредственно следует доказываемое соотношение.
}}
Как следствие из этой теоремы выведем традиционную формулу Бернсайда. Для подстановки <tex>\alpha</tex> через <tex>j_{k}(\alpha)</tex> обозначим число циклов длины <tex>k</tex> в её разложении в произведение непересекающихся циклов.
{{Лемма
|author=Бернсайд
|statement=
Число <tex>N(A)</tex> орбит группы подстановок <tex>A</tex> равно <tex>N(A) = \frac{1}{|A|}\sum\limits_{\alpha \in A}j_{1}(\alpha)</tex>.
|proof=
Так как в доказательстве этой леммы мы не учитываем значения весовой функции, то <tex>|A|N(A) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x}1</tex>, но <tex>\sum\limits_{x = \alpha x}1</tex> и есть <tex>j_{1}(\alpha)</tex>, то есть для получения исходной формулы нужно поделить обе части равенства на <tex>|A|</tex>.
}}
