szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 20 kwi 2019, o 10:34 
Użytkownik
Avatar użytkownika

Posty: 22
Lokalizacja: Bytom
Drzewo S_{0} składa się z pojedynczego wierzchołka. Drzewo S_{i}, gdzie i > 0 tworzone jest za pomocą dwóch drzew S_{i-1}, przez zaczepienie korzenia jednego z tych drzew jako syna korzenia drugiego drzewa.

a) Wierzchołkami na poziomie i są wszystkie wierzchołki odległe o i krawędzi od korzenia.
Drzewo S_{k} ma wierzchołki na poziomach 0, 1 ..., k (ma zatem k + 1 poziomów). Ile wierzchołków na poziomie 0, 1, 2, 3 ma drzewo S_{3}?

b) Spróbuj odgadnąć wzór na liczbę wierzchołków drzewa S_{k} na poziomie i.

O ile w podpunkcie a), po wyrysowaniu drzewa, nie mam problemu bo to będzie:
dla i = 0, 1 wierzchołek
dla i = 1, 3 wierzchołki
dla i = 2, 3 wierzchołki
dla i = 3, 1 wierzchołek

O tyle nie mam pojęcia jak ugryźć podpunkt b).
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2019, o 22:39 
Użytkownik

Posty: 364
Lokalizacja: Warszawa
Niech p_{n,k} będzie liczbą wierzchołków, które na poziomie k ma n-te drzewo. Wtedy z konstrukcji tych drzew zachodzi równość

p_{n+1,k}=p_{n,k}+p_{n,k-1}

Zauważmy, że jeszcze zachodzi p_{n,0} = 1 dla każdego n. Tyle w kwestii \{p_{n,k}\}_{n,k\in \mathbb{N}}. A teraz coś z (nie)zupełnie innej beczki. Mamy

{n+1 \choose k} =  {n \choose k} + {n \choose k-1}

oraz {n \choose 0} = 1.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podać liczbę rozwiązań równania  Zephi  3
 Z cyfr 1...7 układamy liczbę, w której...  ghostko  6
 Wzór Newtona - zadanie 4  bazilazi  1
 Wzór jawny na sume  timus221  2
 Na ile sposobów można ułożyć liczbę podzielną przez 4?  teclado  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl