跳至內容

偶谷排

維基百科,自由的百科全書

偶谷排是組合數學中的問題之一。考慮一個有n個元素的排列,從左往右第一個低谷(就是比左右兩邊的數都小)出現在偶數位置。 n個元素的偶谷排記為Kn。

注意:第一個元素和最後一個元素只需和後面的或者前面的元素相比。

枚舉

對於情況較少的排列,可以使用枚舉法[1]

  • 當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的個數。

參考資料

  1. ^ 盧開澄、盧華明. 《组合数学》. 清華大學出版社. ISBN 730213961X (中文(簡體)).