Дано: n вершин в дереве.
Найти: количество упорядоченных деревьев с n вершинами.
Решение:
1. По определению, упорядоченное дерево — это дерево, в котором порядок дочерних узлов для каждого узла имеет значение.
2. Для n-вершинного дерева существует n^(n-2) различных деревьев по теореме Кэли. Это количество деревьев определяется тем, что на каждой итерации добавления новой вершины мы можем выбирать, к какой из уже существующих вершин присоединить новую вершину.
3. Рассмотрим процесс построения упорядоченного дерева:
- Сначала выбираем корень дерева (одну из n вершин).
- Затем добавляем оставшиеся n - 1 вершин по одному. Каждую новую вершину можно прикрепить к любой из уже существующих вершин.
- При этом, поскольку порядок имеет значение, у нас есть n вариантов для выбора родительской вершины для каждой новой вершины.
4. На каждом шаге добавления новой вершины у нас есть n возможных выборов, и мы повторяем этот процесс n - 1 раз (поскольку одна вершина уже выбрана как корень).
5. Таким образом, общее количество упорядоченных деревьев с n вершинами будет равно n * n * n * ... (n - 1 раз), что можно записать как n^(n-1).
6. Также заметим, что аналогично количеству упорядоченных деревьев можно исследовать последовательности длины n - 2 из натуральных чисел от 1 до n. Мы можем выбрать n - 2 элемента из n доступных, причем каждый элемент может повторяться.
7. Как следствие, количество упорядоченных деревьев с n вершинами равно n^(n-2).
Ответ:
Существует ровно n^(n-2) упорядоченных деревьев с n вершинами.