Для помеченных деревьев существует эффективный способ кодирования(его можно использовать для компьютерного представления деревьев).
Найдем лист с минимальным номером, удалим его вместе с инцидентной дугой и запишем номер второй вершины этой дуги. В получившемся после удаления дереве поступаем аналогично и т.д. p-2 раза. Таким образом, код является последовательностью длины p-2, элементы которой – числа от 1 до p.
Разумеется, код полезен тогда, когда существует метод декодирования, т.е. восстановления дерева по коду. Опишем соответствующий алгоритм. Выпишем произвольный код, а под ним числа от 1 до p. Находим в нижней последовательности минимальное число, которого нет в коде (такие числа существуют, поскольку код короче p), соединяем вершину с этим номером с вершиной, номер которой в коде первый, вычеркиваем из последовательностей оба эти элемента. Далее продолжаем. В конце в нижней последовательности остаются два числа, соответствующие вершины соединяем дугой.
Поскольку коды деревьев это размещения с повторениями, справедлив следующий результат.
Теорема 18(Кэли). Число помеченных деревьев с p вершинами равно pp-2.
Это число гигантское, сопоставимое с p!. Обозреть все помеченные деревья даже при небольших p (порядка 10) невозможно.