Q31 Matemática  (IMO Longlists 1969)

$(GDR3)$ Encontre o número de permutações $a_1,\cdots ,a_n$ do conjunto $\{1,2,...,n\}$ tal que $|a_i-a_{i+1}|\ne 1$ para todo $i=1,2,...,n-1.$ Encontre uma fórmula de recorrência e calcule o número de tais permutações para $n\le 6.$