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