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

Материал из Викиконспекты
Перейти к: навигация, поиск
(fix seq)
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 15 участников)
Строка 1: Строка 1:
==Последовательности(Seq)==
+
{{Определение
 +
|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>.
 +
}}
 +
 
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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\limits_{i=1}^{n} w_{i} S_{n-i}</tex>. Причем <tex dpi="150"">S_{0} = 1</tex>.
 +
|proof=
 +
<tex dpi="130"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.
  
<tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>.
+
Докажем по индукции.
 +
 
 +
'''База <tex dpi="130"">n = 1</tex>'''.
 +
:<tex dpi="130"">S_{1}=w_{1} S_{0}=w_{1}</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="150">n</tex>===
 
===Подсчет битовых векторов длины <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">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_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}</tex>.
+
Тогда, <tex dpi="150">S_{n}=\sum\limits\limits_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}</tex>.
  
 
===Подсчет Seq из маленьких и больших элементов===
 
===Подсчет 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=Seq(A)</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">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="150">S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-i}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex dpi="150">F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.
  
===Подсчет подвешенных непомеченных деревьев с порядком на детях===
+
==Множества (PSet)==
Пусть <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>-ое [[Числа Каталана|число Каталана]]
 
  
[[File:Ordered_Rooted_Trees.png|700px]]
+
{{Определение
 
+
|definition=
==Множества(PSet)==
+
<tex dpi="130">P=PSet(A)</tex> {{---}} множество всех множеств, составленных из элементов <tex dpi="130">A</tex>. <tex dpi="150">P_{n}</tex> {{---}} '''количество множеств''' суммарного веса <tex dpi="130">n</tex>.
 +
}}
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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="150">P_{n}=p_{n, n}</tex>, где <tex dpi="150">p_{n, k}=\sum\limits_{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">p_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="130">p_{i, 0} = 0</tex>, <tex dpi="130"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
 +
 
 +
Изначально у нас есть только пустое множество веса <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 из элементов <tex>0</tex> или <tex>1</tex>===
+
===Количество PSet из элементов 0 и 1===
Пусть <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>P=PSet(A)</tex> {{---}} множество всех множеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>. Тогда <tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex tex dpi="150">p_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i}p_{n-ik, k-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">P_{0}=p_{0, 0} = 1</tex>.
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \times s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>
+
:<tex dpi="150">P_{1}=p_{1, 1} = \binom{2}{0}p_{1, 0} + \binom{2}{1}p_{0, 0} = 2p_{0, 0} = 2</tex>.
:<tex dpi="150">{S_{3}=s_{3, 3} = s_{3, 2} + 0 \times s_{0, 2} = s_{3, 1} + 0 \times s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \times s_{1, 0} + 0 \times s_{0, 0}= 0}</tex>
+
:<tex dpi="150">P_{2}=p_{2, 2} = \binom{0}{0} p_{2, 1} + \binom{0}{1}p_{0, 1} = \binom{2}{0}p_{2, 0} + \binom{2}{1}p_{1, 0} + \binom{2}{2}p_{0, 0}= p_{0, 0} = 1</tex>.
:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_{n} = 0</tex>  
+
:<tex dpi="150">{P_{3}=p_{3, 3} = \binom{0}{0}p_{3, 2} + \binom{0}{1} p_{0, 2} = \binom{0}{0}p_{3, 1} + \binom{0}{1} p_{0, 1} = \binom{2}{0}p_{3, 0} + \binom{2}{1}p_{2, 0} + \binom{2}{2} p_{1, 0} + \binom{2}{3} p_{0, 0}= 0}</tex>.
 +
:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">P_{n} = 0</tex> .
  
 
:<tex dpi="150">\{\}</tex>
 
:<tex dpi="150">\{\}</tex>
 
:<tex dpi="150">\{0\}, \{1\}</tex>
 
:<tex dpi="150">\{0\}, \{1\}</tex>
 
:<tex dpi="150">\{0, 1\}</tex>
 
:<tex dpi="150">\{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="130">A=\mathbb{N}</tex>, <tex dpi="130">P=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 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>, что, как не сложно заметить, соответствует формуле, полученной методом динамического программирования.
+
:<tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex tex dpi="150">p_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} p_{n-ik, k-1} = p_{n, k-1} + p_{n - k, k}</tex>, что, как несложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].
  
 +
