Изменения

{{Определение|definition=<tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex>, <tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{z_{1}}\}</tex> {{---}} множества из различных объектов. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{l}\}</tex> {{---}} количество объектов веса от <tex dpi="130">1</tex> до <tex dpi="130">l</tex> из <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{l}\}</tex> {{---}} соответственно для <tex dpi="130">B</tex>. }} В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество (то есть <tex dpi="130">w_{0}=1</tex>).  ==Последовательности(Seq)== {{Определение|definition=<tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex dpi="130">A</tex>. <tex dpi="150">S_{n}</tex> {{---}} '''количество последовательностей''' веса <tex dpi="130">n</tex>.}} 

Пусть <tex dpi="130150">AS_{n}=\sum\limits_{a_{i=1},a_^{2n}, \ldots ,a_w_{ni}\}</tex> S_{{--n-i}} множество из различных объектов, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов . Причем <tex dpi="130150">A</tex>, <tex dpi="130">WS_{0} =\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса .|proof=<tex dpi="130"">\S_{1 \ldots m\0}</tex>. Тогда '''количество последовательностей''' веса <tex dpi="130">n1</tex> можно вычислить , так как:есть единственный способ составить пустую последовательность.

Докажем по индукции. '''База <tex dpi="150130"">n = 1</tex>'''. :<tex dpi="130"">S_{n1}=\sum_w_{i=1}^S_{n0} =w_{i1} S_</tex>, что верно, так как единственный способ составить последовательность веса <tex dpi="130"">1</tex> {{---}} это взять любой элемент веса <tex dpi="130"">1</tex>. '''Переход'''. :Пусть для <tex dpi="130"">j < n</tex> верно. Докажем для <tex dpi="130"">n</tex>. Возьмем произвольный элемент из <tex dpi="130"">A</tex> веса <tex dpi="130"">i \leqslant n</tex>, и допишем его к последовательности элементов веса <tex dpi="130"">n-i}</tex>. Образуется новая последовательность веса <tex dpi="130"">n</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса <tex dpi="130"">n</tex> и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.

Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]].

Тогда, <tex dpi="150">S_{n}=\sum_sum\limits\limits_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}</tex>.

Пусть <tex dpi="130">A=\{1, 2\}</tex>, <tex dpi="130">W=\{1, 1, 0 \ldots 0\}</tex>, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из маленьких и больших элементов , <tex dpi="130">SS_{1}=Seq(A)1</tex>.

Тогда, <tex dpi="150">S_{n}=\sum_sum\limits_{i=1}^{n} w_{i} S_{n-1i}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex dpi="150">F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.

===Подсчет подвешенных непомеченных деревьев с порядком на детях===Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">S=SeqМножества (APSet)</tex> {{---}} множество всех последовательностей из данных деревьев. <tex dpi="130">S_{n}</tex> {{---}} количество последовательностей с суммарным количество вершин <tex dpi="130">n</tex>. Чтобы получить дерево из <tex dpi="130">n</tex> вершин достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней последовательность деревьев с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда::<tex dpi="150">T_{n}=S_{n-1}</tex>.:<tex dpi="150">S_{n}=\sum_{i=1}^{n} T_{i} S_{n-i}=\sum_{i=1}^{n} S_{i-1} S_{n-i}=\sum_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]]

[[File:Ordered_Rooted_Trees.png{{Определение|700px]]definition=<tex dpi="130">P=МножестваPSet(PSetA)</tex> {{---}} множество всех множеств, составленных из элементов <tex dpi="130">A</tex>. <tex dpi="150">P_{n}</tex> {{---}} '''количество множеств''' суммарного веса <tex dpi="130">n</tex>.}}

