Подсчет деревьев

Эта статья находится в разработке!

Описание всех используемых далее комбинаторных объектов можно найти в статье "конструирование комбинаторных объектов и их подсчёт".

Непомеченные деревья

Подвешенные неполные двоичные деревья

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами. [math]D=Pair(T, T)[/math] — множество всех пар из данных деревьев. Чтобы получить двоичное дерево из [math]n[/math] вершин, достаточно взять [math]1[/math] вершину и подвесить к ней левого и правого сына с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=D_{n-1}=\sum\limits_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}[/math], где [math]C_{n}[/math] — [math]n[/math]-ое число Каталана.

Подвешенные непомеченные деревьея с порядком на детях

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами. [math]S=Seq(A)[/math] — множество всех последовательностей из данных деревьев. [math]S_{n}[/math] — количество последовательностей с суммарным количество вершин [math]n[/math]. Чтобы получить дерево из [math]n[/math] вершин, достаточно взять [math]1[/math] вершину, и подвесить к ней последовательность деревьев с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=S_{n-1}[/math].

[math]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}[/math], где [math]C_{n}[/math] — [math]n[/math]-ое число Каталана.

Подвешенные непомеченные деревья без порядка на детях

Пусть [math]T_{n}[/math] — количество таких деревьев с [math]n[/math] вершинами. [math]F=MSet(T)[/math] — множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. [math]F_{n}=f_{n,n}[/math] — количество лесов с суммарным количество вершин [math]n[/math]. [math]f_{n, k}[/math] — количество таких лесов из [math]n[/math] вершин, что деревья в них содержат не более чем [math]k[/math] вершин. Чтобы получить дерево из [math]n[/math] вершин, достаточно взять [math]1[/math] вершину и подвесить к ней лес деревьев с суммарным количеством вершин [math]n-1[/math]. Тогда:

[math]T_{n}=F_{n-1}[/math].

[math]F_{n}=f_{n, n}[/math].

[math]f{n,k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}[/math].

Количество таких деревьев с [math]n[/math] вершинами образуют последовательность [math] 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots[/math]

Помеченные деревья

Теорема (Кэли):

Число помеченных деревьев с [math]n[/math] вершинами равно [math]n^{n - 2}[/math].

Доказательство:

[math]\triangleright[/math]

Можно доказать формулу двумя способами. Первый способ. Так как между помеченными деревьями порядка [math]n[/math] и последовательностями длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] существует биекция (Код Прюфера), то количество помеченных деревьев совпадает с количеством последовательностей длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n = n^{n - 2}[/math]. Второй способ. С помощью матрицы Кирхгофа для полного графа на [math]n[/math] вершинах. Число помеченных деревьев порядка [math]n[/math], очевидно, равно числу остовов в полном графе [math]K_n[/math], которое есть [math]n^{n-2}[/math] по следствию теоремы Кирхгофа.

[math]\triangleleft[/math]

Утверждение:

Число помеченных корневых деревьев с [math]n[/math] вершинами есть [math]T_n = n^{n - 2}[/math].

[math]\triangleright[/math]

Данное утверждение является следствием теоремы Кэли. Обозначим через [math]T_n[/math] число корневых помеченных деревьев с [math]n[/math] вершинами, т.е. число помеченных деревьев, в которых одна из вершин выделена и названа корнем. Число корневых помеченных деревьев с [math]n[/math] вершинами в [math]n[/math] раз больше числа помеченных деревьев с [math]n[/math] вершинами: в качестве корня можно выбрать любую из [math]n[/math] различных вершин.

[math]\triangleleft[/math]

Дополнительно

Теорема (Скойнс):

Число 2-раскрашенных деревьев с [math]m[/math] вершинами одного цвета и [math]n[/math] вершинами другого равно [math]S_n = n^{m - 1} m^{n - 1}[/math].

См.также

• Лемма Бёрнсайда и Теорема Пойа
• Числа Каталана
• Генерация комбинаторных объектов в лексикографическом порядке