a1,a2,...,an是1,2,...,n中的一个排列,且（ai-a(i-1))的绝对值忘记一个条件已知a1=1

Question

a1,a2,...,an是1,2,...,n中的一个排列,且（ai-a(i-1))的绝对值
忘记一个条件 已知a1=1

Answer 1

f(n) = g(n)+h(n)+l(n), 其中
g(n)：所有an 不=n 的排列数.任何一个这种排列, n 两边必然是 n-1, n-2.
h(n)：所有an = n, a(n-1) = n-1 的排列数.
l(n)：所有an = n, a(n-1) = n-2 的排列数.任何一个这种排列, a(n-2) = n-1. 因为 n-1 不可能排在别的地方.（如果没有a1=1的条件, 倒可以 a1 = n-2.)
有如下递推关系：
g(n+1) = g(n)+h(n), n>=3;
h(n+1) = h(n)+l(n), n>=3;
l(n+1)=h(n-1), n>= 4; （注：如果没有a1=1的条件,l(n+1)=h(n-1) + 2)
g(3) = 1, g(4) = 2
h(3)= 1, h(4)= 1, h(5) = 2.
l(3) = 0, l(4) = 1,
于是 从中可得 h(n+1)=h(n)+h(n-2), n >= 4,
只考虑除以3的余数, 我们有：
h（n) 的值依次为： （ 从h(3)开始）
1,1,2,0,1,0,0,1,1,1,2,0,1,0,0,1,1 ,.
所以h(n)除以3的余数 是重复 “1,1,2,0,1,0,0,1”的周期为8的序列.
于是 l(n) 也是周期为8的序列：（ 从l(3)开始）
0, 1, 1,1,2,0,1,0,
而作为除以3的余数,
g(n+8) = h(n+7) + g(n+7)
= h(n+7) + h(n+6) + g(n+6)
= ...
= h(n+7) + h(n+6) + ...+ h(n) + g(n)
= 6 + g(n) = g(n)
所以 8 是 f(n) 除以3的余数的周期.
所以 f(2011) = f(8 * 251 + 3) = f(3)= 2 (mod3)