ile jest drzew na zbiorze...

[pumbosha]

Mam takie chyba trywialne wręcz zadanko, ale nie bardzo mogę zrozumieć odpowiedzi do niego:

Ile jest drzew na zbiorze wierzchołków {1..n}
a)mających wierzchołek stopnia n-1(odp n)
b)mających wierzchołek stopnia n-2(odp n(n-1)(n-2))
c)mających wierzchołki stopnia 1 i 2 (odp n!/2)

[BettyBoo]

To są właściwie zadania z zakresu kombinatoryki

a) skoro drzewo ma mieć wierzchołek stopnia n-1 to znaczy, że musi z niego wychodzić n-1 krawędzi. A więc jeden wierzchołek jest połączony z każdym innym i innych krawędzi być nie może (bo to drzewo, więc nie ma pętli ani cykli ani nic). Wobec tego takich drzew jest tyle, ile sposobów wyboru tego wierzchołka, czyli n

b)skoro mamy wierzchołek stopnia n-2, to jest on połączony z n-2-ma innymi wierzchołkami. Pozostaje więc jeden wolny wierzchołek, który musi być też z czymś połączony - można go połączyć tylko z jednym z tych n-2 wierzchołków. Pozostaje więc ustalić, ile jest możliwości stworzenia takiego drzewa dla n wierzchołków. Mianowicie, wybieramy dowolny wierzchołek (n możliwości), który ma stopnień n-2. Teraz z pozostałych wierzchołków wybieramy dowolny, który nie będzie z nim połączony (n-1 możliwości) i łączymy go z jednym z pozostałych wierzchołków (n-2 możliwości). Na każdą z n możliwości pierwszego wyboru przypada każda z n-1 możliwości drugiego wyboru oraz każda z n-2 możliwości trzeciego wyboru, a więc w sumie mamy n(n-1)(n-2) możliwości.

c) skoro wierzchołki mają mieć tylko stopień 1 lub 2, to nasze drzewo jest w rzeczywistości gołym, bezlistnym badylkiem a więc możliwości skonstruowania takiego drzewa jest tyle, ile wynosi połowa ilości permutacji zbioru n-elementowego (połowa dlatego, że drzewo z obu "końców" wygląda tak samo), a więc n!/2

Pozdrawiam.