Изменения

Пусть есть <tex>n</tex> сколь угодно много бусинок <tex>m</tex> разных сортов, . Необходимо найти число различных ожерелий длинны <tex>n_in</tex> назовем количество бусинок <tex>i</tex>ого цвета<tex>(i \in [1;m])</tex> (так же для удобства будем называть <tex>n_i</tex> цвет, цвет которому соответствует данное число бусин). Найти число ожерелий которые можно составить из этих бусинок. Ожерелья , полученные поворотом друг из друга поворотом или отражением , считаются одним ожерельемодинаковыми.

Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного <tex>n</tex>-угольника вершины которого окрашены в цветов, а количество вершин каждого цвета равно <tex>n_im</tex>цветов. Две расскраски раскраски считаются разными, если из одной нельзя получить другую с помощью симметрии или вращения. Пусть <tex>M</tex> — множество всех возможных окрасок <tex>n</tex>угольника, <tex>D</tex> — группа симметрий <tex>n</tex>угольника, состоящая из <tex>2n</tex> преобразований. Группа <tex>G</tex> определяет группу перестановок на множестве <tex>M</tex>. Пусть <tex> d \in D</tex> — некое преобразование симметрии <tex> \Rightarrow </tex> для любого многоугольник <tex>x \in M</tex> можно сопоставить многоугольник получаемый из него симметрией <tex>d</tex>. Назовем сопоставление этой перестановки <tex>d'</tex>. Группу всех таких перестановок из <tex>D</tex> назовем <tex>D'</tex>. Два многоугольника будут считаться разными, если из одного невозможно получить другой какой-либо перестановкой <tex>d' \in D'</tex> (они содержаться на разных орбитах группы <tex>D'</tex> действующей на множестве <tex>M</tex>). Поэтому для получения количества различных раскрасок вершин <tex>n</tex>угольника достаточно найти количество орбит группы <tex>D'</tex> на множестве <tex>M</tex>. По лемме Бернсайда, для этого нужно посчитать число неподвижных точек каждой перестановки <tex> d' \in D'</tex>.

пусть Рассмотрим поворот <tex>kd</tex> — общий делитель на угол <tex>n_i</tex>ых<tex>(i k,\,k\in [10..mn-1]) \Rightarrow</tex> поворот (поворотом на угол <tex>a_1k</tex> мы называем поворот на "реальный" угол <tex>\frac { 2\pi k} { k n}</tex> оставит неподвижными ожерелья из ). Мы хотим найти число раскрасок, инвариантных относительно этого поворота. Такая раскраска должна быть инвариантна относительно и всей подгруппы <tex>G=\lbrace e,d,d^2,...,d^p\rbrace</tex>(<tex>p</tex> - порядок d). Это означает, что орбита вершины под действием <tex>kG</tex> одинаковых кусков длинны должна быть окрашена в один цвет. Очевидно, что это требование является не только необходимым, но и достаточным. То есть, инвариантных раскрасок столько же, сколько и раскрасок орбит. Пользуясь леммой Бернсайда, можно определить число орбит: неподвижные точки есть только у тождественного поворота, при этом их <tex>\frac {n} {k}</tex>штук. Каждый кусок состоит из Тогда число орбит равно <tex>\frac {n_i} { k } n/p</tex> бусен . Осталось найти число <tex>ip</tex>ого цвета- минимальное число, поэтому число неподвижных точек для поворота будет равно количеству способов расставить бусины при котором <tex>kp</tex> делится на <tex>\frac {n} {k}</tex> местах. Соответственно для перестановки В этом случае <tex>d'kp</tex> число неподвижных точек будет равно наименьшим числом, делящимся и на <tex>n</tex> и на <tex>k</tex>, поэтому <tex>tkp=\operatorname{lcm}(d'n,k)\Rightarrow p=P(\frac {n_1\operatorname{lcm}(n,k)} { k }, =\frac {n_2n} { k }, ..., \frac operatorname{n_mgcd} { (n,k )})</tex>, где . Тогда число орбит равняется <tex>Pn/p=\operatorname{gcd}(x_1n, x_2, ..., x_mk)</tex> — полиномиальные коэффициенты. рассмотрим поворот и число их раскрасок <tex> a_iN_k=m^{\operatorname{gcd}(n,k)}</tex> на угол . Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\frac sum_{k=0}^{2in-1}N_k=\pisum_{k=0}^{n-1} m^{\operatorname{gcd}(n,k)}</tex>, где . В последней сумме <tex> i \in [1..k]phi(n)</tex>. Количество его неподвижных точек равно количеству неподвижных точек слагаемых, для которых <tex>a_1\operatorname{gcd}(n,k)=1</tex>, если . Если же <tex> i\operatorname{gcd}(n,k)=q</tex> взаимно просто с , то <tex>\operatorname{gcd}(n/q,k/q)=1</tex>. Количество взаимно простых с Чтобы определить количество таких k, меньших n, нужно перебрать числа вида <tex>k=lq,\,0\leq l\leq n/q</tex>(не превосходящих и проверять их на условие <tex>1=\operatorname{gcd}(n/q,k/q)=\operatorname{gcd}(n/q,l)</tex>) — является функцией Эйлера . Таких чисел, очевидно, <tex>\phi(kn/q)</tex>. Пусть (по определению <tex>S\phi(n)</tex> — сумма по всем поворотам, тогда ). Поэтому сумму можно заменить: <tex>S= \sum_{k=0} \phi(k) \cdot P(\frac ^{n_1n-1} m^{ k }, \frac operatorname{n_2gcd} { (n,k )}, ..., =\frac sum_{n_m} { k q|n}\phi(n/q)</tex>, где k пробегает множество общих делителей <tex>n_1, n_2, ..., n_mm^q</tex>.  

<tex>n</tex> — нечетно. Тогда симметричные ожерелья существуют только если среди <tex>n_i/,(i \in [1..m])</tex> только одно число нечетное. Пусть <tex>n_1</tex> — нечетно, <tex>d</tex> — симметрия относительно оси, проходящей всех отражений проходят через некоторую вершину. Тогда неподвижными будут ожерелья, симметричные относительно оси проходящей через бусину цвета и для инвариантности мы должны выбрать <tex>n_1</tex>. По одной стороне от оси будут находится <tex> \frac {(n-1} { )/2 } </tex> бусин: <tex> \frac {n_1-+1} { 2 } </tex> бусин <tex>n_1 цветавершин и раскрасить, а остальные дополнить по симметрии. Для каждого отражения получаем <tex> \frac {n_i} m^{ 2 } </tex> бусин <tex>n_i</tex> цвета, где <tex>i \in [2.. m] \Rightarrow t(d')=P(\frac {n_1-n+1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })=P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }]),</tex> где <tex>[x]</tex> — целая часть числа <tex>x</tex>. Тогда такое Сумма же число неподвижных точек имеет каждая из по всем отражениям, которых <tex>n</tex> соответствующая таким симметриям. Пусть штук, <tex>S'</tex> — сумма числа всех неподвижных точек <tex>t(d')</tex> по всем отражениям: <tex>S'S_{ref}=n*m \cdot P([\frac {n_1} ^{ 2 }], [\frac {n_2n+1} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.

<tex>n</tex> — четно. ОжерельяТогда есть <tex>m/2</tex> осей, симметричные относительно оси проходящей между бусинамипроходящих через стороны <tex>n</tex>-угольника, существуют только если все для каждой <tex>n_i (i \in [1..m])^{n/2}</tex> четныеинвариантных раскрасок(половину точек раскрашиваем по желанию, половину дополняем по инвариантности). Если ось проходит через Для оставшихся <tex>m/2</tex> бусиныосей, проходящих через 2 точки, то симметричные ожерелья существуют только если все имеем инвариантных раскрасок(свободно выбирается <tex>n_i (i \in [n/2+1..m])</tex> четные '''или''' если только цвет) <tex>m^{n/2+1}</tex> из . Итоговая сумма по всем отражениям: <tex>n_i (i S_{ref}=nm^{n/2}\in [frac{1..+m])}{2}</tex> не четные. Рассмотрим оба случая:

''б)Пусть все'Итак:' <tex>n_i</tex> — ''четные''. Если <tex>d</tex> — симметрия относительно оси проходящей через 2 вершины, то неподвижными точками для <tex>d'</tex> будут симметричные ожерелья, у которых <tex>2</tex> бусины <tex>n_i (i \in [1..m])</tex> цвета расположены на данной оси. Их количество <tex>t(d')=P(\frac {n_1-2} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })+P(\frac {n_1} { 2 }, \frac {n_2-2} { 2 }, \frac {n_3} { 2 }, ..., \frac {n_m} { 2 })</tex><tex>+ ...+</tex><tex>P(\frac {n_1} { 2 }, ..., \frac {n_{m-1}} { 2 }, ..., \frac {n_m-2} { 2 })=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex> \frac {m} {2}</tex>. Если <tex>d</tex> — симметрия относительно оси, проходящей между бусинами, то количество неподвижных точек равно <tex>t(d')=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий также <tex> \frac {m} {2}</tex>. Поэтому <tex>S'=m \cdot P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.

'''Итак:''' Во всех случаях получились одинаковые формулы для сумм неподвижных точек по всем отражениямДля нечетного <tex>(S')n</tex>. По лемме Бернсайда : <tex>t(D')N= \frac {1} {2n} \cdot (S+S')= \frac {1} {2m} \cdot \sum_{kq|n} \phi(kn/q) \cdot P(m^q+\frac {n_1} m^{ k }, \frac {n_2} { k }, ..., \frac {n_m} { k })n+ \frac {1} {2} \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }]) </tex>. Это и будет количеством ожерелий. Если среди всех <tex>n_i (i \in [1..m])</tex> более 2 нечетных, то нет симметрий <tex>\Rightarrow S'=0, \, t(D')= \frac {1} {2m} \cdot \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })</tex>.