==Мультимножества (MSet)==
 +
 +
{{Определение
 +
|definition=
 +
<tex dpi="130">M=MSet(A)</tex> {{---}} множество всех мультимножеств <ref>[[wikipedia:Multiset|Wikipedia {{---}} Мультимножества]]</ref> из элементов <tex dpi="130">A</tex>. <tex dpi="150">M_{n}</tex> {{---}} '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex>.
 +
}}
  
==Мультимножества(MSet)==
 
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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>.
+
<tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, которые содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>. Причем <tex dpi="150">m_{0, i} = 1</tex>, а <tex dpi="150">m_{i, 0} = 0</tex>, <tex dpi="150"">i \ne 0</tex>.
 +
|proof=
 +
<tex dpi="130">m_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="130">m_{i, 0} = 0</tex>, <tex dpi="130"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
 +
 
 +
Рассуждения аналогичны рассуждениям <tex dpi="130">PSet</tex>, однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.  
 
}}
 
}}
  
===Количество MSet из элементов <tex>0</tex> или <tex>1</tex>===
+
===Количество MSet из элементов 0 и 1===
Пусть <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">M=MSet(A)</tex> {{---}} множество всех мультимножеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</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">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i}m_{n-ik, k-1}</tex>
:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>
+
:<tex dpi="150">M_{0}=m_{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">M_{1}=m_{1, 1} = \binom{1}{0}m_{1, 0} + \binom{2}{1}m_{0, 0} = 2m_{0, 0} = 2</tex>.
:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \times s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3</tex>
+
:<tex dpi="150">M_{2}=m_{2, 2} = \binom{0}{0}m_{2, 1} + \binom{0}{1} m_{0, 1} = \binom{1}{0}m_{2, 0} + \binom{2}{1}m_{1, 0} + \binom{3}{2}m_{0, 0}= 3m_{0, 0} = 3</tex>.
:<tex dpi="150">S_{3}=s_{3, 3} = s_{3, 2} + 0 \times s_{0, 2} = s_{3, 1} + 0 \times s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4</tex>
+
:<tex dpi="150">{M_{3}=m_{3, 3} = \binom{0}{0}m_{3, 2} + \binom{0}{1} m_{0, 2} = \binom{0}{0}m_{3, 1} + \binom{0}{1} m_{0, 1} = \binom{1}{0}m_{3, 0} + \binom{2}{1}m_{2, 0} + \binom{3}{2}m_{1, 0} + \binom{4}{3}m_{0, 0}= 4m_{0, 0} = 4}</tex>.
  
 
:<tex dpi="150">\{\}</tex>
 
:<tex dpi="150">\{\}</tex>
Строка 69: Строка 101:
 
:<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 \times s_{0, n-1} = s_{n, n-2} + 0 \times 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">{M_{n}=m_{n, n} = \binom{0}{0}m_{n, n-1} + \binom{0}{1} m_{0, n-1} = \binom{0}{0}m_{n, n-2} + \binom{0}{1} m_{0, n-2} = \ldots = \binom{1}{0}m_{n, 0} + \binom{2}{1}m_{n - 1, 0} + \ldots + \binom{n}{n-1}m_{1, 0} + \binom{n+1}{n} m_{0,0} = (n + 1) 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> вершинами.
 +
}}
  
