Find the number of permutations of the set such that for all Find a recurrence formula and evaluate the number of such permutations for
%V0
$(GDR 3)$ Find the number of permutations $a_1, \cdots, a_n$ of the set $\{1, 2, . . ., n\}$ such that $|a_i - a_{i+1}| \neq 1$ for all $i = 1, 2, . . ., n - 1.$ Find a recurrence formula and evaluate the number of such permutations for $n \le 6.$
Izvor: Međunarodna matematička olimpijada, shortlist 1969
Školjka 
Find the number of permutations 
of the set 
such that 
for all 
Find a recurrence formula and evaluate the number of such permutations for 