a1,a2,...,an是1,2,...,n中的一个排列,且(ai-a(i-1))的绝对值

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)