===Подсчет подвешенных непомеченных деревьев без порядка на детях===
+
{{Лемма
Пусть <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>. Тогда:
+
|statement=
:<tex dpi="150">T_{n}=F_{n-1}</tex>.
+
<tex dpi="150">G_{n} = 2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex> {{---}} количество помеченных графов с <tex dpi="130">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="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>  
+
{{Утверждение
[[File:Rooted_Trees.png|700px]]
+
|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, \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>
 +
<tex dpi = "150">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.
 +
</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>, причем <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\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>[[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)}</tex>.
 +
|}
 +
 
 +
===Ограниченные конструкции===
 +
Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, <tex dpi="130">Seq_{k}(A)</tex> {{---}} <tex dpi="130">k</tex> компонентов).
 +
 
 +
Непосредственной формулой для производящих функций является диагональ <tex dpi="130">\Delta</tex> декартова произведения <ref>[[wikipedia:Cartesian product | Wikipedia {{---}} Декартово произведение]]</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>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{---}} [[Лемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].
 +
 
 +
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <ref>[[wikipedia:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:
 +
 
 +
{| 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> {{---}} [[Функция_Эйлера | функция Эйлера]].
 +
|}
 +
 
 +
==См.также==
 +
*[[Лемма Бёрнсайда и Теорема Пойа]]
 +
*[[Числа Каталана]]
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Подсчет деревьев]]
 +
*[[Метод производящих функций]]
  
 
==Примeчания==
 
==Примeчания==
 
<references/>
 
<references/>
 +
 +
==Источники информации==
 +
*[http://ac.cs.princeton.edu/home/AC.pdf Philippe Flajolet, Robert Sedgewick, Analytic Combinatorics, 15-92, 2008]
 +
*[https://www.youtube.com/playlist?list=PLrNmXMVD0XDSluoHUcasgvvmBAkf2BGLi Online Course Materials from Robert Sedgewick]
 +
*[https://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
 +
*[https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) Wikipedia {{---}} Symbolic method]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]

Текущая версия на 19:15, 4 сентября 2022

Определение:
[math]A=\{a_{1},a_{2}, \ldots ,a_{z}\}[/math], [math]B=\{b_{1},b_{2}, \ldots ,b_{z_{1}}\}[/math] — множества из различных объектов. [math]W=\{w_{1},w_{2}, \ldots ,w_{l}\}[/math] — количество объектов веса от [math]1[/math] до [math]l[/math] из [math]A[/math], а [math]U=\{u_{1},u_{2}, \ldots ,u_{l}\}[/math] — соответственно для [math]B[/math].


В дальнейшем, будем считать что нет объектов веса [math]0[/math], так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество (то есть [math]w_{0}=1[/math]).


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

Определение:
[math]S=Seq(A)[/math] — множество всех последовательностей из элементов [math]A[/math]. [math]S_{n}[/math]количество последовательностей веса [math]n[/math].


Утверждение:
[math]S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-i}[/math]. Причем [math]S_{0} = 1[/math].
[math]\triangleright[/math]

[math]S_{0} = 1[/math], так как есть единственный способ составить пустую последовательность.

Докажем по индукции.

База [math]n = 1[/math].

[math]S_{1}=w_{1} S_{0}=w_{1}[/math], что верно, так как единственный способ составить последовательность веса [math]1[/math] — это взять любой элемент веса [math]1[/math].

Переход.

Пусть для [math]j \lt n[/math] верно. Докажем для [math]n[/math]. Возьмем произвольный элемент из [math]A[/math] веса [math]i \leqslant n[/math], и допишем его к последовательности элементов веса [math]n-i[/math]. Образуется новая последовательность веса [math]n[/math]. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса [math]n[/math] и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.
[math]\triangleleft[/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\limits\limits_{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_{1}=1[/math].

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

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

Определение:
[math]P=PSet(A)[/math] — множество всех множеств, составленных из элементов [math]A[/math]. [math]P_{n}[/math]количество множеств суммарного веса [math]n[/math].


Утверждение:
[math]P_{n}=p_{n, n}[/math], где [math]p_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}[/math] — количество таких множеств, которые содержат объекты, вес которых не больше чем [math]k[/math]. Причем [math]p_{0, i} = 1[/math], а [math]p_{i, 0} = 0[/math], [math]i \ne 0[/math].
[math]\triangleright[/math]

[math]p_{0, i} = 1[/math], так как не набирать никакой вес есть один способ, а [math]p_{i, 0} = 0[/math], [math]i \ne 0[/math], так как нельзя набрать положительный вес из ничего.

Изначально у нас есть только пустое множество веса [math]0[/math]. Рассмотрим очередной этап вычисления [math]p_{n,k}[/math]. Для данных [math]n[/math] и [math]k[/math] у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от [math]0[/math] до [math]\lfloor \frac{n}{k} \rfloor[/math] элементов веса [math]k[/math] (при условии, что столько различных элементов имеется) в данное множество. Выбрать нужное количество элементов можно с помощью сочетаний. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше [math]k[/math] (чтобы избежать повторений) суммарного веса [math]n-ik[/math], где [math]i[/math] — количество элементов веса [math]k[/math] которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле.
[math]\triangleleft[/math]

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

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

[math]P_{0}=p_{0, 0} = 1[/math].
[math]P_{1}=p_{1, 1} = \binom{2}{0}p_{1, 0} + \binom{2}{1}p_{0, 0} = 2p_{0, 0} = 2[/math].
[math]P_{2}=p_{2, 2} = \binom{0}{0} p_{2, 1} + \binom{0}{1}p_{0, 1} = \binom{2}{0}p_{2, 0} + \binom{2}{1}p_{1, 0} + \binom{2}{2}p_{0, 0}= p_{0, 0} = 1[/math].
[math]{P_{3}=p_{3, 3} = \binom{0}{0}p_{3, 2} + \binom{0}{1} p_{0, 2} = \binom{0}{0}p_{3, 1} + \binom{0}{1} p_{0, 1} = \binom{2}{0}p_{3, 0} + \binom{2}{1}p_{2, 0} + \binom{2}{2} p_{1, 0} + \binom{2}{3} p_{0, 0}= 0}[/math].
Для [math]n \gt 2[/math], [math]P_{n} = 0[/math] .
[math]\{\}[/math]
[math]\{0\}, \{1\}[/math]
[math]\{0, 1\}[/math]

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

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

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

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

Определение:
[math]M=MSet(A)[/math] — множество всех мультимножеств [2] из элементов [math]A[/math]. [math]M_{n}[/math]количество мультимножеств из объектов суммарного веса [math]n[/math].


Утверждение:
[math]M_{n}=m_{n, n}[/math], где [math]m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}[/math] — количество таких мультимножеств, которые содержат объекты, вес которых не больше чем [math]k[/math]. Причем [math]m_{0, i} = 1[/math], а [math]m_{i, 0} = 0[/math], [math]i \ne 0[/math].
[math]\triangleright[/math]

[math]m_{0, i} = 1[/math], так как не набирать никакой вес есть один способ, а [math]m_{i, 0} = 0[/math], [math]i \ne 0[/math], так как нельзя набрать положительный вес из ничего.

Рассуждения аналогичны рассуждениям [math]PSet[/math], однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.
[math]\triangleleft[/math]

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

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

Тогда, [math]M_{n}=m_{n, n}[/math], где [math]m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i}m_{n-ik, k-1}[/math]
[math]M_{0}=m_{0, 0} = 1[/math].
[math]M_{1}=m_{1, 1} = \binom{1}{0}m_{1, 0} + \binom{2}{1}m_{0, 0} = 2m_{0, 0} = 2[/math].
[math]M_{2}=m_{2, 2} = \binom{0}{0}m_{2, 1} + \binom{0}{1} m_{0, 1} = \binom{1}{0}m_{2, 0} + \binom{2}{1}m_{1, 0} + \binom{3}{2}m_{0, 0}= 3m_{0, 0} = 3[/math].
[math]{M_{3}=m_{3, 3} = \binom{0}{0}m_{3, 2} + \binom{0}{1} m_{0, 2} = \binom{0}{0}m_{3, 1} + \binom{0}{1} m_{0, 1} = \binom{1}{0}m_{3, 0} + \binom{2}{1}m_{2, 0} + \binom{3}{2}m_{1, 0} + \binom{4}{3}m_{0, 0}= 4m_{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]{M_{n}=m_{n, n} = \binom{0}{0}m_{n, n-1} + \binom{0}{1} m_{0, n-1} = \binom{0}{0}m_{n, n-2} + \binom{0}{1} m_{0, n-2} = \ldots = \binom{1}{0}m_{n, 0} + \binom{2}{1}m_{n - 1, 0} + \ldots + \binom{n}{n-1}m_{1, 0} + \binom{n+1}{n} m_{0,0} = (n + 1) m_{0,0} = n+1}[/math].

Помеченные унициклические графы

Определение:
[math]Унициклическим[/math] называется связный граф, содержащий один простой цикл и не содержащий петель и кратных рёбер. [math]U_{n}[/math]количество унициклических графов из [math]n[/math] вершин, [math]n \gt 2[/math].


Утверждение:
[math]U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}[/math].
[math]\triangleright[/math]
Для всех [math]r \in [3;n][/math] найдем число способов выбрать вершины для цикла длины [math]r[/math], их количество равняется [math]\binom{n}{r}[/math]. Найдём число способов упорядочить выбранные вершины: заметим что каждый цикл длины [math]r[/math] порождается [math]2r[/math] способами (у каждой перестановки существует [math]r - 1[/math] циклический сдвиг и одно зеркальное представление), поэтому существует [math]\frac{r!}{2r} = \frac{(r-1)!}{2}[/math] различных циклов. Найдём количество способов достроить полученный цикл до связного унициклического графа. Заметим, что при удалениии всех ребер цикла граф станет лесом из [math]r[/math] деревьев и [math]n[/math] вершин. Используя кодирование Прюфера, получим, что количество таких лесов равно [math]r {n}^{n-r-1}[/math]. Нахождение количества таких лесов аналогично нахождению количества помеченных деревьев. Значит, количество унициклических графов порядка [math]n[/math] равно [math]U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}[/math].
[math]\triangleleft[/math]

