填色問題 - 拼圖

※ 引述《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


生成函數的其他應用，有興趣的人可以再進一步思考摸索。

--
錢，真的是萬能的。

——如果你不這麼覺得的話，那只是因為你的錢還不夠多而已。

--