Конструирование комбинаторных объектов и их подсчёт — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(+Cycle)
(Modify Cycle + few fix)
Строка 3: Строка 3:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</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>.
+
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</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">w_{0} = 1</tex>. Тогда '''количество последовательностей''' веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>.
 
}}
 
}}
  
Строка 19: Строка 19:
 
Пусть <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="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">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>-ое [[Числа Каталана|число Каталана]]
+
:<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]]
 
[[File:Ordered_Rooted_Trees.png|700px]]
Строка 27: Строка 27:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</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">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=\{a_{1},a_{2}, \ldots ,a_{z}\}</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">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">k</tex>.
 
}}
 
}}
  
 
===Количество PSet из элементов <tex>0</tex> или <tex>1</tex>===
 
===Количество PSet из элементов <tex>0</tex> или <tex>1</tex>===
Пусть <tex dpi="130">A={0, 1}</tex>, <tex>S=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_{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}</tex>
+
Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex>S=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_{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}</tex>.
:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>
+
:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>.
:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>
+
:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>.
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>
+
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>.
:<tex dpi="150">{S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \cdot s_{1, 0} + 0 \cdot s_{0, 0}= 0}</tex>
+
:<tex dpi="150">{S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \cdot s_{1, 0} + 0 \cdot s_{0, 0}= 0}</tex>.
:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_{n} = 0</tex>  
+
:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_{n} = 0</tex> .
  
 
:<tex dpi="150">\{\}</tex>
 
:<tex dpi="150">\{\}</tex>
Строка 44: Строка 44:
  
 
===Количество разбиений на слагаемые===
 
===Количество разбиений на слагаемые===
Пусть <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="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)|динамического программирования]].
 
:<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)|динамического программирования]].
  
Строка 51: Строка 51:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</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">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>.
+
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</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">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>.
 
}}
 
}}
  
 
===Количество MSet из элементов <tex>0</tex> или <tex>1</tex>===
 
===Количество MSet из элементов <tex>0</tex> или <tex>1</tex>===
Пусть <tex dpi="130">A={0, 1}</tex>, <tex dpi="130">S=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="130">A=\{0, 1\}</tex>, <tex dpi="130">S=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_{n}=s_{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">S_{n}=s_{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">S_{0}=s_{0, 0} = 1</tex>
+
:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>.
:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>
+
:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>.
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3</tex>
+
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3</tex>.
:<tex dpi="150">S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4</tex>
+
:<tex dpi="150">S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4</tex>.
  
 
:<tex dpi="150">\{\}</tex>
 
:<tex dpi="150">\{\}</tex>
Строка 67: Строка 67:
 
:<tex dpi="150">\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}</tex>
 
:<tex dpi="150">\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}</tex>
  
:<tex dpi="150">{S_{n}=s_{n, n} = s_{n, n-1} + 0 \cdot s_{0, n-1} = s_{n, n-2} + 0 \cdot s_{0, n-2} = \ldots = s_{n, 0} + 2s_{n - 1, 0} + \ldots + ns_{1, 0} + (n+1) s_{0,0} = (n + 1) s_{0,0} = n+1}</tex>
+
:<tex dpi="150">{S_{n}=s_{n, n} = s_{n, n-1} + 0 \cdot s_{0, n-1} = s_{n, n-2} + 0 \cdot s_{0, n-2} = \ldots = s_{n, 0} + 2s_{n - 1, 0} + \ldots + ns_{1, 0} + (n+1) s_{0,0} = (n + 1) s_{0,0} = n+1}</tex>.
  
 
===Подсчет подвешенных непомеченных деревьев без порядка на детях===
 
===Подсчет подвешенных непомеченных деревьев без порядка на детях===
Строка 73: Строка 73:
 
