偶谷排

偶谷排是组合数学中的问题之一。考虑一个有n个元素的排列，从左往右第一个低谷（就是比左右两边的数都小）出现在偶数位置。 n个元素的偶谷排记为Kn。

注意：第一个元素和最后一个元素只需和后面的或者前面的元素相比。

枚举
对于情况较少的排列，可以使用枚举法。
当n=1时，全排列只有一种，不是偶谷排，K1 = 0。
当n=2时，全排列有两种，即1、2和2、1，后者是错排，K2 = 1。
当n=3时，全排列有六种，即1、2、3；1、3、2；2、1、3；2、3、1；3、1、2；3、2、1，其中只有有3、1、2和2、1、3是偶谷排，K3=2。用同样的方法可以知道K4=9。
最小的几个偶谷排是：k1 = 0，K2 = 1，K3=2，K4 = 9，D5 = 44，K6 = 265，K7 = 1854.

定理
偶谷排个数Kn等于错排Dn的个数。

证明，我们来建立一个双射。考虑一个错排 （9,7,4,3,8,2,6,5,1）。

(1,9)(2,7,6)(3,4)(5,8)   考虑它的置换群
(5,8)(3,4)(2,7,6)(1,9)   按最小元降序排  
(8,5)(4,3)(6,2,7,)(9,1)  把最小元放到第二个位置 
(8,5,4,3,6,2,7,9,1)      把括号去掉，得到一个偶谷排，第一个谷底是3，在偶数位置。

反之一样，这样就建立了一个双射，所以偶谷排个数Kn等于错排Dn的个数。

参考资料