求{1,2,N}的置换数,使序列先增加后减少?

1. 所有这些排列都有数字 N 中间的某个地方
2. 所有小于 N 可以分为两组:左侧和右侧。左组按递增顺序,右组按递减顺序。
3. 左组和右组不能为空。
4. 所有剩余的数字按降序排列。
5. N N-1 数字。

{1, 2, ..., N-1} 减去两个角案例。那就是 2^(N-1) - 2

算法如下

1. 峰值元素始终为N
2. N不能在两个端点中的任何一端,因此我们可以将其放置在N-2位置
3. 假设N在第i个位置,我们可以选择i-1个数字在左侧。这些元素将以排序的方式放置,其他元素将简单地以相反的顺序放置在N之后
4. 从n=nCi中选择i个元素的方法数量,我们必须从(n-1)个元素中选择(i-1)个元素
5. N可以在i=2到N-1之间的任何索引处(假设索引从1开始)

6. (n-1)C1+(n-1)C2+(n-1)C3+(n-1)C4+。。。。(n-1)Cn-2= 2^(n-1)-2 //-2处理n-1C0和n-1Cn-1的情况