Тогда, <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>.
===Подсчет подвешенных непомеченных деревьев с порядком на детях===
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами. <tex dpi="130">S=Seq(A)</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\limits_{i=1}^{n} T_{i} S_{n-i}=\sum\limits_{i=1}^{n} S_{i-1} S_{n-i}=\sum\limits_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].
[[File:Sequence_of_rooted_Trees.png|750px]]
[[File:Ordered_Rooted_Trees.png|700px]]
==Множества (PSet)==
:<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\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>.
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex> <ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref>
[[File:Forests.png|670px]]
[[File:Rooted_Trees.png|700px]]
==Помеченные унициклические графы==
*[[Числа Каталана]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Подсчет деревьев]]
==Примeчания==
