推 brad84622: 原來是問最大的！ 謝謝！ 09/14 19:05
※ 引述《brad84622 (brad84622)》之銘言：
: http://i.imgur.com/fZIj2wF.jpg
: 主要是b選項
: http://i.imgur.com/iDtJKET.jpg
: 不太明白為何對角線一定是1
antisymmetric relation的定義
If R(a,b) and R(b,a), then a = b
或者
If R(a.b) with a =/= b, them R(b,a) must not hold.
所以對角線項不受限制，既然問題問|R|最大的情況
就給所有的對角線項1
接下來是非對角線項
設i =/= j
如M_ij = 1 => M_ji = 0
所以M_ij和M_ji綁在一起
只要其中有一個1
另外一個一定得是0
所以求|R|最大的情況時
就是在M_ij, M_ji這一個非對角項組裡面
挑一個為1 另一個為0
總共有2種選擇
而非對角項組總共有(n-1) + (n-2) + ... + 1 = n(n-1)/2
所以|R|最大的情況下是
1.對角項全1
2.每個非對角項組都是一個1，另一個為0的情況
因此就有1 * 2 * 2 * 2 ... * 2 = 2自乘n(n-1)/2 種組合
最後結果就是2^[n(n-1)/2]種關係矩陣滿足|R|最大的情況
: 而且反對稱部分算在一起
: 跟前面的算法不太一樣
: http://i.imgur.com/C7BRzjZ.jpg
: http://i.imgur.com/hhTmVI0.jpg
: 是我對題目的理解有錯嗎？
: -----
: Sent from JPTT on my Samsung SM-N9208.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.56.9.110
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1473830733.A.B4D.html