Drzewa - matematyka dyskretna Martyna: Dzień dobry, przychodzę z takim zadaniem: W drzewie o 100 wierzchołkach każdy wierzchołek ma stopień 1 lub 3. Ile liści ma takie drzewo? Podejrzewam, że będzie tu trzeba w jakiś sposób użyć liczb Catalana, tylko kompletnie nie wiem jak się za to zabrać

wredulus_pospolitus: należy zauważyć, że każdy wierzchołek stopnia 1 jest liściem, reszta musi być stopnia 3. rozpatrując pełne drzewo będziemy mieli następujące ilości wierzchołków (na kolejnych poziomach) 1 3 3*2 = 6 6*2 = 12 12*2 = 24 24*2 = 48 daje nam to w sumie 96 wierzchołków, czyli tylko 2 (z ostatniego poziomu) nie będą liśćmi. zatem liści mamy: 46 + 2*2 = 52

kerajs: Dlaczego korzeń nie może być stopnia 1?

Martyna: Stopień oznacza ilość "linii" wchodzących i wychodzących z danego wierzchołka, prawda?

kerajs: Prawda, lecz nie linii, a krawędzi. https://pl.wikipedia.org/wiki/Stopie%C5%84_wierzcho%C5%82ka Moim zdaniem są dwie możliwości: Jeśli korzeń jest stopnia 1 to drzewo ma 50 liści Jeśli korzeń jest stopnia 3 to drzewo ma 51 liści