Znajdz liczbę drzew

Znajdz ilość drzew ze zbiorem wierzchołków i maksymalnym stopniu wierzchołka:

a)
b)

Wydawało mi się że w pierwszym to będzie ale w odpowiedziach jest

Skoro pewien wierzchołek ma stopień , to znaczy, że odchodzą od niego krawędzie do wszystkich pozostałych wierzchołków. W takim razie jak już narysujemy ten wierzchołek i połączymy go z resztą, to mamy całe drzewo. Nic więcej już nie możemy zrobić. Zatem takich drzew jest , bo wystarczy zdecydować, który wierzchołek będzie tym wyróżnionym.

b) Tutaj jeden wierzchołek będzie miał sąsiadów i dokładnie jeden z jego sąsiadów będzie miał jeszcze jednego sąsiada innego od tych . To będzie taka gwiazda z ogonkiem. Najpierw wybieramy wierzchołek największego stopnia na sposobów, potem tych dwóch tworzących ogonek i permutujemy ich razy , czyli , a na koniec wybieramy kolejnych sąsiadów tych tworzących ogonek idąc np. zgodnie ze wskazówkami zegara na sposobów, ale musimy to podzielić przez bo nie ma znaczenia czy idziemy zgodnie, czy przeciwnie do wskazówek zegara. Łącznie .

Dlaczego mnożysz wyrażenie przez 2? Wtedy zliczamy chyba podwójnie każdy układ. Wybierasz wierzchołek o najwyższym stopniu na sposobów, potem połączony z nim jedyny wierzchołek niebędący liściem na sposobów i ostatni z tej trójki na sposobów. Czyli w tym przypadku dostajemy np. takie układy i , a mnożac przez dwa niepotrzebnie permutujemy. I mam pytanie jeszcze co do tych pozostałych wierzchołków - czy jako to samo ustawienie uznajemy układ wtedy, kiedy każdy z liści bezpośrednio dołączonych do wierzchołka o najwyższym stopniu ma tych samych sąsiadów? Jeśli tak, to nie powinno być tych permutacji tyle, co ustawień wokół okrągłego stołu, czyli ?

Tak, nie powinienem mnożyć przez 2.

Teraz mam wrażenie, że skoro w a) nie liczyła się kolejność liści, to i w b) kolejność liści może nie mieć znaczenia, czyli być może nie trzeba tego mnożyć wcale. Czyli że wynik to .
Wygląda na to, że tak jest, bo przy zliczaniu drzew za pomocą tw. Cayley'a właśnie tyle wychodzi - kolejność liści nie ma znaczenia.

A co by to miało znaczyć, że "kolejność liści ma znaczenie"? Formalnie zliczamy pary zbiorów postaci . Pary te są różne, jeśli różnią się zbiorem krawędzi. A zbiór krawędzi "widzi" tylko, który numer z którym jest połączony. Nie ma więc miejsca na kolejność liści. Jak już ustalimy, że nasze drzewo oprócz wierzchołka stopnia musi się składać z liści i jednego wierzchołka stopnia , to po prostu musimy zdecydować, kto będzie miał stopień , kto i kto będzie liściem połączonym z wierzchołkiem stopnia . Reszta jest zadana. Dlatego odpowiedź to .