Количество помеченных деревьев

Помеченное дерево

Определение:

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

Количество помеченных деревьев

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

Дискретная математика: Алгоритмы. Формула Кэли