作者 freePrester (Prester) 看板 Math
標題 Re: [計算] 高中教甄.矩陣.排列
時間 Sun Aug 23 01:06:14 2009
───────────────────────────────────────
※ 引述《ddtjam (浣妹我愛你 XD)》之銘言：
: 2*n矩陣 [ x1 x2 ................ xn ]
: y1 y2 .................. yn
: 其中 x1~xn,y1~yn 為 1~2n的排列
: 對所有i 滿足 xi<x( i+1 ) , yi< y( i+1 ) , xi< yi
: 此種矩陣多少種
: 答案是 C (2n,n) -C (2n , n+1 )
: 麻煩強者解惑， 感恩
考慮將數字由小到大填入矩陣中時
會有下列兩個條件：
1) 每個數字只能填入 x列 或 y列 當時最左端的空白位置
2) y列 的元素個數在任何時候都不能不能大於 x列
所以填入數字的方法相當於下圖中由 A 走到 B 的方法數：
n ┌┬┬┬┬ ＸＢ
填 n-1├┼┼┼┼ ┼┤
y :
列 4 ├┼┼Ｘ┼ ┼┤
個 3 ├┼Ｘ┼┼ ┼┤
數 2 ├Ｘ┼┼┼ ┼┤
1 Ｘ┼┼┼┼ ┼┤
0 Ａ┴┴┴┴ ┴┘
0 1 2 3 4 … n
填 x 列的個數
其中 X 為不可經過的點。
由圖可知，由 A 到 B 的所有捷徑走法有 C(2n,n)
而經過 X 的方法數可以這樣觀察：
假定有非法路線為：
ＸＢ
┌──Ｘ─┘
│ Ｘ
│Ｘ
Ｘ
Ｘ│
Ａ┘
你可以透過類似下列的對應方法使得路線改成由 C 到 B 如圖：
ＸＢ
┌──Ｘ─┘
│ Ｘ
│Ｘ
┌─Ｘ
ＣＸ│
Ａ┘
對應方法是 由A到B路經中，第一個遇到X點前的路線作鏡射
這很容易證明這樣的對應方法是 1-1
所以由 A 到 B 的非法路線等同於由 C 走到 B 的方法數，即 C(2n,n+1)
綜合上述，可知所有可能的矩陣個數為 C(2n,n) - C(2n,n+1) 。
--
���H�����L���l
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.206.122
※ 編輯: freePrester 來自: 118.169.206.122 (08/23 01:15)
推 bugmens :97政大附中 http://tinyurl.com/kvhgr4 08/23 06:12