:<tex dpi="150">T_{n}=F_{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}=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>
+
:<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>.
  
 
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex>  <ref>[http://oeis.org/A000081| Number of unlabeled rooted trees with n node]</ref>  
 
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex>  <ref>[http://oeis.org/A000081| Number of unlabeled rooted trees with n node]</ref>  
Строка 95: Строка 95:
 
Тогда '''количество циклов''' веса <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">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">c_{n,s} =\sum_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}</tex>, где <tex dpi="150">|St(\vec{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>  
+
Найдем <tex dpi="130">|St(\vec{i})|=z_{n,s,i}</tex> в общем случае.
 +
 
 +
Пусть <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>.
  
 
<p>
 
<p>
 
<tex dpi = "150">z_{n, s, i} =  
 
<tex dpi = "150">z_{n, s, i} =  
\left \{\begin{array}{ll} 0, & n \mod \frac{s}{g} \neq 0 \\
+
\left \{\begin{array}{ll} 0, & n \bmod \frac{s}{g} \neq 0 \\
b_{\frac{ng}{s}, g}, & n \mod \frac{s}{g} = 0 \end{array} \right.  
+
b_{\frac{ng}{s}, g}, & n \bmod \frac{s}{g} = 0 \end{array} \right.  
 
</tex>
 
</tex>
 
</p>
 
</p>
 
Где <tex dpi="150">b_{n,k}</tex> {{---}} число способов упорядочить набор из <tex dpi="150">k</tex> элементов суммарного веса <tex dpi="150">n</tex> и  
 
Где <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>
+
<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>.
}}
+
 
 +
===Задача об ожерельях===
 +
Решим данным способом [[Задача об ожерельях|задачу об ожерельях]]. Пусть необходимый вес <tex dpi="130">n</tex> это количество бусинок, а <tex dpi="130">k</tex> {{---}} количество цветов. При чем каждая бусинка весит <tex dpi="130">1</tex>. То есть <tex dpi="130">W=\{k, 0 \ldots 0\}</tex>.
 +
 
 +
<tex dpi="130">C_{n}=\sum_{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_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum_{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_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}</tex>.
 +
 
 
==Примeчания==
 
==Примeчания==
 
<references/>
 
<references/>

Версия 08:44, 27 декабря 2017

Последовательности(Seq)

Утверждение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math] — множество из различных объектов, [math]S=Seq(A)[/math] — множество всех последовательностей из элементов [math]A[/math], [math]W=\{w_{1},w_{2}, \ldots ,w_{m}\}[/math] — количество объектов веса [math]\{1 \ldots m\}[/math], [math]w_{0} = 1[/math]. Тогда количество последовательностей веса [math]n[/math] можно вычислить как [math]S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}[/math].

Подсчет битовых векторов длины [math]n[/math]

Пусть [math]A=\{0, 1\}[/math], [math]W=\{2, 0 \ldots 0\}[/math], [math]S=Seq(A)[/math] — множество всех битовых векторов.

Тогда, [math]S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}[/math].

Подсчет Seq из маленьких и больших элементов

Пусть [math]A=\{1, 2\}[/math], [math]W=\{1, 1, 0 \ldots 0\}[/math], [math]S=Seq(A)[/math] — множество всех последовательностей из маленьких и больших элементов [math]S=Seq(A)[/math].

Тогда, [math]S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=S_{n-1}+S_{n-2}=F_{n}[/math], где [math]F_{n}[/math][math]n[/math]-ое число Фибоначчи [1].

Подсчет подвешенных непомеченных деревьев с порядком на детях

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами, [math]T_{0} = 1[/math]. [math]S=Seq(A)[/math] — множество всех последовательностей из данных деревьев. [math]S_{n}[/math] — количество последовательностей с суммарным количество вершин [math]n[/math]. Чтобы получить дерево из [math]n[/math] вершин достаточно взять [math]1[/math] вершину и подвесить к ней последовательность деревьев с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=S_{n-1}[/math].
[math]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}[/math], где [math]C_{n}[/math][math]n[/math]-ое число Каталана.

Ordered Rooted Trees.png

Множества(PSet)

Утверждение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math] — множество из различных объектов, [math]S=PSet(A)[/math] — множество всех множеств составленных из элементов [math]A[/math], [math]W=\{w_{1},w_{2}, \ldots ,w_{k}\}[/math] — количество объектов веса [math]\{1 \ldots k\}[/math], [math]w_{0} = 1[/math]. Тогда количество множеств суммарного веса [math]n[/math] можно вычислить как [math]S_{n}=s_{n, n}[/math], где [math]s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} s_{n-ik, k-1}[/math] — количество таких множеств, что они содержат объекты, вес которых не больше чем [math]k[/math].