Пусть <tex dpi="130150">AP_{n}=\p_{a_n, n}</tex>, где <tex dpi="150">p_{1n, k},a_=\sum\limits_{2i=0}, ^{\lfloor \ldots ,a_frac{n}{k}\rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}</tex> {{---}} множество из различных объектовколичество таких множеств, которые содержат объекты, вес которых не больше чем <tex dpi="150">k</tex>. Причем <tex dpi="130150">Sp_{0, i} =PSet(A)1</tex> , а <tex dpi="150">p_{{---i, 0}} множество всех множеств объектов= 0</tex>, составленных из элементов <tex dpi="130150"">Ai \ne 0</tex>, .|proof=<tex dpi="130">W=\p_{w_{1}0,w_{2i}= 1</tex>, \ldots так как не набирать никакой вес есть один способ,w_а <tex dpi="130">p_{k}\i, 0}= 0</tex> {{---}} количество объектов веса , <tex dpi="130"">i \{1 \ldots k\}ne 0</tex>, составленных так как нельзя набрать положительный вес из элементов ничего. Изначально у нас есть только пустое множество веса <tex dpi="130">A0</tex>, . Рассмотрим очередной этап вычисления <tex dpi="130">w_p_{0n,k} = 1</tex>. Тогда '''количество множеств''' из объектов суммарного веса Для данных <tex dpi="130">n</tex> можно вычислить как и <tex dpi="150130">S_{n}=s_{n, n}k</tex>у нас уже имеется множество, где которое необходимо дополнить. Мы можем сделать это добавляя от <tex dpi="150130">s_{n, k}0</tex> до <tex dpi=\sum_{i=0}^{"130">\lfloor \frac{n}{k} \rfloor} \binom{w_{</tex> элементов веса <tex dpi="130">k</tex> (при условии, что столько различных элементов имеется) в данное множество. Выбрать нужное количество элементов можно с помощью сочетаний. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше <tex dpi="130">k}}{i} s_{</tex> (чтобы избежать повторений) суммарного веса <tex dpi="130">n-ik</tex>, k-1}где <tex dpi="130">i</tex> {{---}} количество таких множеств, что они содержат объекты суммарного элементов веса <tex dpi="130">\leqslant k</tex>которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле.

===Количество PSet из элементов <tex>0</tex> или <tex>и 1</tex>===Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex>SP=PSet(A)</tex> {{---}} множество всех множеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда <tex dpi="150">S_P_{n}=s_p_{n, n}</tex>, где <tex tex dpi="150">s_p_{n, k}=\sum_sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_\binom{w_{k}}{i}p_{n-ik, k-1}</tex>. :<tex dpi="150">S_P_{0}=s_p_{0, 0} = 1</tex>.:<tex dpi="150">S_P_{1}=s_p_{1, 1} = s_\binom{2}{0}p_{1, 0} + 2s_\binom{2}{1}p_{0, 0} = 2s_2p_{0, 0} = 2</tex>.:<tex dpi="150">S_P_{2}=s_p_{2, 2} = s_\binom{0}{0} p_{2, 1} + \binom{0 \times s_}{1}p_{0, 1} = s_\binom{2}{0}p_{2, 0} + 2s_\binom{2}{1}p_{1, 0} + s_\binom{2}{2}p_{0, 0}= s_p_{0, 0} = 1</tex>.:<tex dpi="150">{S_P_{3}=s_p_{3, 3} = s_\binom{0}{0}p_{3, 2} + \binom{0 \times s_}{1} p_{0, 2} = s_\binom{0}{0}p_{3, 1} + \binom{0 \times s_}{1} p_{0, 1} = s_\binom{2}{0}p_{3, 0} + 2s_\binom{2}{1}p_{2, 0} + 0 \times s_binom{2}{2} p_{1, 0} + 0 \times s_binom{2}{3} p_{0, 0}= 0}</tex>.:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_P_{n} = 0</tex> .

Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">SP=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда, :<tex dpi="150">S_P_{n}=s_p_{n, n}</tex>, где <tex tex dpi="150">s_p_{n, k}=\sum_sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_p_{n-ik, k-1} = s_p_{n, k-1} + s_p_{n - k, k}</tex>, что, как не сложно несложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].