Связные графы

Определение:
[math]CONN_{n}[/math] - количество связных графов с [math]n[/math] вершинами.


Лемма:
[math]G_{n} = 2^{\binom{n}{2}}[/math], где [math]G_{n}[/math] — количество помеченных графов с [math]n[/math] вершинами.
Утверждение:
[math]CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}[/math], — количество связных графов с [math]n[/math] вершинами.
[math]\triangleright[/math]

Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что [math]CONN_{n}=G_{n}-X_{n}[/math], где [math]X_{n}[/math] — количество несвязных графов. Также [math]X_{n}=\dfrac{Y_{n}}{n}[/math], где [math]Y_{n}[/math] — количество корневых[3] несвязных графов.

Вычислим [math]Y_{n}[/math]. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. [math](k=1\ldots n-1)[/math]. Для каждого [math]k[/math] посчитаем количество таких графов. Количество способов выбрать [math]k[/math] вершин из [math]n[/math] равно [math]\binom{n}{k}[/math]. Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно [math]G_{n-k}[/math]. Количество способов выделить корневую вершину в компоненте связности из [math]k[/math] вершин равно [math]k[/math]. Также количество связных графов в компоненте связности с корневой вершиной равно [math]CONN_{k}[/math].

Итого, для фиксированного [math]k[/math] количество корневых несвязных графов равно

