Ile drzew $e$ krawędzie w oznaczonej klice
Mając oznaczoną klikę $G=(E,V)$, Chciałbym wymienić liczbę drzew, które można wykonać dla danej liczby krawędzi $e$, tak, że wszystkie węzły w drzewie są połączone.
Na przykład niech $G$być wykresem 4-klikowym. Chciałbym znaleźć liczbę drzew z 3 krawędziami, które można utworzyć jako podgrafy.
Próbowałem to zbadać, ale tak naprawdę nie mogłem uporać się z literaturą. Ten post MSE wygląda bardzo podobnie do mojego pytania, ale mam problem z odpowiedzią.
Oto moja próba rozwiązania tego problemu. Najpierw obliczamy całkowitą liczbę sposobów wyboru 3 krawędzi z 4-kliki. W sumie jest 6 krawędzi. Tam są$6\cdot 5 \cdot 4 = 120 $różne sposoby dokonywania wyborów; jednak wiele z nich jest sobie równoważnych. W rzeczywistości, biorąc pod uwagę trzy możliwości wyboru krawędzi,$\{e_1,e_2,e_3\}$, kolejność, w jakiej są wybierane, nie ma znaczenia. Więc musimy podzielić 120 przez liczbę permutacji 3-literowego słowa, czyli 6. Stąd liczba wykresów, które można wykonać z wyboru dowolnych 3 krawędzi z 4-kliki wynosi$120/6= 20$ który jest również współczynnikiem dwumianowym
$$ \binom{6}{3} $$
Oczywiście liczba drzew musi być mniejsza od tej liczby. Moim naiwnym podejściem jest myślenie, że drzewo o rozmiarze 3 będzie zawsze zawierało 4 węzły. Badania wykazały, że takich drzew jest 16 w przypadku 4 kliku przez zatrudnienie$$ n^{n-2}=4^2=16 $$Jednak ta metoda jest ważna tylko w tym przypadku. W przypadku większych klik, jak mogę znaleźć liczbę drzew za pomocą$e$ krawędzie, gdzie $e\neq n-1$?
Szczególny przypadek $e=3$ jest moim głównym celem dla arbitralności $n$.
Odpowiedzi
Drzewo z $e$ krawędzie ma $e+1$węzły. Biorąc pod uwagę zestaw$n$ węzły, są $\binom n{e+1}$ sposoby wyboru zbioru węzłów dla drzewa, a następnie według wzoru Cayleya są $(e+1)^{e-1}$ drzewa na tym zbiorze węzłów, więc ostateczna odpowiedź brzmi $$\binom n{e+1}(e+1)^{e-1}.$$