Количество PSet из элементов [math]0[/math] или [math]1[/math]

Пусть [math]A=\{0, 1\}[/math], [math]S=PSet(A)[/math] — множество всех множеств из [math]A[/math], [math]W=\{2, 0 \ldots 0\}[/math], [math]w_{0} = 1[/math]. Тогда [math]S_{n}=s_{n, n}[/math], где [math]s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}[/math].

[math]S_{0}=s_{0, 0} = 1[/math].
[math]S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2[/math].
[math]S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1[/math].
[math]{S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \cdot s_{1, 0} + 0 \cdot s_{0, 0}= 0}[/math].
Для [math]n \gt 2[/math], [math]S_{n} = 0[/math] .
[math]\{\}[/math]
[math]\{0\}, \{1\}[/math]
[math]\{0, 1\}[/math]


Количество разбиений на слагаемые

Пусть [math]A=\mathbb{N}[/math], [math]S=PSet(A)[/math] — множество всех разбиений на слагаемые, [math]W=\{1 \ldots 1\}[/math], [math]w_{0} = 1[/math]. Тогда,

[math]S_{n}=s_{n, n}[/math], где [math]s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1} = s_{n, k-1} + s_{n - k, k}[/math], что, как не сложно заметить, соответствует формуле, полученной методом динамического программирования.


Мультимножества(MSet)

Утверждение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math] — множество из различных объектов, [math]S=MSet(A)[/math] — множество всех мультимножеств из элементов [math]A[/math], [math]W=\{w_{1},w_{2}, \ldots ,w_{k}\}[/math] — количество объектов веса [math]\{1 \ldots k\}[/math], [math]w_{0} = 1[/math]. Тогда количество мультимножеств из объектов суммарного веса [math]n[/math] можно вычислить как [math]S_{n}=s_{n, n}[/math], где [math]s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_{n-ik, k-1}[/math] — количество таких мультимножеств, что они содержат объекты, вес которых не больше чем [math]k[/math].

Количество MSet из элементов [math]0[/math] или [math]1[/math]

Пусть [math]A=\{0, 1\}[/math], [math]S=PSet(A)[/math] — множество всех множеств из [math]A[/math], [math]W=\{2, 0 \ldots 0\}[/math], [math]w_{0} = 1[/math].

Тогда, [math]S_{n}=s_{n, n}[/math], где [math]s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}[/math]
[math]S_{0}=s_{0, 0} = 1[/math].
[math]S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2[/math].
[math]S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3[/math].
[math]S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4[/math].
[math]\{\}[/math]
[math]\{0\}, \{1\}[/math]
[math]\{0, 0\}, \{0, 1\}, \{1, 1\}[/math]
[math]\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}[/math]
[math]{S_{n}=s_{n, n} = s_{n, n-1} + 0 \cdot s_{0, n-1} = s_{n, n-2} + 0 \cdot s_{0, n-2} = \ldots = s_{n, 0} + 2s_{n - 1, 0} + \ldots + ns_{1, 0} + (n+1) s_{0,0} = (n + 1) s_{0,0} = n+1}[/math].

Подсчет подвешенных непомеченных деревьев без порядка на детях

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами, [math]T_{0} = 1[/math]. [math]F=MSet(T)[/math] — множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. [math]F_{n}=f_{n,n}[/math] — количество лесов с суммарным количество вершин [math]n[/math]. [math]f_{n, k}[/math] — количество лесов из [math]n[/math] вершин, таких что они содержат не более чем [math]k[/math] вершин. Чтобы получить дерево из [math]n[/math] вершин достаточно взять [math]1[/math] вершину и подвесить к ней лес деревьев с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=F_{n-1}[/math].
[math]F_{n}=f_{n, n}[/math].
[math]f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}[/math].

Количество таких деревьев с [math]n[/math] вершинами образуют последовательность [math] 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots[/math] [2] Rooted Trees.png

Пары(Pair)

