Задача
COM-B2-M03-P018 Код Прюфера
Докажите, что число помеченных деревьев на вершинах \(1,\ldots,n\) равно \(n^{n-2}\).
Постройте код длины \(n-2\): каждый раз удаляйте лист с наименьшим номером и записывайте его соседа.
Из дерева строим последовательность длины \(n-2\): пока осталось больше двух вершин, удаляем лист с наименьшей меткой и записываем метку его соседа. Обратно, по последовательности \(c_1,\ldots,c_{n-2}\) восстанавливаем дерево: на каждом шаге берём наименьшую метку, которой нет в текущей последовательности, соединяем её с \(c_1\), затем удаляем эту метку из набора вершин и удаляем \(c_1\) из последовательности. В конце соединяем две оставшиеся вершины.
Эти процедуры обратны: удалённый на каждом шаге лист именно та наименьшая метка, которая больше не появится в коде. Поэтому деревья биективны последовательностям длины \(n-2\) над алфавитом из \(n\) меток. Таких последовательностей \(n^{n-2}\).
Сложная, но очень ценная биекция; можно вынести как challenge.