Изменения
→См.также
{{Определение
|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=
'''База <tex dpi="130"">n = 1</tex>'''.
Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex> <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]].
Тогда, <tex dpi="150">S_{n}=\sum_sum\limits\limits_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}</tex>.
===Подсчет 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_{1}=1</tex>.
Тогда, <tex dpi="150">S_{n}=\sum_sum\limits_{i=1}^{n} w_{i} S_{n-1i}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex dpi="150">F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.
===Подсчет подвешенных непомеченных деревьев с порядком на детях===Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами. <tex dpi="130">S=SeqМножества (APSet)</tex> {{---}} множество всех последовательностей из данных деревьев. <tex dpi="130">S_{n}</tex> {{---}} количество последовательностей с суммарным количество вершин <tex dpi="130">n</tex>. Чтобы получить дерево из <tex dpi="130">n</tex> вершин, достаточно взять <tex dpi="130">1</tex> вершину, и подвесить к ней последовательность деревьев с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда::<tex dpi="150">T_{n}=S_{n-1}</tex>.:<tex dpi="150">S_{n}=\sum_{i=1}^{n} T_{i} S_{n-i}=\sum_{i=1}^{n} S_{i-1} S_{n-i}=\sum_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].
{{Утверждение
|statement=
}}
===Количество 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="150">P_{n}=p_{n, n}</tex>, где <tex tex dpi="150">p_{n, k}=\sum_sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} 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{12}{0}p_{1, 0} + \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}{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">{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">\{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">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)|динамического программирования]].
===Количество разбиений на слагаемые===Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">P=PSetМультимножества (AMSet)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</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} = p_{n, k-1} + p_{n - k, k}</tex>, что, как несложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].
{{Определение
|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>.
}}
{{Утверждение
|statement=
}}
===Количество MSet из элементов 0 и 1===
Пусть <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="130">w_{0} = 1</tex>.:Тогда, <tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum_sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{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} + \binom{2}{1}m_{0, 0} = 2m_{0, 0} = 2</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>.
==Помеченные унициклические графы=Подсчет подвешенных непомеченных деревьев без порядка на детях===Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</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>.:<tex dpi="150">f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>.
{{Утверждение|statement=<tex dpi="150">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> вершин. Используя [File:Forests[Коды Прюфера|кодирование Прюфера]], получим, что количество таких лесов равно <tex dpi="130">r {n}^{n-r-1}</tex>.pngНахождение количества таких лесов аналогично нахождению [[Количество помеченных деревьев|670pxколичества помеченных деревьев]]. Значит, количество унициклических графов порядка <tex dpi="130">n</tex> равно <tex dpi="130">U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}</tex>.}} ==Связные графы=={{Определение|definition=<tex dpi="130">CONN_{n}</tex> - количество связных графов с <tex dpi="130">n</tex> вершинами.}} {{Лемма|statement=<tex dpi="150">G_{n} = 2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex> {{---}} количество помеченных графов с <tex dpi="130">n</tex> вершинами.}} {{Утверждение|statement=<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов с <tex dpi="130">n</tex> вершинами.|proof= Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{n}=G_{n}-X_{n}</tex>, где <tex dpi="150">X_{n}</tex> {{---}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex> {{---}} количество корневых<ref>[[Filewikipedia:Rooted_Trees.pngRooted_graph |700pxWikipedia {{---}} Корневой граф]]</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=
|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">T_{n}C=Cycle(A)</tex> {{---}} количество таких деревьев с множество всех циклов <tex dpi="130">n</tex> вершинами. <tex dpi="130">D=Pair(T, T)</texref> [[wikipedia:Cyclic order | Wikipedia {{---}} множество всех пар из данных деревьев. Чтобы получить двоичное дерево из <tex dpi="130">nЦиклы]]</texref> вершин, достаточно взять из элементов <tex dpi="130">1</tex> вершину и подвесить к ней левого и правого сына с суммарным количеством вершин <tex dpi="130">n-1A</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="150">b_{n,k}</tex> {{---}} число способов упорядочить набор из <tex dpi="150">k</tex> элементов суммарного веса <tex dpi="150">n</tex> и
<tex dpi="150">b_{n,k}=\sum_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_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_sum\limits_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum_sum\limits_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum_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_sum\limits_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}</tex>.
==Метод производящих функций==
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов <ref>[[wikipedia:Symbolic method (англ. ''combinatorics) | Wikipedia {{---}} Symbolic method'')]]</ref>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, <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">k</tex>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{- --}} [[Лемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана—Лагранжа Бюрмана-Лагранжа <ref>[[wikipedia:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, ограниченные конструкции производящие функции ограниченных конструкций можно подсчитать следующим способом:
{| class="wikitable"
*[[Числа Каталана]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Подсчет деревьев]]
*[[Метод производящих функций]]
==Примeчания==