Пусть <tex dpi="130150">A=\M_{a_{1n},a_=m_{2}, \ldots n,a_{n}\}</tex> {{---}} множество из различных объектов, где <tex dpi="130150">Sm_{n, k}=MSet(A)\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}</tex> {{---}} множество всех количество таких мультимножеств объектов, составленных из элементов которые содержат объекты, вес которых не больше чем <tex dpi="130">Ak</tex>, . Причем <tex dpi="130150">W=\m_{w_{1}0,w_{2}, \ldots ,w_{k}\i}= 1</tex> {{---}} количество объектов веса , а <tex dpi="130150">\m_{1 \ldots k\i, 0}= 0</tex>, составленных из элементов <tex dpi="130150"">Ai \ne 0</tex>, .|proof=<tex dpi="130">w_m_{0, i} = 1</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса , так как не набирать никакой вес есть один способ, а <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_m_{ni, 0}=s_{n, n}0</tex>, где <tex dpi="150130"">s_{n, k}=i \sum_{i=ne 0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, что они содержат объекты суммарного веса не более так как нельзя набрать положительный вес из ничего. Рассуждения аналогичны рассуждениям <tex dpi="130">kPSet</tex>, однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.

===Количество MSet из элементов <tex>0</tex> или <tex>и 1</tex>===Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">SM=PSetMSet(A)</tex> {{---}} множество всех множеств мультимножеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">w_{0} = 1</tex>.:Тогда, <tex dpi="150">S_M_{n}=s_m_{n, n}</tex>, где <tex dpi="150">s_m_{n, k}=\sum_sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_ \binom{w_{k}+i-1}{i}m_{n-ik, k-1}</tex>:<tex dpi="150">S_M_{0}=s_m_{0, 0} = 1</tex>.:<tex dpi="150">S_M_{1}=s_m_{1, 1} = s_\binom{1}{0}m_{1, 0} + 2s_\binom{2}{1}m_{0, 0} = 2s_2m_{0, 0} = 2</tex>.:<tex dpi="150">S_M_{2}=s_m_{2, 2} = s_\binom{0}{0}m_{2, 1} + \binom{0 \times s_}{1} m_{0, 1} = s_\binom{1}{0}m_{2, 0} + 2s_\binom{2}{1}m_{1, 0} + 3s_\binom{3}{2}m_{0, 0}= 3s_3m_{0, 0} = 3</tex>.:<tex dpi="150">S_{M_{3}=s_m_{3, 3} = s_\binom{0}{0}m_{3, 2} + \binom{0 \times s_}{1} m_{0, 2} = s_\binom{0}{0}m_{3, 1} + \binom{0 \times s_}{1} m_{0, 1} = s_\binom{1}{0}m_{3, 0} + 2s_\binom{2}{1}m_{2, 0} + 3s_\binom{3}{2}m_{1, 0} + 4s_\binom{4}{3}m_{0, 0}= 4s_4m_{0, 0} = 4}</tex>.

:<tex dpi="150">{S_M_{n}=s_m_{n, n} = s_\binom{0}{0}m_{n, n-1} + \binom{0 \times s_}{1} m_{0, n-1} = s_\binom{0}{0}m_{n, n-2} + \binom{0 \times s_}{1} m_{0, n-2} = \ldots = s_\binom{1}{0}m_{n, 0} + 2s_\binom{2}{1}m_{n - 1, 0} + \ldots + ns_\binom{n}{n-1}m_{1, 0} + (\binom{n+1) s_}{n} m_{0,0} = (n + 1) s_m_{0,0} = n+1}</tex>. ==Помеченные унициклические графы== {{Определение|definition=<tex dpi="130">Унициклическим</tex> называется связный граф, содержащий один простой цикл и не содержащий петель и кратных рёбер. <tex dpi="150">U_{n}</tex> {{---}} '''количество унициклических графов''' из <tex dpi="130">n</tex> вершин, <tex dpi="130">n > 2</tex>.}} {{Утверждение|statement=<tex dpi="150">U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}</tex>.|proof=Для всех <tex dpi="130">r \in [3;n]</tex> найдем число способов выбрать вершины для цикла длины <tex dpi="130">r</tex>, их количество равняется <tex dpi="130">\binom{n}{r}</tex>. Найдём число способов упорядочить выбранные вершины: заметим что каждый цикл длины <tex dpi="130">r</tex> порождается <tex dpi="130">2r</tex> способами (у каждой перестановки существует <tex dpi="130">r - 1</tex> циклический сдвиг и одно зеркальное представление), поэтому существует <tex dpi="130">\frac{r!}{2r} = \frac{(r-1)!}{2}</tex> различных циклов. Найдём количество способов достроить полученный цикл до связного унициклического графа. Заметим, что при удалениии всех ребер цикла граф станет лесом из <tex dpi="130">r</tex> деревьев и <tex dpi="130">n</tex> вершин. Используя [[Коды Прюфера|кодирование Прюфера]], получим, что количество таких лесов равно <tex dpi="130">r {n}^{n-r-1}</tex>. Нахождение количества таких лесов аналогично нахождению [[Количество помеченных деревьев|количества помеченных деревьев]]. Значит, количество унициклических графов порядка <tex dpi="130">n</tex> равно <tex dpi="130">U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}</tex>.}} ==Связные графы=={{Определение|definition=<tex dpi="130">CONN_{n}</tex> - количество связных графов с <tex dpi="130">n</tex> вершинами.}}

