[概率统计] 排列方法

mathworld

求
把从1到n的n个整数排成一列,使得除了左边第一个数以外,每一个数均与他左方（不必相邻）的某一个数相差1的排列方法

如果我们让k作为第一个数
第二个数可以是k+1，或k-1，第三个数就比较麻烦了，如果第二个是k+1，那可以选k+2和k-1，如果是k-1，则可以选k+1和k-2
那么接下来的数分为两组：
k+1,k+2,...,n
k-1,k-2,...,1
于是这两组数可以交替排列在后面，但每一组都必须按照自己的顺序来排，比如k+2必然排在k+1的后面，但k+2和k-1却无所谓谁先谁后
这样在后面的n-1个位置中，要拿出k-1个来给第二组，剩下的给第一组，就有C(k-1,n-1)种
由于每个数都可以排在第一位，总排列数就是要全部加起来
即C(0,n-1)+C(1,n-1)+...+C(n-1,n-1)=2^(n-1)种



本帖最后由 yddy11 于 2013-6-19 23:50 编辑


我用“递推思想”得到的递推关系式为：
f(n+1)=f(n)+f(n-1)+f(n-2)+。。。+f(2)+f(1)+1，其中，f(1)=1,f(2)=2,f(3)=4,f(4)=8都是可以验证的，从而递推计算出f(5)=16，f(6)=32，。。。，可以用第二数学归纳法证明：f(n)=2^(n-1).