Re: [問題] 填色問題

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者terrorlone (終於擺脫憂鬱)時間16年前 (2009/12/22 06:08)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串2/3 (看更多)

※ 引述《raincole (冷雨)》之銘言： : 有一張6*4的方格紙，將其中12格塗黑，使每列皆有2格、每行皆有3格為黑。 : 問有多少種上色方法？ : 原方格紙： : □□□□ : □□□□ : □□□□ : □□□□ : □□□□ : □□□□ : 其中一種上色方法： : ■■□□ : □■■□ : □□■■ : ■■□□ : ■□□■ : □□■■ : 這題有沒有什麼方法可以計算？爬了一下文，不知為何剛好爬到這題。這題用生成函數來算非常簡單，分別用 a,b,c,d 四個變數記錄四行的黑格分佈，則在「每列皆有兩格」的前提之下，生成函數就是 (ab+ac+ad+bc+bd+cd)^6 而若要求每行皆有三格，那麼上面生成函數當中「a^3 b^3 c^3 d^3」的這個項之係數就會是答案了。用電腦來算的話是秒殺，不過可能會有人想問要怎樣用手算，底下解釋。跟一般的符號一樣用 [x^n] 表示係數擷取運算，則 [a^3 b^3 c^3 d^3] (ab+ac+ad+bc+bd+cd)^6 = C(6,3) [b^3 c^3 d^3] (b+c+d)^3 (bc+bd+cd)^3 （我們必須從其中三個括號取得 a） = C(6,3) [c^3 d^3] ( (cd)^3 + 3*(c+d)*3*(c+d)(cd)^2 + 3*(c+d)^2*3*(c+d)^2*cd + (c+d)^3*(c+d)^3 ) （考慮三個 b 是怎麼從那兩組括號取得的） = C(6,3) ( 1 + 9*2 + 9*6 + C(6,3) ) （前一式當中的四項有多少種方法可以取得 c^3 d^3 用看的就知道了） = 1860 （不用解釋了吧……算就是了）這題的正確答案為 1860，完全可以用手算而且一點也不牽涉到複雜的展開。如果要求每行想要的格子數未必相同、例如依序為 A,B,C,D 那麼多格（當然它們必須滿足 A+B+C+D=2*6 這個關係式，否則根本不可能），那麼也就是只要取出「a^A b^B c^C d^D」這個項的係數就會是答案了。甚至如果每行每列想要的格子數都要特別指定，那一樣可以用這邊的方法算，例如考慮 4*4 的格子，想要每列依序有 1,2,2,3 格，且每行也是依序 1,2,2,3 格，那麼答案就會是 [a b^2 c^2 d^3] (a+b+c+d) (ab+ac+ad+bc+bd+cd)^2 (abc+acd+bcd+abd) = [b^2 c^2 d^3] (bc+bd+cd)^2(bcd) + 2*(b+c+d)^2(bc+bd+cd)(bcd) + (b+c+d)(bc+bd+cd)^3 = 2 + 2 [bc] ( bc + 2*(b+c)^2 ) + [b^2 c^2] ( (b+c)^4 + 3*(b+c)^2(bc) ) = 2 + 2*(1 + 4) + 6 + 6 = 24 生成函數的其他應用，有興趣的人可以再進一步思考摸索。 -- 錢，真的是萬能的。 ——如果你不這麼覺得的話，那只是因為你的錢還不夠多而已。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 98.253.57.175 ※ 編輯: terrorlone 來自: 98.253.57.175 (12/22 07:13)