Изменения

==Унициклические Помеченные унициклические графы c порядком на детях==

|definition=<tex dpi="130">Унициклическим</tex> называется связный граф, содержащий один простой цикли не содержащий петель и кратных рёбер. <tex dpi="150">U_{n}</tex> {{---}} '''количество унициклических графов''' из <tex dpi="130">n</tex> вершин, <tex dpi="130">n > 2</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>.