Утверждение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math], [math]B=\{b_{1},b_{2}, \ldots ,b_{m}\}[/math] — множества из различных объектов, [math]S=Pair(A, B)[/math] — множество всех пар объектов, составленных из элементов [math]A[/math] и [math]B[/math]. [math]W=\{w_{1},w_{2}, \ldots ,w_{k}\}[/math] — количество объектов веса [math]\{1 \ldots k\}[/math], составленных из элементов [math]A[/math], а [math]U=\{u_{1},u_{2}, \ldots ,u_{k}\}[/math] — соответственно для [math]B[/math]. Тогда количество пар из объектов суммарного веса [math]n[/math] можно вычислить как [math]S_{n}=\sum_{i=0}^{n}w_{i}u_{n-i}[/math].

Количество подвешенных неполных двоичных деревьев

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами, [math]T_{0} = 1[/math]. [math]S=Pair(T, T)[/math] — множество всех пар из данных деревьев. Чтобы получить двоичное дерево из [math]n[/math] вершин, достаточно взять [math]1[/math] вершину и подвесить к ней левого и правого сына с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=S_{n-1}=\sum_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}[/math], где [math]C_{n}[/math][math]n[/math]-ое число Каталана.

Циклы(Cycle)

Утверждение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math] — множество из различных объектов, [math]C=Cycle(A)[/math] — множество всех циклов из элементов [math]A[/math], [math]W=\{w_{1},w_{2}, \ldots ,w_{m}\}[/math] — количество объектов веса [math]\{1 \ldots m\}[/math].

Тогда количество циклов веса [math]n[/math] можно вычислить как [math]C_{n}=\sum_{s=1}^{n}c_{n, s}[/math], где [math]c_{n,s}[/math] — количество циклов веса [math]n[/math] длины [math]s[/math].

По лемме Бёрнсайда [math]c_{n,s} =\sum_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}[/math], где [math]|St(\vec{i})|[/math] — количество стабилизаторов для циклического сдвига на [math]i[/math] .

Найдем [math]|St(\vec{i})|=z_{n,s,i}[/math] в общем случае.

Пусть [math]g=\mathrm{gcd}(s,i)[/math]наибольший общий делитель[math](s, i)[/math]. Заметим, что в [math]i[/math]-ой перестановке на [math]j[/math]-ой позиции стоит элемент [math](i + j)\bmod s[/math]. Также, заметим, что элемент [math]a[/math] переходит в элемент [math]a + in[/math], где [math]i = 1, 2, \ldots k[/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math] \dfrac{\mathrm{lcm}(s, i)}{i} = \dfrac{s}{g}[/math], где [math]\mathrm{lcm}(s, i)[/math]наименьшее общее кратное[math](s, i)[/math].

Также заметим, что если вес [math]n[/math] нельзя равномерно распределить по всей длине цикла, то стабилизатор равен [math]0[/math].

[math]z_{n, s, i} = \left \{\begin{array}{ll} 0, & n \bmod \frac{s}{g} \neq 0 \\ b_{\frac{ng}{s}, g}, & n \bmod \frac{s}{g} = 0 \end{array} \right. [/math]

Где [math]b_{n,k}[/math] — число способов упорядочить набор из [math]k[/math] элементов суммарного веса [math]n[/math] и

[math]b_{n,k}=\sum_{i=1}^{n}w_{i}b_{n-i, k-1}[/math], при чем [math]b_{n,1}=w_{n}[/math].

Задача об ожерельях

Решим данным способом задачу об ожерельях. Пусть необходимый вес [math]n[/math] это количество бусинок, а [math]k[/math] — количество цветов. При чем каждая бусинка весит [math]1[/math]. То есть [math]W=\{k, 0 \ldots 0\}[/math].

[math]C_{n}=\sum_{s=1}^{n}c_{n,s}=c_{n,n}[/math] так как невозможно набрать вес [math]n[/math] менее чем [math]n[/math] бусинами при весе бусин [math]1[/math].

[math]c_{n,n}=\sum_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum_{i=0}^{s-1}b_{\mathrm{gcd}(n,i),\mathrm{gcd}(n,i)}[/math]. Поскольку все бусины имеют одинаковый вес [math]1[/math], то [math]b_{n,k} \neq 0[/math]

В итоге, [math]C_{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}[/math].

Примeчания