Сколько существует различных деревьев из 6 вершин? Напомним, что если графы выглядят по-разному, но полностью совпадают по степеням вершин, такие графы считаются одинаковыми.

Ответ: 5 Пояснение пошагово - Пусть деревья на 6 вершинах имеют степени d1, d2, ..., d6. В дереве сумма степеней равна 2(n−1) = 2·5 = 10, и каждая степень хотя бы 1. - Учитывая условие задачи, две деревья считаются одинаковыми, если их мультимножества степеней совпадают. Значит нас интересуют всевозможные неупорядоченные наборы (мультимножества) из 6 чисел ≥1, сумма которых равна 10. - Обозначим di = степень i-й вершины. Пусть xi = di − 1 ≥ 0. Тогда сумма xi = (sum di) − 6 = 10 − 6 = 4. Учитывая неупорядоченность, нас интересуют разложения числа 4 на неотрицательные части, без учета порядка. - Числа разложения 4 (все разложения без учета порядка): 4; 3+1; 2+2; 2+1+1; 1+1+1+1. Каждое такое разложение задаёт соответствующее множество степеней (помните: di = xi + 1). - Переводим разложения xi обратно в степени di: 1) xi: 4 → di: 5,1,1,1,1,1 → {5,1,1,1,1,1} 2) xi: 3+1 → di: 4,2,1,1,1,1 → {4,2,1,1,1,1} 3) xi: 2+2 → di: 3,3,1,1,1,1 → {3,3,1,1,1,1} 4) xi: 2+1+1 → di: 3,2,2,1,1,1 → {3,2,2,1,1,1} 5) xi: 1+1+1+1 → di: 2,2,2,2,1,1 → {2,2,2,2,1,1} - Эти пять наборов степеней действительно выполнимы как дерево (по теореме о Prüfer-коде любой набор положительных степеней с суммой 10 образует дерево; суммa степеней для дерева на 6 вершинах равна 10). Итого, существует 5 различных деревьев на 6 вершин, если считать деревья одинаковыми, если их степени вершин совпадают как многочлены (мультимножества степеней). Примечание: если считать все неориентированные неназываемые деревья без учёта степени вершин, их было бы 6, потому что существует 6 неизоморфных деревьев на 6 вершинах, и у двух разных из них совпадает многочлен степеней.