[math]Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}[/math].

Значит, количество несвязных графов с [math]n[/math] вершинами равно

[math]X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}[/math]

Таким образом, количество связных графов с [math]n[/math] вершинами равно

[math]CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}[/math]
[math]\triangleleft[/math]


Пары (Pair)

Определение:
[math]D=Pair(A, B)[/math] — множество всех пар объектов, составленных из элементов [math]A[/math] и [math]B[/math]. [math]D_{n}[/math]количество пар из объектов суммарного веса [math]n[/math].


Утверждение:
[math]D_{n}=\sum\limits_{i=0}^{n}w_{i}u_{n-i}[/math].
[math]\triangleright[/math]
Чтобы составить пару веса [math]n[/math] нужно взять один элемент веса [math]0 \leqslant i \leqslant n[/math] из [math]A[/math] и элемент веса [math]n-i[/math] из [math]B[/math] , что полностью соответствует данной формуле.
[math]\triangleleft[/math]

Циклы (Cycle)

Определение:
[math]C=Cycle(A)[/math] — множество всех циклов [4] из элементов [math]A[/math]. [math]C_{n}[/math]количество циклов веса [math]n[/math].


Утверждение:
[math]C_{n}=\sum\limits_{s=1}^{n}c_{n, s}[/math], где [math]c_{n,s}=\sum\limits_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}[/math], — количество циклов веса [math]n[/math] длины [math]s[/math], а [math]|St(\vec{i})|[/math] — количество стабилизаторов для циклического сдвига на [math]i[/math] .
[math]\triangleright[/math]
Очевидно, что длина цикла веса [math]n[/math] может быть от [math]1[/math] до [math]n[/math]. Посмотрим сколько существует циклов каждой длины. Это можно сделать по лемме Бёрнсайда.
[math]\triangleleft[/math]
Лемма:
Найдем [math]|St(\vec{i})|=z_{n,s,i}[/math] в общем случае.
Доказательство:
[math]\triangleright[/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\limits_{i=1}^{n}w_{i}b_{n-i, k-1}[/math], причем [math]b_{n,1}=w_{n}[/math].
[math]\triangleleft[/math]

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

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

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

[math]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)}[/math]. Поскольку все бусины имеют одинаковый вес [math]1[/math], то [math]b_{n,k} \neq 0[/math]

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

