求 {1,2,…,N} 使得序列先增后减的排列数？
Find the number of permutations of {1,2,…, N} such that the sequence first increases and then decreases?
例如，对于 N = 3。
排列是：
[1,3,2]
[2,3,1]
注意：[1,2,3] 和 [3,2,1] 在这里无效，因为 [1,2,3] 增加但不减少，反之亦然 [3,2,1]。
我在 TCS CodeVita 2017 中遇到了这个问题，他们甚至没有为此提供社论。
- 所有这些排列在中间某处有数字
N
- 所有小于
N的数字都可以分成两组：左组和右组。左组为升序，右组为降序
- 左右组不能为空
- 答案将等于不同左侧组的数量，因为该组后应紧跟
N，所有剩余数字按降序排列。
- 左边组可以包含除
N之外的所有数字。它既不能为空，也不能包含所有 N-1 个数字。
因此，答案是数字子集的数量 {1, 2, ..., N-1} 减去两个极端情况。即2^(N-1) - 2.
算法如下
- 峰值元素总是 N
- N不能在2个端的任何一个，所以我们可以把它放在N-2个位置
- 假设N在第i个位置，我们可以select第i-1个数字在左边。这些将以排序的方式放置，其他元素将简单地以相反的顺序放置在 N
之后
- 从 n = nCi 到 select i 个元素的方法数，我们必须从 (n-1) 个元素 select (i-1) 个元素
- N 可以是从 i = 2 到 N-1 的任何索引（假设索引从 1 开始）
答案是
(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
例如，对于 N = 3。 排列是：
[1,3,2]
[2,3,1]
注意：[1,2,3] 和 [3,2,1] 在这里无效，因为 [1,2,3] 增加但不减少，反之亦然 [3,2,1]。
我在 TCS CodeVita 2017 中遇到了这个问题，他们甚至没有为此提供社论。
- 所有这些排列在中间某处有数字
N - 所有小于
N的数字都可以分成两组：左组和右组。左组为升序，右组为降序 - 左右组不能为空
- 答案将等于不同左侧组的数量，因为该组后应紧跟
N，所有剩余数字按降序排列。 - 左边组可以包含除
N之外的所有数字。它既不能为空，也不能包含所有N-1个数字。
因此，答案是数字子集的数量 {1, 2, ..., N-1} 减去两个极端情况。即2^(N-1) - 2.
算法如下
- 峰值元素总是 N
- N不能在2个端的任何一个，所以我们可以把它放在N-2个位置
- 假设N在第i个位置，我们可以select第i-1个数字在左边。这些将以排序的方式放置，其他元素将简单地以相反的顺序放置在 N 之后
- 从 n = nCi 到 select i 个元素的方法数，我们必须从 (n-1) 个元素 select (i-1) 个元素
- N 可以是从 i = 2 到 N-1 的任何索引（假设索引从 1 开始）
答案是
(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
的情况