IMO 1969 LL GDR31

Find the number of permutations a1, . . . , an of the set

imolonglistmathematicsolympiad

IMO 1969 LL GDR31

Origin: GDR

Problem

Find the number of permutations a1, . . . , an of the set {1, 2, . . ., n} such that |ai −ai+1| ̸= 1 for all i = 1, 2, . . ., n −1. Find a recurrence formula and evaluate the number of such permutations for n \leq6.