Drzewo binarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aneta909811
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 21 razy

Drzewo binarne

Post autor: aneta909811 » 9 lip 2019, o 09:15

Niech \(\displaystyle{ T_{n}}\) bedzie zbiorem uporządkowanym w typ drzewa binarnego (do kazdego wierzchołka dochodzi jedna krawedz, a wychodzą - poza końcowymi wierzchołka - dwie krawedzie), ktorego wszystkie drogi od korzenia do wierzcholka koncowego maja te samą długość \(\displaystyle{ n}\). Ile wierzchołków ma takie drzewo?
Ostatnio zmieniony 9 lip 2019, o 09:34 przez aneta909811, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Drzewo binarne

Post autor: leg14 » 9 lip 2019, o 09:17

Co to jest suma drogi?

aneta909811
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 21 razy

Drzewo binarne

Post autor: aneta909811 » 9 lip 2019, o 09:34

Przepraszam chodziło o długość drogi

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Drzewo binarne

Post autor: leg14 » 9 lip 2019, o 09:50

Proponuje dowod indukcyjny

aneta909811
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 21 razy

Drzewo binarne

Post autor: aneta909811 » 9 lip 2019, o 10:05

Dobrze, tylko nie wiem właśnie ile to wierzchołków, z dowodem raczej sobie poradzę

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Re: Drzewo binarne

Post autor: leg14 » 9 lip 2019, o 10:14

To na początek rozrysuj sobie przypadki dla \(\displaystyle{ n =1, n=2, n =3}\) - znajdź liczbę wierzchołków i popatrz jak wyglądają takie drzewa

aneta909811
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 21 razy

Re: Drzewo binarne

Post autor: aneta909811 » 9 lip 2019, o 10:31

Czy \(\displaystyle{ w=2^{(n+1)}-1}\)?

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Re: Drzewo binarne

Post autor: leg14 » 9 lip 2019, o 10:37

Tak - teraz czas na odwód indukcyjny

ODPOWIEDZ