作者cuteSquirrel (可愛的小松鼠)
看板Math
標題Re: 請問大大一題塗色問題
時間Mon May 20 01:50:05 2024
※ 引述《rfvbgtsport (uygh)》之銘言：
: 5色去塗2*3方格，規定相鄰異色，且每色至少用一次，方法數？答案是760
: 請教大大們，多了一個每色至少用一次，要如何算，比較好，謝謝大大們
五種顏色要填充2*3的方格子
顏色當主角的想法:
五色挑一色重複 C(5,1)
假設重複的顏色叫做A顏色
A A B C D E 排列有 6! / 2! 種
非法情況(同色相鄰)有 七大類，_ 代表剩下的用盡四色塗法 4!
總共有
A _ _ 或 _ A _ 或 _ _ A 或 A A _ 或 _ A A 或 _ _ _ 或 _ _ _
A _ _ _ A _ _ _ A _ _ _ _ _ _ A A _ _ A A
相鄰異色塗法
= 五色用盡的任意塗法 - 相鄰有同色的情況
= C(5,1) * { 6! / 2! - 7 * 4!}
= 5 * { 360 - 7 * 24 }
= 5 * { 360 - 168 }
= 5 * 192
= 960 種
========================================================================
格子當主角的想法
甲 乙 丙
丁 戊 己
六個格子，用五種顏色來塗，相鄰必須異色，而且顏色必須用盡。
最多鄰居的乙先塗
甲丙戊 同色 禁止，因為這樣沒辦法用盡五色。
甲丙同色 戊異色 => 5 (塗乙) * 4 (塗甲丙) * 3 (塗戊) * 2 (塗丁) * 1 (塗已)
甲戊同色 丙異色 => 5 乙 * 4 甲戊 * 3 丙 * 2 丁 * 1 己
丙戊同色 甲異色 => 5 乙 * 4 丙戊 * 3 甲 * 2 丁 * 1 己
= 5! * 3 = 120 * 3 = 360種
甲丙戊異色 5 * 4 * 3 * 2 * { 丁乙同 1 * 1 + 丁丙同 1 * 1 + 丁用了最後一色 1*3 }
乙 甲 丙 戊 己用最後一色 己用最後一色 己和丙戊異色就好
= 120 * { 1 + 1 + 3 } = 120 * 5
= 600種
所有合法情況加總 = 360種 + 600種 = 960種
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.172.207 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1716141007.A.63F.html
1F：推 rfvbgtsport : 謝謝大大 05/21 01:32
2F：→ cuteSquirrel: : ) 05/23 00:40