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

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

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

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

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

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

Число помеченных деревьев порядка [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]\triangleleft[/math]