Навчання / Бібліотека / Комбінаторика

Кількість позначених дерев

КомбінаторикаСереднє

Скільки різних дерев можна намалювати на позначених вершинах від $1$ до $7$ ? Дерева різні, якщо різняться їхні множини ребер.

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Дерево на позначених вершинах відповідає коду, який отримують, раз за разом видаляючи найменший листок.

Розв’язок

Дерево на $n$ позначених вершинах взаємно однозначно відповідає послідовності довжини $n - 2$ із елементами з $1, \dots, n$ , а саме мітками сусідів видалених найменших листків.
Тут $n = 7$ , тож послідовності мають довжину $5$ , і кожен елемент має $7$ варіантів.
Кількість дерев дорівнює $7^{5} = 16807$ .

Відповідь: $16807$