Szczególne drzewa
-
mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Szczególne drzewa
Ile jest drzew o \(\displaystyle{ n}\) wierzchołkach, w których dla ustalonego wierzchołka \(\displaystyle{ v}\) jest \(\displaystyle{ deg(v)=k}\) ?
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Szczególne drzewa
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...
\(\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...