Witam.
Mam takie oto zadanie:
Niech \(\displaystyle{ n \in N}\). Wyznaczy¢ liczbę drzew T o zbiorze wierzchołków [n]
takich, że \(\displaystyle{ \Delta(T) \le 2}\)
Właściwie chciałem tylko zapytać, czy wpadłem na dobre rozwiązanie.
1. Jeżeli n = 1
To mamy wierzchołek izolowany bez krawędzi, więc takich drzew mamy 1
2. Jeżeli n = 2
Mamy dwa wierzchołki i krawędź między nimi. Takie drzewo jest 1
3. Jeżeli \(\displaystyle{ n \ge 3}\) to kod Prufera ma n-2 "miejsc" dla wierzchołków.
Ponieważ \(\displaystyle{ \Delta(T) \le 2}\) to każdy wierzchołek może pojawić się w kodzie Prufera dokładnie jeden raz albo w ogóle nie wystąpić.
Wybieramy interesujące nas wierzchołki na \(\displaystyle{ {n \choose n-2}}\) sposobów
Następnie ustawiamy je w kodzie Prufera na (n-2)! sposobów
Dostajemy z tego \(\displaystyle{ \frac{n!}{2}}\)
Czy jest to dobre rozwiązanie?
Pozdrawiam,
Fray