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