Oppgave 1

De 4 nodene på nederste nivå kan plasseres på 16 mulige plasser. Dermed gir B(16,4) = 1820 at det er 1820 forskjellige trær der B(16,4) er binomialkoeffisienten.

Oppgave 2

Det motsatte er ikke sant. Ta et tre med 4 noder der rotnoden ikke har høyre barn og det venstre barnet har to barn. Det har høyde ⌊log₂(4)⌋ = 2, men de to nederste nivåene er ikke fylt opp med noder. Men et tre med

Oppgave 3

Det er to muligheter på hvert nivå. Dermed 2^{n - 1} forskjellige trær.

Oppgave 4 a)

Treet i Figur 9.1.1 a)
Direkte utregning: (0·1 + 1·2 + 2·4 + 3·8)/15 = (0 + 2 + 8 + 24)/15 = 34/15
Formel: k = ⌊log₂(15 + 1)⌋ = 4, ((15 + 1)4 − 2(2⁴ − 1))/15 = (64 - 30)/15 = 34/15

Treet i Figur 9.1.1 b)
Direkte utregning: (0·1 + 1·2 + 2·4 + 3·8 + 4·4)/19 = (0 + 2 + 8 + 24 + 16)/19 = 50/19
Formel: k = ⌊log₂(19 + 1)⌋ = 4, ((19 + 1)4 − 2(2⁴ − 1))/19 = (80 - 30)/19 = 50/19

Oppgave 4 b)

La treet ha n noder og la k = ⌊log₂(n + 1)⌋. Hvis treet er perfekt, er k lik antall nivåer i treet (1 mer enn høyden). Hvis ikke, er k lik antallet nivåer i det perfekte treet vi får hvis vi ser bort fra den nederste raden og i det tilfellet vil n − 2^k + 1 være antallet på nederste nivå eller rad. For hver rad ganger vi antallet på raden med avstanden til roten. Antallet på de fulle radene er 1, 2, 4, 8 osv. og generelt lik 2ⁱ for i fra 0 til k − 1. Dermed:

gnd(n) = (0·1 + 1·2 + 2·4 + 3·8 + . . . + (k − 1)·2^{(k − 1)} + k·(n − 2^k + 1))/n

Her kan vi bruke Formel G.1.9. Dermed:

gnd(n) = ((k − 2)·2^k + 2 + k·(n − 2^k + 1))/n = ((n + 1) k − 2(2^k − 1)) / n