Cześć,
Potrzebuję udowodnić, że drzewo dwumianowe danego rzędu \(\displaystyle{ (n)}\) ma \(\displaystyle{ 2^{n}}\) węzłów oraz że na danym poziomie (\(\displaystyle{ k}\)) drzewa dwumianowego danego rzędu (\(\displaystyle{ n}\)) znajduje się dokładnie \(\displaystyle{ {n \choose k}}\) węzłów. O ile wiem co to jest to drzewo dwumianowe, o tyle nie jestem w stanie tego udowodnić w jakiś banalny sposób.
Z góry dzięki za naprowadzenie.
[Struktury danych] Kopiec dwumianowy - liczba węzłów
-
- Użytkownik
- Posty: 1
- Rejestracja: 22 maja 2019, o 11:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
Re: [Struktury danych] Kopiec dwumianowy - liczba węzłów
1. Za każdym razem kiedy "dodajesz" nową warstwę do drzewa, "dodajesz" jeden wierzchołek do każdego istniejącego wierzchołka w drzewie. W związku z tym
\(\displaystyle{ S(B_{K+1}) = 2 \cdot S(B_K)}\)
Drzewo o wysokości 0 ma jeden element,
\(\displaystyle{ S(B_{0}) = 1}\)
więc
\(\displaystyle{ ...}\)
2. W każdym kroku rekurencji liczba wierzchołków na poziomie \(\displaystyle{ k}\) jest powiększona o liczbę wierzchołków na poziomie \(\displaystyle{ k-1}\) w poprzednim kroku rekurencji.
Skoro (celowo pokazuje dość sporo kroków rekurencji)
\(\displaystyle{ R(0,B_{0}) = 1}\)
to
\(\displaystyle{ R(0,B_{1}) = 1+0 = 1}\)
\(\displaystyle{ R(1,B_{1}) = 0+1 = 1}\)
\(\displaystyle{ R(0,B_{2}) = 1+0 = 1}\)
\(\displaystyle{ R(1,B_{2}) = 1+1 = 2}\)
\(\displaystyle{ R(2,B_{2}) = 0+1 = 1}\)
\(\displaystyle{ R(0,B_{3}) = 1 + 0 = 1}\)
\(\displaystyle{ R(1,B_{3}) = 2 + 1 = 3}\)
\(\displaystyle{ R(2,B_{3}) = 1 + 2 = 3}\)
\(\displaystyle{ R(3,B_{3}) = 0 + 1 = 1}\)
\(\displaystyle{ R(0,B_{4}) = 1 + 0 = 1}\)
\(\displaystyle{ R(1,B_{4}) = 3 + 1 = 2 + 1 + 1 = 4}\)
\(\displaystyle{ R(2,B_{4}) = 3 + 3 = 3 + 2 + 1 = 6}\)
\(\displaystyle{ R(3,B_{4}) = 1 + 3 = 1 + 1 + 2 = 4}\)
\(\displaystyle{ R(4,B_{4}) = 0 + 1 = 1}\)
czyli
\(\displaystyle{ ...}\)
\(\displaystyle{ S(B_{K+1}) = 2 \cdot S(B_K)}\)
Drzewo o wysokości 0 ma jeden element,
\(\displaystyle{ S(B_{0}) = 1}\)
więc
\(\displaystyle{ ...}\)
2. W każdym kroku rekurencji liczba wierzchołków na poziomie \(\displaystyle{ k}\) jest powiększona o liczbę wierzchołków na poziomie \(\displaystyle{ k-1}\) w poprzednim kroku rekurencji.
Skoro (celowo pokazuje dość sporo kroków rekurencji)
\(\displaystyle{ R(0,B_{0}) = 1}\)
to
\(\displaystyle{ R(0,B_{1}) = 1+0 = 1}\)
\(\displaystyle{ R(1,B_{1}) = 0+1 = 1}\)
\(\displaystyle{ R(0,B_{2}) = 1+0 = 1}\)
\(\displaystyle{ R(1,B_{2}) = 1+1 = 2}\)
\(\displaystyle{ R(2,B_{2}) = 0+1 = 1}\)
\(\displaystyle{ R(0,B_{3}) = 1 + 0 = 1}\)
\(\displaystyle{ R(1,B_{3}) = 2 + 1 = 3}\)
\(\displaystyle{ R(2,B_{3}) = 1 + 2 = 3}\)
\(\displaystyle{ R(3,B_{3}) = 0 + 1 = 1}\)
\(\displaystyle{ R(0,B_{4}) = 1 + 0 = 1}\)
\(\displaystyle{ R(1,B_{4}) = 3 + 1 = 2 + 1 + 1 = 4}\)
\(\displaystyle{ R(2,B_{4}) = 3 + 3 = 3 + 2 + 1 = 6}\)
\(\displaystyle{ R(3,B_{4}) = 1 + 3 = 1 + 1 + 2 = 4}\)
\(\displaystyle{ R(4,B_{4}) = 0 + 1 = 1}\)
czyli
\(\displaystyle{ ...}\)