Задание 1
Ответ в приложении
Задание 2
Тут, очевидно, опечатка, k
n=1:
- k=0 - одно дерево, состоящее из одной вершины.
n=2:
- k=0 => граф не связный => не дерево
- k=1 => одно дерево, состоящее из одного ребра
n>2:
- k=0 => граф не связный => не дерево
- k>0 => Тогда каждому дереву поставим в соответствие код Прюфера. Его длина - n-2. Т.к. вершина 1 имеет степень k, то встречается в нем k-1 раз. Тогда для остальных n-1 вершин остается n-2-(k-1)=n-k-1 мест. Тогда всего таких кодов Прюфера, и, следовательно, деревьев,
Задание 3
Найти количество деревьев с n вершинами, имеющими вершину степени n-2.
Зафиксируем номер этой вершины. Тогда в коде Прюфера она встречается n-3 раз. Тогда для остальных n-1 вершин остается n-2-(n-3)=1 место. Кол-во способов выбора номера вершины степени n-2 из n равно n. Тогда искомое число деревьев равно 