找出{1,2,...,N}的排列数,使序列首先增加然后减少？

Question

例如,对于N = 3. 排列是:

[1,3,2]
[2,3,1]

注意:[1,2,3]并且[3,2,1]在此处无效,因为[1,2,3]增加但不减少,反之亦然[3,2,1].

我在TCS CodeVita 2017中遇到了这个问题,他们甚至没有为此提供社论.

Answer 1

1. 所有这些排列都N在中间的某个位置
2. 所有小于的数字N可分为两组:左和右.左侧组按升序排列,右侧组按递减顺序排列.
3. 左侧和右侧组不能为空.
4. 答案将等于不同左组的数量,因为该组应立即跟随N,所有剩余的数字按降序排列.
5. 左侧组可以包含除此之外的所有数字N.它既不能为空,也不能包含所有N-1数字.

因此,答案是数字子集的数量{1, 2, ..., N-1}减去两个角落情况.那是2^(N-1) - 2.