Подсчет деревьев — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Literature section added)
м (oops)
Строка 6: Строка 6:
 
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами. <tex dpi="130">D=Pair(T, T)</tex> {{---}} множество всех пар из данных деревьев. Чтобы получить двоичное дерево из <tex dpi="130">n</tex> вершин, достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней левого и правого сына с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда:
 
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами. <tex dpi="130">D=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}=D_{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>-ое [[Числа Каталана|число Каталана]].
 
:<tex dpi="150">T_{n}=D_{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>-ое [[Числа Каталана|число Каталана]].
 
= Помеченные деревья =
 
{{Теорема
 
|author=Формула Кэли
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|proof=
 
Можно доказать формулу двумя способами.
 
 
''Первый способ.''
 
 
Так как между помеченными деревьями порядка <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> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
 
}}
 
  
 
== Подвешенные непомеченные деревьея с порядком на детях ==
 
== Подвешенные непомеченные деревьея с порядком на детях ==
Строка 40: Строка 25:
 
[[File:Forests.png|670px]]
 
[[File:Forests.png|670px]]
 
[[File:Rooted_Trees.png|700px]]
 
[[File:Rooted_Trees.png|700px]]
 +
 +
= Помеченные деревья =
 +
{{Теорема
 +
|author=Формула Кэли
 +
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 +
|proof=
 +
Можно доказать формулу двумя способами.
 +
 +
''Первый способ.''
 +
 +
Так как между помеченными деревьями порядка <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> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
 +
}}
  
 
= См.также =
 
= См.также =

Версия 22:22, 8 июня 2020

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

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

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

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

Пусть [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]-ое число Каталана.

Sequence of rooted Trees.png Ordered Rooted Trees.png

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

Пусть [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] [1]

Forests.png Rooted Trees.png

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

Теорема (Формула Кэли):
Число помеченных деревьев порядка [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]

См.также

Литература