permutatie

Opgave - CanMO 1996 vraag 3

We noteren een willekeurige permutatie van de natuurlijke getallen $1,2,...,n$ door $a_1,a_2,...,a_n$. Zij $f(n)$ het aantal dergelijke permutaties zodat
(i) $a_1=1;$
(ii) $|a_i-a_{i+1}|\leq2,\ i=1,2,...,n-1$.
Bepaal of $f(1996)$ al dan niet deelbaar is door 3.