We want to arrange the integers 1,2,...,n (in a row) such that successive integers cannot be in adjacent positions. In how many ways can we do this for a general n?
Okay, let a_n denote the number of such arrangements. Then we have
a_2 = a_3 = a_4 = 0, a_5 = 2 (13524,14253). The only useful thing i could notice is that in forming the 5-integers arrangement, we can fix 1 and then add 3524 to 1 forwards and backwards. I think we can use this trick in any integer arrangement greater than 5. But how can we calculate the number of arrangements for larger numbers?