Szczególne drzewa

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 6007
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2499 razy
Pomógł: 666 razy

Szczególne drzewa

Post autor: mol_ksiazkowy » 2 maja 2020, o 18:23

Ile jest drzew o \(\displaystyle{ n}\) wierzchołkach, w których dla ustalonego wierzchołka \(\displaystyle{ v}\) jest \(\displaystyle{ deg(v)=k}\) ?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Szczególne drzewa

Post autor: arek1357 » 3 maja 2020, o 02:59

weźmy :

\(\displaystyle{ a(n,k)}\) - ilość drzew rozpiętych na grafie o wierzchołkach \(\displaystyle{ n}\) i stopniu jedynego wierzchołku \(\displaystyle{ k}\)

Zauważmy też, że jeżeli zsumujemy od \(\displaystyle{ k=1}\) do \(\displaystyle{ k= n-1}\) otrzymamy wszystkie możliwe drzewa rozpięte na grafie i \(\displaystyle{ n }\)wierzchołkach czyli:

\(\displaystyle{ n^{n-2}}\) - znany wzór...

znaczy:

\(\displaystyle{ \sum_{k=1}^{n-1} a(n,k)=n^{n-2}}\)


ale:

\(\displaystyle{ n^{n-2}=[(n-1)+1]^{n-2}= \sum_{k=0}^{n-2} {n-2 \choose k}(n-1)^{n-2-k} \cdot 1^k }\)

No jest pięknie, ale nie do końca bo nie pasują nam krańce sumowania bo nie zgadza się z tym, że stopień wierzchołka nie powinien być równy zero bo kicha...

ale nic nie stoi na przeszkodzie by zmienić przedziały sumowania tak, żeby pasowało, a mianowicie:

\(\displaystyle{ k=k+1}\)

\(\displaystyle{ n-2=n-1}\)

Otzrymamy:

\(\displaystyle{ \sum_{k=1}^{n-1} {n-2 \choose k}(n-1)^{n-k-1} =n^{n-2} }\)

widać z tego, że:

\(\displaystyle{ a(n,k)= {n-2 \choose k}(n-1)^{n-k-1}}\)

I jak widac można było to zrobić bez żadnych kombinacji tylko rozebrać wzór, który jest szeroko znany...

ODPOWIEDZ