Определение: Подстановка р:Х→Х={1,2,…,n} сохраняет элемент а (а есть неподвижная точка подстановки р), если р(а)=а.

Стабилизатор элемента а из Х группы G есть множество G_a = {p∈G: p(a) = a} всех подстановок, сохраняющих элемент а.

Замечание: Стабилизатор Ga есть группа.

Утверждение: Длина орбиты А(а) равна индексу стабилизатора G(a) в группе G, то есть мощность |A(a)|=|G|/|Ga|.
Без доказательства.

Лемма (Бернсайда): Если 1) X={1,2,…,n}; 2) G= {p₀ =e, p₁, …, p_r-1} есть группа подстановок на множестве Х; 3) χ(p) есть число фиксированных точек подстановки р, тогда число орбит группы подстановок G равно f(G) = |G|^-1∑_p∈G χ(p).

Доказательство: Изобразим отношение «m есть фиксированный элемент подстановки р».

На каждой вертикали p_i звездочкой отмечены неподвижные точки подстановки p_i. Их число равно χ(p_i). При вычислении по вертикалям число звезд (неподвижных точек) равно: χ(p₀) + χ(p₁) + … + χ(p_r-1) = ∑χ_p∈G(p_i) . На каждой горизонтали m отмечены все подстановки, сохраняющие элемент m. Эти подстановки образуют стабилизатор Gm, который есть группа, и по предыдущему утверждению |A(m)| = |G|/|G_m|, откуда |G_m|=|G|/|A(m)|. При вычислении по горизонтали число звезд на диаграмме равно |G₁| + |G₂| + … + |G_n| = ∑_{m ∈X}|G_m|. Множество Х разбивается в объединение попарно непересекающихся орбит. X = O₁ ∪ O₂ ∪ … ∪ O_t, где t=f(G) есть число орбит. Перегруппируем слагаемые предыдущей суммы относительно элементов орбит и получим:

∑_m∈O|G_m| = ∑_m∈O1|G_m| + … + ∑_m∈Ot|G_m|.

Если m∈O включение верно для орбиты O, то O=А(m), тогда каждое слагаемое предыдущей суммы:

∑_m∈O|G_m| = ∑_m∈O|G|/|A(m)| = ∑_m∈X|G|/|O| = |G|/|O|∑_m∈X1 = |G|/|O| |O| = |G|

Тогда вся сумма: ∑_m∈O|G_m| = |G| + … + |G| = t|G| = f(G)|G|.

Число звездочек, вычисленных по горизонтали и вертикали, совпадает. Следовательно, сумма ∑χ_p∈G = f(G)|G|, откуда число орбит группы G: f(G) = |G|^-1 ∑χ_p∈G. Лемма доказана.

Комментарии запрещены.