Изменения

Описание всех используемых далее комбинаторных объектов можно найти в статье [[Конструирование комбинаторных объектов и их подсчёт|"конструирование комбинаторных объектов и их подсчёт"]].= Непомеченные [[Дерево, эквивалентные определения|деревья]] === Бинарные деревья =={{Утверждение|id=unmarked_bin|statement=Число непомеченных бинарных деревьев: <tex>T_n = C_{n}</tex> (<tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]]).|proof=Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом <tex>T = \varepsilon + z\times T\times T</tex>.<br>В разработкетерминах производящих функций эта конструкция выглядит следующим образом <tex>T(s) = 1 + s{T(s)}^2</tex>.Решением данного уравнения будет <tex>T(s) = \frac{1 - \sqrt{1 - 4s}}{2s}</tex>.Тогда::<tex dpi="150">T_{n} = Pair(T, \; T_{n-1}) = \sum\limits_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].}}

Описание всех используемых далее комбинаторных объектов можно найти в статье [[Конструирование комбинаторных объектов и их подсчёт{{Утверждение|"конструирование комбинаторных объектов и их подсчёт"]].statement= Непомеченные деревья === Подвешенные неполные двоичные деревья ==Пусть Производящая функция числа непомеченных полных бинарных деревьев: <tex dpi>T(s) ="130">T_{n}</tex> \frac{1 - \sqrt{1 ---4s^2}}{2s} количество таких деревьев с <tex dpi="130">n</tex> вершинами. |proof=Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом <tex dpi="130">DT =Pair(z + z\times T, \times T)</tex> {{---}} множество всех пар из данных деревьев. Чтобы получить двоичное дерево из <tex dpi="130"br>nВ терминах производящих функций эта конструкция выглядит следующим образом </tex> вершин, достаточно взять <tex dpiT(s) ="130">1</tex> вершину и подвесить к ней левого и правого сына с суммарным количеством вершин <tex dpi="130">n-1s + s{T(s)}^2</tex>. Тогда::Решением данного уравнения будет <tex dpi="150">T_{n}T(s) =D_\frac{n1 -1}=\sum\limits_{i=0}^sqrt{n-1}T_{i}T_{n-i-14s^2}=C_{n}</tex>, где <tex dpi="150">C_{n2s}</tex> {{---.}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].

[[File<gallery mode="packed-hover" widths=400px heights=300px>Image:Sequence_of_rooted_Trees.png|750px]]''Последовательность корневых деревьев''[[FileImage:Ordered_Rooted_Trees.png|700px]]''Последовательность помеченных корневых деревьев''</gallery>

:<tex dpi="150">ff_{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> A000081<ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref> .

[[File<gallery mode="packed-hover" widths=400px heights=300px>Image:Forests.png|670px]]''Последовательность леса''[[FileImage:Rooted_Trees.png|700px]]''Последовательность корневых деревьев''</gallery>

: Так как между помеченными деревьями порядка c <tex>n</tex> вершинами и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция ([[Коды Прюфера|Код Прюфера]]), то количество помеченных деревьев совпадает с количеством последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n = n^{n - 2}</tex>.

: С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> вершинах. Число помеченных деревьев порядка c <tex>n</tex>вершинами, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.

|statement=Число помеченных корневых деревьев с <tex>n</tex> вершинами есть <tex>T_n = n^{n - 21}</tex>.