286
правок
Изменения
+Pair
[[File:Rooted_Trees.png|700px]]
==Пары(Pair)==
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex>, <tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{m}\}</tex> {{---}} множества из различных объектов, <tex dpi="130">S=Pair(A, B)</tex> {{---}} множество всех пар объектов, составленных из элементов <tex dpi="130">A</tex> и <tex dpi="130">B</tex>. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, составленных из элементов <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{k}\}</tex> {{---}} соответственно для <tex dpi="130">B</tex>. Тогда '''количество пар''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=0}^{n}w_{i}u_{n-i}</tex>.
}}
===Количество подвешенных неполных двоичных деревьев===
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">S=Pair(T, T)</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}=\sum_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].
==Примeчания==
<references/>
