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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (oops)
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 3 участников)
Строка 1: Строка 1:
{{В разработке}}
+
Описание всех используемых далее комбинаторных объектов можно найти в статье [[Конструирование комбинаторных объектов и их подсчёт|"конструирование комбинаторных объектов и их подсчёт"]].
 +
= Непомеченные [[Дерево, эквивалентные определения|деревья]] =
 +
== Бинарные деревья ==
 +
{{Утверждение
 +
|id=unmarked_bin
 +
|statement=Число непомеченных бинарных деревьев <tex>T_n</tex> равно <tex>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>T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}</tex>.
== Подвешенные неполные двоичные деревья ==
+
|proof=
Пусть <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>T = z + z\times T\times T</tex>.<br>
:<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>T(s) = s + s{T(s)}^2</tex>.
 +
Решением данного уравнения будет <tex>T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}</tex>.
 +
}}
  
 
== Подвешенные непомеченные деревьея с порядком на детях ==
 
== Подвешенные непомеченные деревьея с порядком на детях ==
Строка 12: Строка 26:
 
:<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>-ое [[Числа Каталана|число Каталана]].
 
:<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]]
+
<gallery mode="packed-hover" widths=400px heights=300px>
[[File:Ordered_Rooted_Trees.png|700px]]
+
Image:Sequence_of_rooted_Trees.png|''Последовательность корневых деревьев''
 +
Image:Ordered_Rooted_Trees.png|''Последовательность помеченных корневых деревьев''
 +
</gallery>
  
 
== Подвешенные непомеченные деревья без порядка на детях ==
 
== Подвешенные непомеченные деревья без порядка на детях ==
Строка 19: Строка 35:
 
:<tex dpi="150">T_{n}=F_{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}=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="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>  
+
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность A000081<ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref>.
  
[[File:Forests.png|670px]]
+
<gallery mode="packed-hover" widths=400px heights=300px>
[[File:Rooted_Trees.png|700px]]
+
Image:Forests.png|''Последовательность леса''
 +
Image:Rooted_Trees.png|''Последовательность корневых деревьев''
 +
</gallery>
  
 
= Помеченные деревья =
 
= Помеченные деревья =
 +
{{Определение
 +
|definition=
 +
'''Помеченное дерево''' c <tex>n</tex> вершинами - дерево c <tex>n</tex> вершинами, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
 +
}}
 +
 
