Re: 請問大大一題塗色問題
※ 引述《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://www.ptt.cc/bbs/Math/M.1716141007.A.63F.html
推
05/21 01:32,
3周前
, 1F
05/21 01:32, 1F
→
05/23 00:40,
3周前
, 2F
05/23 00:40, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 3 之 3 篇):