偶谷排

偶谷排是組合數學中的問題之一。考慮一個有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的個數。