[Struktury danych] Kopiec dwumianowy - liczba węzłów

janko_informatyk
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 22 maja 2019, o 11:13
Płeć: Mężczyzna
Lokalizacja: Warszawa

[Struktury danych] Kopiec dwumianowy - liczba węzłów

Post autor: janko_informatyk »

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.
Dudenzz
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 8 mar 2009, o 18:21
Płeć: Mężczyzna
Pomógł: 19 razy

Re: [Struktury danych] Kopiec dwumianowy - liczba węzłów

Post autor: Dudenzz »

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{ ...}\)
ODPOWIEDZ