Изменения

'''Инвариантная перестановка''' {{- --}} такая перестановка, которая по условию задачи не меняет сам объект, а только его представление.

<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>.

<tex>\sum\limits_{k \in G}I(k)</tex> — {{---}} это ни что иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> — {{---}} количество перестановок, относительно которых объект <tex>f</tex> инвариантен:

Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <tex>f_i</tex>, строки — {{---}} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения . Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет как означать, что соответствующие этим столбцам <tex>f</tex> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству различных комбинаторных объектов.

Cтолбцы Столбцы таблицы сами распадаются на комбинаторные обекты; зафиксируем теперь какой-либо объект и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <tex>f_i</tex> одного объекта (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой комбинаторный объект, что невозможно). Во-вторых, каждый элемент <tex>f_i</tex> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного комбинаторного объекта совпадают друг с другом как мультимножества.

Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а с другой стороны — {{---}} сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):

|statement= <tex> C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{k \in G} l^{P(k)}</tex> ,где <tex>C</tex> {{- --}} кол-во различных комбинаторных объектов, <tex>P(k) </tex> - кол-во циклов в перестановке <tex>k</tex>, <tex>l</tex>{{--- }} кол-во различных состояний одного элемента.

Пусть нам даны бусинки <tex>k </tex> различных цветов, а ожерелье должно состоять из <tex>n </tex> бусинок.

где С <tex>C</tex> - кол-во различных ожерелий,которые можно составить из <tex>n </tex> бусинок <tex>k </tex> различных цветов.