kleurrijk halssnoer

We noemen het aantal mogelijkheden voor k kralen f(k).

We bepalen eerst $f(2)$. De eerste kraal heeft 5 mogelijkheden, de tweede 4, en de armband kan langs twee kanten gedragen worden, dus is $f(2)=\frac{5*4}2=10$.

Vervolgens kijken we naar het geval $k=3$. Dan zijn er voor de eerste kraal 5 mogelijkheden, voor de tweede 4 en voor de derde 3. De tweede en de eerste kunnen onmogelijk gelijk zijn, dus moet er geen gevalsonderscheid gemaakt worden. Omdat de ketting langs twee kanten kan gedragen worden, is $f(3)=\frac{5*4*3}2=30.$

Nu bepalen we $f(n)$ voor $n \ge 4$.
Er moet gevalsonderscheid gemaakt worden, want er zijn twee mogelijkheden:
1) kraal 1 heeft niet dezelfde kleur als kraal $n-1.$
2) Kraal 1 heeft wel dezelfde kleur als kraal $n-1.$
Het aantal mogelijkheden waarin geval 1) waar is, is gelijk aan $f(n-1)$: dit omdat hierin de eerste en de $(n-2)^{de}$ kraal niet dezelfde kleur mogen hebben. Dus voor de nde kraal zijn er nu nog 3 mogelijkheden, dus als geval 1) waar is, heb je $3*f(n-1)$ mogelijkheden.
Als geval 2) waar is, heb je voor de $(n-2)^{de}$ kraal slechts 1 mogelijkheid, aangezien deze dezelfde kleur moet hebben als de eerste kraal. In dit geval mag de $(n-2)^{de}$ kraal niet dezelfde kleur hebben als de eerste kraal, omdat dande $(n-2)^{de}$ kraal niet dezelfde kleur kan hebben als de eerste kraal, want dan zou zijn kleur dezelfde zij als die van de kraal voor hem. Dus het aantal mogelijkheden waarin 2) waar is, is gelijk aan $f(n-2)$, omdat daarin de eerste en de $(n-2)^{de}$ kraal niet dezelfde kleur mag hebben. Er zijn in dit geval nog 4 mogelijkheden voor de $n^{de}$ kraal, dus is het totaal aantal mogelijkheden in dit geval gelijk aan $4*f(n-2).$
Voor $f(n)$ tellen we deze twee mogelijkheden op.
Zo komen we aan de recursieformule $f(n)=3*f(n-1)+4*f(n-2)$ voor $n \ge 4$.

Hieruit volgt:
$f(4)=3*f(3)+4*f(2)=90+40=130$
$f(5)=510$
$f(6)=2050$
$f(7)= 8190$