Re: [理工] [離散]100年成大
使用rook polynomial(城堡多項式)
在某一格放下一子時，其同一行與同一列不能再放其他子
＊代表不能放置的位子
L A P1 T O P2
L ＊
A ＊
P1 ＊ ＊
T ＊
O ＊
P2 ＊ ＊
整理成
L A T O P1 P2
L ＊
A ＊
T ＊
O ＊
P1 ＊ ＊
P2 ＊ ＊
左上四個＊和右下方的一塊互相不影響
所以在＊上放子的方法數=(1+x)^4 * (1+4x+2x^2)
=1+8x+24x^2+36x^3+29x^4+12x^5+2x^6
其中x^i的係數代表在＊上放i子的方法數
再使用排容原理
允許的字串=全部的字串 - 至少1bit不對的字串 + 至少2bit不對的字串.....
1*6!-8*5!+24*4!-36*3!+29*2!-12*1!+2*0!=168
然後P1=P2，所以最後答案要除以2，=84
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.67.230
※ 編輯: cooper6334 來自: 111.252.67.230 (02/21 01:05)
推
02/22 22:57, , 1F
02/22 22:57, 1F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 5 篇)：
理工
8
35