===Подсчет подвешенных непомеченных деревьев без порядка на детях=={{Лемма|statement=Пусть <tex dpi="130150">T_G_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_2^{0} = 1</tex>. <tex dpi="130">F=MSet(T)</tex> {{---}} множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. <tex dpi="130">F_\binom{n}=f_{n,n2}</tex> {{---}} количество лесов с суммарным количество вершин <tex dpi="130">n</tex>. , где <tex dpi="130150">f_G_{n, k}</tex> {{---}} количество лесов из <tex dpi="130">n</tex> вершин, таких что они содержат не более чем <tex dpi="130">k</tex> вершин. Чтобы получить дерево из <tex dpi="130">n</tex> вершин достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней лес деревьев помеченных графов с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда::<tex dpi="150">T_{n}=F_{n-1}</tex>.:<tex dpi="150">F_{n}=f_{n, n}</tex>вершинами.:<tex dpi="150">f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>

{{Утверждение|statement=<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов с <tex dpi="130">n</tex> вершинами.|proof= Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{n}=G_{n}-X_{n}</tex>, где <tex dpi="150">X_{n}</tex> {{---}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex> {{---}} количество корневых<ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref> несвязных графов.  Вычислим <tex dpi="150">Y_{n}</tex>. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. <tex dpi="150">(k=1\ldots n-1)</tex>. Для каждого <tex dpi="150">k</tex> посчитаем количество таких графов. Количество способов выбрать <tex dpi="150">k</tex> вершин из <tex dpi="150">n</tex> равно <tex dpi="150">\binom{n}{k}</tex>. Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно <tex dpi="150">G_{n-k}</tex>. Количество таких деревьев способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>. Также количество связных графов в компоненте связности с корневой вершиной равно <tex dpi="150">CONN_{k}</tex>. Итого, для фиксированного <tex dpi="150">k</tex> количество корневых несвязных графов равно <tex dpi="150">Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}</tex>. Значит, количество несвязных графов с <tex dpi="150">n</tex> вершинами равно <tex dpi="150">X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex> Таким образом, количество связных графов с <tex dpi="130">n</tex> вершинами образуют последовательность равно <tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>}}  ==Пары (Pair)== {{Определение|definition=<tex dpi="130">D=Pair(A, B)</tex> {{---}} множество всех пар объектов, составленных из элементов <tex dpi="130">A</tex> и <tex dpi="130">B</tex>. <tex dpi="150">D_{n}</tex> {{---}} '''количество пар''' из объектов суммарного веса <tex dpi="130">n</tex>.}} {{Утверждение|statement=<tex dpi="150">D_{n}=\sum\limits_{i=0}^{n}w_{i}u_{n-i}</tex>.|proof=Чтобы составить пару веса <tex dpi="130">n</tex> нужно взять один элемент веса <tex dpi="130">0 \leqslant i \leqslant n</tex> из <tex dpi="130">A</tex> и элемент веса <tex dpi="130">n-i</tex> из <tex dpi="130">B</tex> , что полностью соответствует данной формуле.}} ==Циклы (Cycle)== {{Определение|definition=<tex dpi="130">C=Cycle(A)</tex> {{---}} множество всех циклов <ref>[[wikipedia:Cyclic order | Wikipedia {{---}} Циклы]]</ref> из элементов <tex dpi="130">A</tex>. <tex dpi="150">C_{n}</tex> {{---}} '''количество циклов''' веса <tex dpi="150">n</tex>.}} {{Утверждение|statement=<tex dpi="150">C_{n}=\sum\limits_{s=1}^{n}c_{n, s}</tex>, где <tex dpi="150">c_{n,s}=\sum\limits_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}</tex>, {{---}} количество циклов веса <tex dpi="150">n</tex> длины <tex dpi="150">s</tex>, а <tex dpi="150">|St(\vec{i})|</tex> {{---}} количество стабилизаторов для циклического сдвига на <tex dpi="150">i</tex> .|proof=Очевидно, что длина цикла веса <tex dpi="130">n</tex> может быть от <tex dpi="130"> 1</tex> до <tex dpi="130">n</tex>. Посмотрим сколько существует циклов каждой длины. Это можно сделать по [[Лемма Бёрнсайда и Теорема Пойа#Лемма Бёрнсайда|лемме Бёрнсайда]].}} {{Лемма|statement= Найдем <tex dpi="130">|St(\vec{i})|=z_{n, s,i}</tex> в общем случае.|proof=Пусть <tex dpi = "130">g=\mathrm{gcd}(s,i)</tex> {{---}} [[Наибольший общий делитель|наибольший общий делитель<tex dpi = "130">(s, i)</tex>]]. Заметим, что в <tex dpi = "130">i</tex>-ой перестановке на <tex dpi = "130">j</tex>-ой позиции стоит элемент <tex dpi = "130">(i + j)\bmod s</tex>. Также, заметим, что элемент <tex dpi = "130">a</tex> переходит в элемент <tex dpi = "130">a + in</tex>, где <tex dpi = "130">i = 1, 2, 4\ldots k</tex>. Из этого следует, 9что длина цикла для <tex dpi = "130">i</tex>-ой перестановки равна <tex dpi = "130"> \dfrac{\mathrm{lcm}(s, 20i)}{i} = \dfrac{s}{g}</tex>, 48где <tex dpi = "130">\mathrm{lcm}(s, i)</tex> {{---}} [[Наименьшее общее кратное|наименьшее общее кратное<tex dpi = "130">(s, 115i)</tex>]]. Также заметим, 286что если вес <tex dpi="130">n</tex> нельзя равномерно распределить по всей длине цикла, 719то стабилизатор равен <tex dpi="130">0</tex>. <p><tex dpi = "150">z_{n, 1842s, 4766i} = \left \{\begin{array}{ll} 0, 12486& n \bmod \frac{s}{g} \neq 0 \\b_{\frac{ng}{s}, g}, & n \bmod \frac{s}{g} = 0 \end{array} \right. </tex></p>Где <tex dpi="150">b_{n,k}</tex> {{---}} число способов упорядочить набор из <tex dpi="150">k</tex> элементов суммарного веса <tex dpi="150">n</tex> и  <tex dpi="150">b_{n,k}=\sum\limits_{i=1}^{n}w_{i}b_{n-i, k-1}</tex>, 32973причем <tex dpi="150">b_{n, 878111}=w_{n}</tex>.}} ===Задача об ожерельях===Решим данным способом [[Задача об ожерельях|задачу об ожерельях]]. Пусть необходимый вес <tex dpi="130">n</tex> {{---}} это количество бусинок, 235381а <tex dpi="130">k</tex> {{---}} количество цветов. Причем каждая бусинка весит <tex dpi="130">1</tex>. То есть <tex dpi="130">W=\{k, 634847 0 \ldots0\}</tex>. <tex dpi="130">C_{n}=\sum\limits_{s=1}^{n}c_{n,s}=c_{n,n}</tex> так как невозможно набрать вес <tex dpi="130">n</tex> менее, чем <tex dpi="130">n</tex> бусинами при весе бусин <tex dpi="130">1</tex>. <tex dpi="130">c_{n,n}=\sum\limits_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum\limits_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum\limits_{i=0}^{s-1}b_{\mathrm{gcd}(n,i),\mathrm{gcd}(n,i)}</tex>. Поскольку все бусины имеют одинаковый вес <tex dpi="130">1</tex>, то <tex dpi="130">b_{n,k} \neq 0</tex> В итоге, <tex dpi="130">C_{n}=\dfrac{1}{n}\sum\limits_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}</tex> . ==Метод производящих функций==Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов <ref>[[wikipedia:Symbolic method (combinatorics) | Wikipedia {{---}} Symbolic method]]</ref>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.При непомеченных объектах рассмотренные классы имеют следующие производящие функции: {| class="wikitable" |-align="center" !<tex dpi="130">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-A(z)}</tex>|-align="center" !<tex dpi="130">PSet(A)</tex>||<tex dpi="130">\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}A(z^{k})}{k})</tex>|-align="center" !<tex dpi="130">MSet(A)</tex>||<tex dpi="130">\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})</tex>|-align="center" !<tex dpi="130">Pair(A,B)</tex>||<tex dpi="130">A(z)B(z)</tex>|-align="center" !<tex dpi="130">Cycle(A)</tex>||<tex dpi="130">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].|} Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графы. С помеченными объектами используется экспоненциальная производящая функция <ref>[http[wikipedia:exponential generating function | Wikipedia {{---}} Exponential generating function]]</ref>. В данном случае для некоторых рассмотренных классов используются следующие производящие функции: {| class="wikitable" |-align="center" !<tex dpi="130">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-A(z)}</tex>|-align="center" !<tex dpi="130">Pset(A)</tex>||<tex dpi="130">\exp(A(z))</tex>|-align="center" !<tex dpi="130">Pair(A,B)</tex>||<tex dpi="130">A(z)B(z)</tex>|-align="center" !<tex dpi="130">Cycle(A)</tex>||<tex dpi="130">\ln\dfrac{1}{1-A(z)}</oeistex>.|} ===Ограниченные конструкции===Иногда в анализе необходимо ввести ограничение на количество компонентов.orgТакой случай обозначается нижним коэффициентом (например, <tex dpi="130">Seq_{k}(A)</tex> {{---}} <tex dpi="130">k</tex> компонентов).  Непосредственной формулой для производящих функций является диагональ <tex dpi="130">\Delta</A000081tex> декартова произведения <ref>[[wikipedia:Cartesian product | Number of unlabeled rooted trees with n nodeWikipedia {{---}} Декартово произведение]]</ref> <tex dpi="130">A \times A</tex>, определяемая как <tex dpi="130">B \equiv \Delta(A \times A) : \{(a, a) \mid a \in A\}</tex>. Тогда имеет место соотношение <tex dpi="130">B(z)=A(z^{2})</tex>.  Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из <tex dpi="130">A</tex>, то есть к <tex dpi="130">P = PSet_{2}(A)</tex>. Прямое выражение выполняется следующим способом: неупорядоченная пара <tex dpi="130">\langle \alpha, \beta \rangle </tex> связана с двумя упорядоченными парами <tex dpi="130">(\langle \alpha, \beta \rangle </tex> и <tex dpi="130">\langle \beta, \alpha \rangle )</tex>, кроме тех случаев, когда <tex dpi="130">\alpha = \beta</tex>, то есть когда пара лежит на диагонали декартова произведения. Другими словами, <tex dpi="130">PSet_{2}(A) + PSet_{2}(A) + \Delta(A \times A) \cong A \times A</tex>. Это, в свою очередь, означает что <tex dpi="130">2P(z) + A(z^{2}) = A(z)^{2}</tex>. Таким образом можно выразить <tex dpi="130">PSet_{2}(A)</tex>. Аналогично для <tex dpi="130">Seq_{2}(A)</tex>, <tex dpi="130">MSet_{2}(A)</tex> и <tex dpi="130">Cycle_{2}(A)</tex>: {| class="wikitable" |-align="center" !<tex dpi="130">Seq_{2}(A)</tex>||<tex dpi="130>A(z)^{2}</tex>|-align="center" !<tex dpi="130">PSet_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}-\dfrac{A(z^{2})}{2}</tex>|-align="center" !<tex dpi="130">MSet_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>|-align="center" !<tex dpi="130">Cycle_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>|} Аналогичные рассуждения можно провести и для больших <tex dpi="130">k</tex>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{---}} [[FileЛемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].  Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <ref>[[wikipedia:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:Rooted_Trees {| class="wikitable" |-align="center" !<tex dpi="130">Seq_{k}(A)</tex>||<tex dpi="130">A(z)^{k}</tex>|-align="center" !<tex dpi="130">PSet_{k}(A)</tex>||<tex dpi="130">[u^{k}]\exp(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i})</tex>|-align="center" !<tex dpi="130">MSet_{k}(A)</tex>||<tex dpi="130">[u^{k}]\exp(\sum\limits_{i=1}^{k}\dfrac{u^{i}A(z^{i})}{i})</tex>|-align="center" !<tex dpi="130">Cycle_{k}(A)</tex>||<tex dpi="130">[u^{k}]\sum\limits_{i \geqslant 1}\dfrac{\phi(i)}{i}\ln\dfrac{1}{1 - u^{i}A(z^i)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].png|700px} ==См.также==*[[Лемма Бёрнсайда и Теорема Пойа]]*[[Числа Каталана]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Подсчет деревьев]]*[[Метод производящих функций]]