Изменения
Добавлен раздел про количество связных графов. Гранкин Максим 1 курс M3137
Пусть <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)|динамического программирования]].
==Количество связных графов==
{{Определение
|definition=
<tex dpi="130">CONN_{n}</tex> - количество связных графов порядка <tex dpi="130">n</tex>.
}}
{{Лемма
|statement=
<tex dpi="130">G_{n}=2^{\binom{n}{2}}</tex>, {{---}} количество помеченных графов.
}}
{{Утверждение
|statement=
<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}2^{\binom{n-k}{2}}CONN_{k}</tex>, {{---}} количество связных графов порядка n.
|proof=
Пусть <tex dpi="150">X</tex> {{---}} количество '''несвязных графов'''. Тогда количество '''связных графов''' равно <tex dpi="150">G_{n}-X</tex>.
Пусть <tex dpi="150">Y</tex> {{---}} количество '''количество корневых несвязных графов'''. Тогда количество '''несвязных графов''' равно <tex dpi="150">\dfrac{Y}{n}</tex>.
Заметим, что, так как граф является '''несвязным''', то в нём найдётся компонента связности, внутри которой лежит корневая вершина <ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref>, а остальной граф будет представлять собой одну или более компонент связности.
Переберем количество вершин в компоненте связности, содержащей корневую вершину. <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">CONN_{k}</tex>.
В-третьих, оставшийся граф из <tex dpi="150">n-k</tex> вершин является произвольным графом, поэтому он даёт множитель <tex dpi="150">G_{n-k}</tex>.
В-четвертых, количество способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>.
Итого, при фиксированном <tex dpi="150">k</tex> количество корневых несвязных графов равно:
<tex dpi="150">k\binom{n}{k}CONN_{k}G_{n-k}</tex>.
Значит, количество несвязных графов с <tex dpi="150">n</tex> вершинами равно:
<tex dpi="150">\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>
Наконец, искомое количество связных графов равно:
<tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>
}}