{{Теорема
 
{{Теорема
|author=Формула Кэли
+
|author=Кэли
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
+
|id=th_kelly
 +
|statement=Число помеченных деревьев с <tex>n</tex> вершинами равно <tex>n^{n - 2}</tex>.
 
|proof=
 
|proof=
 
Можно доказать формулу двумя способами.
 
Можно доказать формулу двумя способами.
Строка 35: Строка 59:
 
''Первый способ.''  
 
''Первый способ.''  
  
Так как между помеченными деревьями порядка <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>.
+
: Так как между помеченными деревьями 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> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>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 - 1}</tex>.
 +
|proof=
 +
Данное утверждение является следствием [[#th_kelly|теоремы Кэли]].<br>
 +
Обозначим через <tex>T_n</tex> число корневых помеченных деревьев с <tex>n</tex> вершинами, т.е. число помеченных деревьев, в которых одна из вершин выделена и названа корнем.<br>
 +
Число корневых помеченных деревьев с <tex>n</tex> вершинами в <tex>n</tex> раз больше числа помеченных деревьев с <tex>n</tex> вершинами: в качестве корня можно выбрать любую из <tex>n</tex> различных вершин.
 +
}}
 +
 +
== Подвешенные помеченные деревья с порядком на детях ==
 +
{{Утверждение
 +
|statement=Число помеченных корневых деревьев с <tex>n</tex> вершинами с порядком на детях есть <tex>T_n = n!\cdot C_n</tex>.
 +
|proof=
 +
Как и в непомеченном случае, структура объекта остается неизменной:<br>
 +
: <tex>T = U\times Seq(T)</tex><br>
 +
Производящая функция будет иметь вид:<br>
 +
: <tex>T(s) = s\dfrac{1}{1 - T(s)} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{1 - \sqrt{1 - 4s}}{2} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{C_nn!}{n!}s^n</tex><br>
 +
Таким образом, число помеченных корневых деревьев с <tex>n</tex> с порядком на детях вершинами есть <tex>T_n = n!\cdot C_n</tex>
 +
}}
 +
 +
== Подвешенные помеченные деревья без порядка на детях ==
 +
{{Утверждение
 +
|statement=Как и в непомеченном случае, структура объекта остается неизменной: <tex>T = U\times Set(T)</tex>.<br>
 +
Производящая функция будет иметь вид: <tex>T(s) = s\cdot e^{T(s)}</tex><br>
 +
}}
 +
В предыдущем пункте порядок на детях однозначно задавал, как будут располагаться поддеревья, теперь же подсчёт оказывается сложнее:
 +
[[File:Marked_trees_no_order_example.jpg|250px|left]]
 +
<br>
 +
<br>
 +
В данном примере в А два представленных дерева {{---}} одинаковые, а в B {{---}} разные.<br>
 +
Для <tex>T(s)</tex> нет однозначно выражаемой формулы. Однако, <tex>T_n</tex> можно получить, раскрыв экспоненту до <tex>n</tex>-ого члена, а именно <tex>e^{T(s)} = \sum\limits_{k = 0}^{n}\dfrac{(T(s))^k}{k!}</tex><br>
 +
Более подробное объяснение происходящего можно посмотреть в лекции<ref>Станкевич А.С. Лекции по дискретной математике // Помеченные объекты и экспоненциальные ПФ, 2020. URL: https://youtu.be/6qQQj6G8-tA?t=4391</ref>.
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
  
 
= См.также =
 
= См.также =
 +
*[[Конструирование комбинаторных объектов и их подсчёт]]
 
*[[Лемма Бёрнсайда и Теорема Пойа]]
 
*[[Лемма Бёрнсайда и Теорема Пойа]]
 
*[[Числа Каталана]]
 
*[[Числа Каталана]]
Строка 47: Строка 109:
  
 
= Литература =
 
= Литература =
 +
 +
[[Категория: Дискретная математика]]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]
 +
[[Категория: Подсчёт числа объектов]]
 +
[[Категория: Комбинаторные объекты]]
 +
[[Категория: Свойства комбинаторных объектов]]

Текущая версия на 19:40, 4 сентября 2022

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

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

Бинарные деревья

Утверждение:
Число непомеченных бинарных деревьев [math]T_n[/math] равно [math]C_{n}[/math] ([math]n[/math]-ое число Каталана).
[math]\triangleright[/math]

Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом [math]T = \varepsilon + z\times T\times T[/math].
В терминах производящих функций эта конструкция выглядит следующим образом [math]T(s) = 1 + s{T(s)}^2[/math]. Решением данного уравнения будет [math]T(s) = \frac{1 - \sqrt{1 - 4s}}{2s}[/math]. Тогда:

[math]T_{n} = Pair(T, \; T_{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]\triangleleft[/math]
Утверждение:
Производящая функция числа непомеченных полных бинарных деревьев: [math]T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}[/math].
[math]\triangleright[/math]

Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом [math]T = z + z\times T\times T[/math].
В терминах производящих функций эта конструкция выглядит следующим образом [math]T(s) = s + s{T(s)}^2[/math].

Решением данного уравнения будет [math]T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}[/math].
[math]\triangleleft[/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] вершинами образуют последовательность A000081[1].

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

Определение:
Помеченное дерево c [math]n[/math] вершинами - дерево c [math]n[/math] вершинами, вершинам которого взаимно однозначно соответствуют числа от 1 до n.


Теорема (Кэли):
Число помеченных деревьев с [math]n[/math] вершинами равно [math]n^{n - 2}[/math].
Доказательство:
[math]\triangleright[/math]

Можно доказать формулу двумя способами.

Первый способ.

Так как между помеченными деревьями c [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] вершинах. Число помеченных деревьев c [math]n[/math] вершинами, очевидно, равно числу остовов в полном графе [math]K_n[/math], которое есть [math]n^{n-2}[/math] по следствию теоремы Кирхгофа.
[math]\triangleleft[/math]
Утверждение:
Число помеченных корневых деревьев с [math]n[/math] вершинами есть [math]T_n = n^{n - 1}[/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]

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

Утверждение:
Число помеченных корневых деревьев с [math]n[/math] вершинами с порядком на детях есть [math]T_n = n!\cdot C_n[/math].
[math]\triangleright[/math]

Как и в непомеченном случае, структура объекта остается неизменной:

[math]T = U\times Seq(T)[/math]

Производящая функция будет иметь вид:

[math]T(s) = s\dfrac{1}{1 - T(s)} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{1 - \sqrt{1 - 4s}}{2} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{C_nn!}{n!}s^n[/math]
Таким образом, число помеченных корневых деревьев с [math]n[/math] с порядком на детях вершинами есть [math]T_n = n!\cdot C_n[/math]
[math]\triangleleft[/math]

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

Утверждение:
Как и в непомеченном случае, структура объекта остается неизменной: [math]T = U\times Set(T)[/math].
Производящая функция будет иметь вид: [math]T(s) = s\cdot e^{T(s)}[/math]

В предыдущем пункте порядок на детях однозначно задавал, как будут располагаться поддеревья, теперь же подсчёт оказывается сложнее:

Marked trees no order example.jpg



В данном примере в А два представленных дерева — одинаковые, а в B — разные.
Для [math]T(s)[/math] нет однозначно выражаемой формулы. Однако, [math]T_n[/math] можно получить, раскрыв экспоненту до [math]n[/math]-ого члена, а именно [math]e^{T(s)} = \sum\limits_{k = 0}^{n}\dfrac{(T(s))^k}{k!}[/math]
Более подробное объяснение происходящего можно посмотреть в лекции[2].




См.также

Литература

  1. Number of unlabeled rooted trees with n node
  2. Станкевич А.С. Лекции по дискретной математике // Помеченные объекты и экспоненциальные ПФ, 2020. URL: https://youtu.be/6qQQj6G8-tA?t=4391