偶谷排

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

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

枚举

对于情况较少的排列，可以使用枚举法。

• 当n=1时，全排列只有一种，不是偶谷排，K₁ = 0。
• 当n=2时，全排列有两种，即1、2和2、1，后者是错排，K₂ = 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是偶谷排，K₃=2。用同样的方法可以知道K₄=9。
• 最小的几个偶谷排是：k₁ = 0，K₂ = 1，K₃=2，K₄ = 9，D₅ = 44，K₆ = 265，K₇ = 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的个数。