286
правок
Изменения
somefix
===Подсчет битовых векторов длины <tex dpi="150">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="130">S_{0}=1</tex>.
Тогда, <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}</tex>.
===Подсчет Seq из маленьких и больших элементов===
Пусть <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">S_{0}=1</tex>, <tex dpi="130">S_{1}=1</tex>.
Тогда, <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=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(A)</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>-ое [[Числа Каталана|число Каталана]].
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">P=PSet(A)</tex> {{---}} множество всех множеств, составленных из элементов <tex dpi="130">A</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"">0</tex>. Тогда '''количество множеств''' суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex dpi="150">p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}</tex> {{---}} количество таких множеств, которые содержат объекты, вес которых не больше чем <tex dpi="150">k</tex>. Причем <tex dpi="150">p_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="150">p_{i, 0} = 0</tex>, <tex dpi="150"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
|proof=Изначально у нас есть только пустое множество веса <tex dpi="130">0</tex>. Рассмотрим очередной этап вычисления <tex dpi="130">p_{n,k}</tex>. Для данных <tex dpi="130">n</tex> и <tex dpi="130">k</tex> у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от <tex dpi="130">0</tex> до <tex dpi="130">\lfloor \frac{n}{k} \rfloor</tex> элементов веса <tex dpi="130">k</tex> (при условии, что столько различных элементов имеется) в данное множество. Выбрать нужное количество элементов можно с помощью сочетаний. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше <tex dpi="130">k</tex> (чтобы избежать повторений) суммарного веса <tex dpi="130">n-ik</tex>, где <tex dpi="130">i</tex> {{---}} количество элементов веса <tex dpi="130">k</tex> которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле.
}}
===Количество PSet из элементов 0 и 1===
Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex>P=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">P_{n}=p_{n, n}</tex>, где <tex tex dpi="150">p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} p_{n-ik, k-1}</tex>.
:<tex dpi="150">P_{0}=p_{0, 0} = 1</tex>.
:<tex dpi="150">P_{1}=p_{1, 1} = \binom{1}{0}p_{1, 0} + 2p_\binom{2}{1}p_{0, 0} = 2p_{0, 0} = 2</tex>.:<tex dpi="150">P_{2}=p_{2, 2} = \binom{0}{0} p_{2, 1} + \binom{0 \cdot }{1}p_{0, 1} = \binom{2}{0}p_{2, 0} + 2p_\binom{2}{1}p_{1, 0} + \binom{2}{2}p_{0, 0}= p_{0, 0} = 1</tex>.:<tex dpi="150">{P_{3}=p_{3, 3} = \binom{0}{0}p_{3, 2} + \binom{0 \cdot }{1} p_{0, 2} = \binom{0}{0}p_{3, 1} + \binom{0 \cdot }{1} p_{0, 1} = \binom{2}{0}p_{3, 0} + 2p_\binom{2}{1}p_{2, 0} + 0 \cdot binom{2}{2} p_{1, 0} + 0 \cdot binom{2}{3} p_{0, 0}= 0}</tex>.
:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">P_{n} = 0</tex> .
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">M=MSet(A)</tex> {{---}} множество всех мультимножеств <ref>[[wikipedia:Multiset|Wikipedia {{---}} Мультимножества]]</ref> из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{kl}\}</tex> {{---}} количество объектов веса от <tex dpi="130">\{1 \ldots k\}</tex> до <tex dpi="130">l</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, которые содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>.
|proof=Рассуждения аналогичны рассуждениям <tex dpi="130">PSet</tex>, однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.
}}
:Тогда, <tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex>
:<tex dpi="150">M_{0}=m_{0, 0} = 1</tex>.
:<tex dpi="150">M_{1}=m_{1, 1} = \binom{1}{0}m_{1, 0} + 2m_\binom{2}{1}m_{0, 0} = 2m_{0, 0} = 2</tex>.:<tex dpi="150">M_{2}=m_{2, 2} = \binom{0}{0}m_{2, 1} + \binom{0 \cdot }{1} m_{0, 1} = \binom{1}{0}m_{2, 0} + 2m_\binom{2}{1}m_{1, 0} + 3m_\binom{3}{2}m_{0, 0}= 3m_{0, 0} = 3</tex>.:<tex dpi="150">{M_{3}=m_{3, 3} = \binom{0}{0}m_{3, 2} + \binom{0 \cdot }{1} m_{0, 2} = \binom{0}{0}m_{3, 1} + \binom{0 \cdot }{1} m_{0, 1} = \binom{1}{0}m_{3, 0} + 2m_\binom{2}{1}m_{2, 0} + 3m_\binom{3}{2}m_{1, 0} + 4m_\binom{4}{3}m_{0, 0}= 4m_{0, 0} = 4}</tex>.
:<tex dpi="150">\{\}</tex>
:<tex dpi="150">\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}</tex>
:<tex dpi="150">{M_{n}=m_{n, n} = \binom{0}{0}m_{n, n-1} + \binom{0 \cdot }{1} m_{0, n-1} = \binom{0}{0}m_{n, n-2} + \binom{0 \cdot }{1} m_{0, n-2} = \ldots = \binom{1}{0}m_{n, 0} + 2m_\binom{2}{1}m_{n - 1, 0} + \ldots + nm_\binom{n}{n-1}m_{1, 0} + (\binom{n+1) }{n} m_{0,0} = (n + 1) m_{0,0} = n+1}</tex>.
===Подсчет подвешенных непомеченных деревьев без порядка на детях===
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">F=MSet(T)</tex> {{---}} множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. <tex dpi="130">F_{n}=f_{n,n}</tex> {{---}} количество лесов с суммарным количество вершин <tex dpi="130">n</tex>. <tex dpi="130">f_{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>.
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{zz_{1}}\}</tex>, <tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{mz_{2}}\}</tex> {{---}} множества из различных объектов, <tex dpi="130">D=Pair(A, B)</tex> {{---}} множество всех пар объектов, составленных из элементов <tex dpi="130">A</tex> и <tex dpi="130">B</tex>. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{kl}\}</tex> {{---}} количество объектов веса от <tex dpi="130">\{1 \ldots k\}</tex> до <tex dpi="130">l</tex>, составленных из элементов <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{kl}\}</tex> {{---}} соответственно для <tex dpi="130">B</tex>. Тогда '''количество пар''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">D_{n}=\sum_{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>, что полностью соответствует данной формуле.
}}
===Количество подвешенных неполных двоичных деревьев===
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">D=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}=D_{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>-ое [[Числа Каталана|число Каталана]].
}}
{{Лемма|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, \ldots k</tex>. Из этого следует, что длина цикла для <tex dpi = "130">i</tex>-ой перестановки равна <tex dpi = "130"> \dfrac{\mathrm{lcm}(s, i)}{i} = \dfrac{s}{g}</tex>, где <tex dpi = "130">\mathrm{lcm}(s, i)</tex> {{---}} [[Наименьшее общее кратное|наименьшее общее кратное<tex dpi = "130">(s, i)</tex>]].
Также заметим, что если вес <tex dpi="130">n</tex> нельзя равномерно распределить по всей длине цикла, то стабилизатор равен <tex dpi="130">0</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>.
}}
===Задача об ожерельях===
