Szczególne drzewa
: 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}\) ?
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...