286
правок
Изменения
+Cycle
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{nz}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>. Тогда '''количество последовательностей''' веса <tex dpi="130">n</tex> можно вычислить как: <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>.
}}
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{nz}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех множеств объектов, составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество множеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} s_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты суммарного веса <tex dpi="130">\leqslant k</tex>.
}}
===Количество разбиений на слагаемые===
Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда, :<tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1} = s_{n, k-1} + s_{n - k, k}</tex>, что, как не сложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{nz}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=MSet(A)</tex> {{---}} множество всех мультимножеств объектов, составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, что они содержат объекты суммарного веса не более <tex dpi="130">k</tex>.
}}
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{nz}\}</tex>, <tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{m}\}</tex> {{---}} множества из различных объектов, <tex dpi="130">S=Pair(A, B)</tex> {{---}} множество всех пар объектов, составленных из элементов <tex dpi="130">A</tex> и <tex dpi="130">B</tex>. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, составленных из элементов <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{k}\}</tex> {{---}} соответственно для <tex dpi="130">B</tex>. Тогда '''количество пар''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=0}^{n}w_{i}u_{n-i}</tex>.
}}
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">S=Pair(T, T)</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}=\sum_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].
==Циклы(Cycle)==
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">C=Cycle(A)</tex> {{---}} множество всех циклов из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>.
Тогда '''количество циклов''' веса <tex dpi="150">n</tex> можно вычислить как <tex dpi="150">C_{n}=\sum_{s=1}^{n}c_{n, s}</tex>, где <tex dpi="150">c_{n,s}</tex> {{---}} количество циклов веса <tex dpi="150">n</tex> длины <tex dpi="150">s</tex>.
По [[Лемма Бёрнсайда и Теорема Пойа#Лемма Бёрнсайда|лемме Бёрнсайда]] <tex dpi="150">c_{n,s} =\sum_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}</tex>, где <tex dpi="150">|St(\vec{i})|=z_{n,s,i}</tex> {{---}} количество стабилизаторов для циклического сдвига на <tex dpi="150">i</tex>
Пусть <tex dpi="150">g=gcd(s,i)</tex> {{---}} наибольший общий делитель <tex dpi="150">s</tex> и <tex dpi="150">i</tex>. Тогда длина циклов при сдвиге на <tex dpi="150">i</tex> равна <tex dpi="150">\frac{s}{g}</tex>
<p>
<tex dpi = "150">z_{n, s, i} =
\left \{\begin{array}{ll} 0, & n \mod \frac{s}{g} \neq 0 \\
b_{\frac{ng}{s}, g}, & n \mod \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_{i=1}^{n}w_{i}b_{n-i, k-1}</tex>, <tex dpi="150">b_{n,1}=w_{n}</tex>
}}
==Примeчания==
<references/>
