2009-12-08

[離散] 排列組合2

不好意思再問一題，看不懂題目


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
於

6 則留言:

  1. 線代離散助教(wynne)2009年12月9日 凌晨12:36

    題目的意思是要在白色的棋格上放 4 個不互相攻擊的 rook 有幾種放法, 其中, 如果兩個 rook 同時存在於同一行或同一列, 他們就會互相攻擊, 就像象棋的俥一樣, 要放 4 隻下去使他們不互吃; 這是一個禁位問題, 也就是限制棋子不能放的區域算方法數, 通常會用rook polynomial的方法來解

    回覆刪除
  2. Chesley2009年12月10日 上午11:00

    請問相關定理書上沒有嗎~?

    所以這題用我現在所學的排列組合概念和手法沒辦法解決摟~?

    回覆刪除
  3. 線代離散助教(wynne)2009年12月10日 晚上11:04

    也不能說是不能解, 只是討論起來會非常非常的麻煩, 就好像很多組合的問題若我們用生成函數解可以方便很多, 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次)

    回覆刪除
  4. Chesley2009年12月11日 下午2:18

    謝謝，這樣我會算了


    所以在禁區中，可以放1~4個方法數
    要自己用手指去數對吧~?

    回覆刪除
  5. Chesley2009年12月11日 下午2:24

    所以棋盤是 5*5

    下面係數就是: *5! - *4! + *3! ....

    這樣嗎~?

    回覆刪除
  6. 線代離散助教(wynne)2009年12月11日 晚上9:10

    1. 對, 用手指去數
    2. yes

    回覆刪除