Изменения

В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество(то есть <tex dpi="130">w_{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>.

==Помеченные унициклические графы=Подсчет подвешенных непомеченных деревьев без порядка на детях= {{Определение|definition=<tex dpi=Пусть "130">Унициклическим</tex> называется связный граф, содержащий один простой цикл и не содержащий петель и кратных рёбер. <tex dpi="130150">T_U_{n}</tex> {{---}} '''количество таких деревьев с унициклических графов''' из <tex dpi="130">n</tex> вершинами. вершин, <tex dpi="130">F=MSet(T)n > 2</tex> .}} {{---}} множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. Утверждение|statement=<tex dpi="130150">F_U_{n}=f_\sum\limits_{r=3}^{n,}\binom{n}</tex> {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">f_\binom{n, k}{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">nr</tex> вершин, что деревья в них содержат не более чем деревьев и <tex dpi="130">kn</tex> вершин. Чтобы получить дерево из Используя [[Коды Прюфера|кодирование Прюфера]], получим, что количество таких лесов равно <tex dpi="130">r {n}^{n-r-1}</tex> вершин. Нахождение количества таких лесов аналогично нахождению [[Количество помеченных деревьев|количества помеченных деревьев]]. Значит, достаточно взять количество унициклических графов порядка <tex dpi="130">1n</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="150130">T_CONN_{n}</tex> - количество связных графов с <tex dpi=F_{"130">n-1}</tex>вершинами.:}} {{Лемма|statement=<tex dpi="150">F_G_{n}=f_2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex>{{---}} количество помеченных графов с <tex dpi="130">n</tex> вершинами.:}} {{Утверждение|statement=<tex dpi="150">fCONN_{n,k}=G_{n} - \frac{1}{n}\sum\limits_{ik=01}^{n-1}k\lfloor \fracbinom{n}{k} \rfloorG_{n-k} \binom{T_CONN_{k}+i</tex>, {{--1-}}количество связных графов с <tex dpi="130">n</tex> вершинами.|proof= Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{in} s_=G_{n}-ikX_{n}</tex>, kгде <tex dpi="150">X_{n}</tex> {{---1}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex>{{---}} количество корневых<ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref> несвязных графов.

Количество таких деревьев с Вычислим <tex dpi="130150">Y_{n}</tex> вершинами образуют последовательность . Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. <tex dpi="130150"> (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>. Оставшийся граф является произвольным, 2таким образом, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldotsколичество помеченных графов в нем равно <tex dpi="150">G_{n-k}</tex> . Количество способов выделить корневую вершину в компоненте связности из <reftex dpi="150">[http:k</tex> вершин равно <tex dpi="150">k</oeistex>.org/A000081 Number of unlabeled rooted trees with n node]Также количество связных графов в компоненте связности с корневой вершиной равно <tex dpi="150">CONN_{k}</reftex> .

[[File:ForestsИтого, для фиксированного <tex dpi="150">k</tex> количество корневых несвязных графов равно <tex dpi="150">Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}</tex>.png|670px]][[File:Rooted_Trees.png|700px]]Значит, количество несвязных графов с <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>}}