Re: [中學] 91新竹女中教甄

[yclinpa (薇楷的爹)]

※ 引述《reebox17 (瑞巴克)》之銘言：
: 用1,2,3,4,5,6作成的六位數密碼，數字不重複使用，且前兩位沒有1,2
: 中間兩位沒有3,4，末兩位沒有5,6，則可作出幾個密碼？
: 麻煩了，感謝:)

使用「城堡多項式」(rook polynomial):

6x6 的板子上有互不影響的 2x2 灰色方格共 3 組，
每一組的城堡多項式為 1+4x+2x^2.

故整塊板子的城堡多項式為
   (1+4x+2x^2)^3
 = 1 + 12 x + 54 x^2 + 112 x^3 + 108 x^4 + 48 x^5 + 8 x^6.

把這個多項式的係數拿來，配上適當的階乘與正負號，得

  6! - 12 * 5! + 54 * 4! - 112 * 3! + 108 * 2! - 48 * 1! + 8 * 0!
= 80

這就是答案。

城堡多項式是基於排容原理的圖像式演算法，請自行上網搜尋。

--
廢話這麼多，還不就是為了撈 P 幣  :q

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.122.140.53
推 jacky7987   :好酷喔!!
推 a88241050   :我們組合課在教這個,我也覺得很神奇..
推 milkkiller  :老師又出馬了..:)
推 reebox17    :感謝老師:)
推 wu1212121212:不推不行XD
推 wa007123456 :真的是80個... http://nopaste.csie.org/c7820
推 n19860423   :推~