不好意思再問一題，看不懂題目
Determine the number of ways of placing four nontaking rooks on the unshaded area of the
following chessboard
1: black 0:white
1 1 1 0 0 0 0
0 1 1 0 0 0 0
0 0 0 1 1 0 0
0 0 0 0 1 1 1
棋盤它是給方格，1代表格子塗黑色
thanks!
ans :160
Research Space for Linear Algebra & Discrete Mathematics
6 則留言:
題目的意思是要在白色的棋格上放 4 個不互相攻擊的 rook 有幾種放法, 其中, 如果兩個 rook 同時存在於同一行或同一列, 他們就會互相攻擊, 就像象棋的俥一樣, 要放 4 隻下去使他們不互吃; 這是一個禁位問題, 也就是限制棋子不能放的區域算方法數, 通常會用rook polynomial的方法來解
請問相關定理書上沒有嗎~?
所以這題用我現在所學的排列組合概念和手法沒辦法解決摟~?
也不能說是不能解, 只是討論起來會非常非常的麻煩, 就好像很多組合的問題若我們用生成函數解可以方便很多, rook polynomial的方法就有點像是利用生成函數再搭配排容的想法下去解, 這樣整理過後會使得此類的問題好算很多; 我先算一下這題給你參考, 至於觀念的部分你可以去google一下或者是翻翻其它原文書
令 r(C,x): rook polynomial,
r(C1,x), r(C2,x) 分別表左上及右下角禁區放的方法數,
則 r(C1,x) = 1x^0 + 5x^1 + 4x^2, 其中
1x^0 是表示在此區放 0 個 rook 有 1 種方法
5x^1 是表示在此區放 1 個 rook 有 5 種方法
4x^2 是表示在此區放 2 個 rook 有 4 種方法
同理可以列出 r(C2,x) = 1 + 5x + 5x^2
=> r(C,x) = r(C1,x)r(C2,x)
=(1 + 5x + 4x^2)(1 + 5x + 5x^2)
= 1 + 10x + 34x^2 + 45x^3 + 20x^4
然後再利用 r(C,x) 中的係數, 可列出總方法數為
1*(7*6*5*4) - 10*(6*5*4) + 34*(5*4) - 45*4 + 20
= 160 (一開始的7是行數, 而因為有4列所以往下乘4次)
謝謝，這樣我會算了
所以在禁區中，可以放1~4個方法數
要自己用手指去數對吧~?
所以棋盤是 5*5
下面係數就是: *5! - *4! + *3! ....
這樣嗎~?
1. 對, 用手指去數
2. yes
張貼留言