Метод производящих функций

Такие большие группы часто анализируют с помощью производящих функций. Один из популярных методов — метод символов [5]. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества. При непомеченных объектах рассмотренные классы имеют следующие производящие функции:

[math]Seq(A)[/math] [math]\dfrac{1}{1-A(z)}[/math]
[math]PSet(A)[/math] [math]\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}A(z^{k})}{k})[/math]
[math]MSet(A)[/math] [math]\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})[/math]
[math]Pair(A,B)[/math] [math]A(z)B(z)[/math]
[math]Cycle(A)[/math] [math]\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}[/math], где [math]\phi(n)[/math] функция Эйлера.

Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — помеченные графы. С помеченными объектами используется экспоненциальная производящая функция [6]. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:

[math]Seq(A)[/math] [math]\dfrac{1}{1-A(z)}[/math]
[math]Pset(A)[/math] [math]\exp(A(z))[/math]
[math]Pair(A,B)[/math] [math]A(z)B(z)[/math]
[math]Cycle(A)[/math] [math]\ln\dfrac{1}{1-A(z)}[/math].

Ограниченные конструкции

Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, [math]Seq_{k}(A)[/math][math]k[/math] компонентов).

Непосредственной формулой для производящих функций является диагональ [math]\Delta[/math] декартова произведения [7] [math]A \times A[/math], определяемая как [math]B \equiv \Delta(A \times A) : \{(a, a) \mid a \in A\}[/math]. Тогда имеет место соотношение [math]B(z)=A(z^{2})[/math].

Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из [math]A[/math], то есть к [math]P = PSet_{2}(A)[/math]. Прямое выражение выполняется следующим способом: неупорядоченная пара [math]\langle \alpha, \beta \rangle [/math] связана с двумя упорядоченными парами [math](\langle \alpha, \beta \rangle [/math] и [math]\langle \beta, \alpha \rangle )[/math], кроме тех случаев, когда [math]\alpha = \beta[/math], то есть когда пара лежит на диагонали декартова произведения. Другими словами, [math]PSet_{2}(A) + PSet_{2}(A) + \Delta(A \times A) \cong A \times A[/math].

Это, в свою очередь, означает что [math]2P(z) + A(z^{2}) = A(z)^{2}[/math]. Таким образом можно выразить [math]PSet_{2}(A)[/math]. Аналогично для [math]Seq_{2}(A)[/math], [math]MSet_{2}(A)[/math] и [math]Cycle_{2}(A)[/math]:

[math]Seq_{2}(A)[/math] [math]A(z)^{2}[/math]
[math]PSet_{2}(A)[/math] [math]\dfrac{A(z)^{2}}{2}-\dfrac{A(z^{2})}{2}[/math]
[math]MSet_{2}(A)[/math] [math]\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}[/math]
[math]Cycle_{2}(A)[/math] [math]\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}[/math]

Аналогичные рассуждения можно провести и для больших [math]k[/math], однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов — теорема Пойа.

Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа [8]. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:

[math]Seq_{k}(A)[/math] [math]A(z)^{k}[/math]
[math]PSet_{k}(A)[/math] [math][u^{k}]\exp(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i})[/math]
[math]MSet_{k}(A)[/math] [math][u^{k}]\exp(\sum\limits_{i=1}^{k}\dfrac{u^{i}A(z^{i})}{i})[/math]
[math]Cycle_{k}(A)[/math] [math][u^{k}]\sum\limits_{i \geqslant 1}\dfrac{\phi(i)}{i}\ln\dfrac{1}{1 - u^{i}A(z^i)}[/math], где [math]\phi(n)[/math] функция Эйлера.

См.также

Примeчания

Источники информации