Условие:
Сколько имеется попарно неизоморфных деревьев с 6 вершинами, из которых четыре висячие.
Решение:
Рассмотрим задачу: найти количество попарно неизоморфных деревьев с 6 вершинами, у которых ровно 4 вершины являются висячими (то есть имеют степень 1).
Шаг 1. Определим суммарную степень вершин.
В дереве с n вершинами сумма степеней равна 2(n – 1). Для n = 6:
∑deg = 2·(6 – 1) = 10.
Шаг 2. Учтём, что ровно 4 вершины — висячие, то есть их степени равны 1.
Общая сумма степеней этих 4 вершин: 4 · 1 = 4.
Остальные две вершины (называем их внутренними) будут иметь степени d1 и d2, и должны удовлетворять:
d1 + d2 + 4 = 10 → d1 + d2 = 6.
При этом каждая из этих вершин должна иметь ст...