Изменения
→См.также
}}
В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество(то есть <tex dpi="130">w_{0}=1</tex>).
Тогда, <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">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)|динамического программирования]].
==Мультимножества (MSet)==
:<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>.
==Помеченные унициклические графы==
|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> вершинами.
}}
{{Лемма
|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>[[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)==
|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)==
*[[Числа Каталана]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Подсчет деревьев]]
*[[Метод производящих функций]]
==Примeчания==
