3622
правки
Изменения
Нет описания правки
|statement=Количество комбинаторных объектов равно сумме количеств неподвижных точек по всем перестановкам из группы <tex>G</tex> , делённой на размер этой группы:
<tex> C =</tex><tex dpi = "180">\frac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>. Где <tex>I(k)</tex> - количество неподвижных точек для перестановки <tex>k</tex>.
|proof=
Рассмотрим сумму в числителе дроби справа:
<tex >C =</tex><tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а с другой стороны — сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):
<tex> C =</tex><tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
}}
|id=teorPo.
|author=Пойа
|statement= <tex> C =</tex><tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{k \in G} l^{P(k)}</tex> ,где <tex>C</tex> - кол-во различных комбинаторных объектов, P(k) - кол-во циклов в перестановке <tex>k</tex>, <tex>l</tex>- кол-во различных состояний одного элемента.
|proof=Для доказательства этой теорем достаточно установить следующее равенство
<tex>I(k) = l^{P(k)}</tex>
<tex>C =</tex><tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{l \in G} k^{P(l)}</tex>
Очевидно, что для каждой перестановки длины <tex>n</tex> существует ровно <tex>n</tex> циклических сдвигов, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i + l)\mod n</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i \in [1; k]</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>lcm(n, i)/i = n/gcd(i,n)</tex>.Откуда следует что:
<tex>C =</tex><tex dpi = "180"> \frac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</tex>.
