推 alexan :題目沒規定相鄰要異色耶 05/31 07:02
※ 引述《alexan (冷藍)》之銘言：
: 摩天輪為一個圓圈6等分，每個區塊塗一種顏色，共有4種顏色可選擇，
: 顏色可重複，共有幾種塗法？
: 這題除了分開討論：
: 6區同色--->4種
: 5同1異---->30種
: 4同2同
: 4同2異.....依此類推
: 請問還有其他方法嗎？
將一圓等分成n等分，用k種顏色來塗n個區域，每一區域塗一色，相鄰區域不同色，
顏色可以重複取用，且不一定k種顏色全用:
設用k種顏色圖n個區域，相鄰區域異色之方法有a_n種
n-1
則a_n + a_n-1 = k*(k-1)
2 2
n = 3 => a_3 + a_2 = k*(k-1) => a_3 + a_2 = k*(1-k)
3 3
n = 4 => a_4 + a_3 = k*(k-1) => -a_4 - a_3 = k*(1-k)
4 4
n = 5 => a_5 + a_4 = k*(k-1) => a_5 + a_4 = k*(1-k)
......
n-1 n-1 n-1 n-1
+)n = n => a_n + a_n-1 = k*(k-1) => (-1) a_n +(-1) a_n-1 = k*(1-k)
--------------------------------------------------------------------------
n-1 2 3 n-1
(-1) a_n +k*(1-k) = k*(1-k) +K*(1-k) + .... + k*(1-k)
n-1
n-1 k*(1-k)[1-(1-k) ] n
(-1) a_n = -------------------- = -(k-1)-(1-k)
1-(1-k)
n n
a_n = (-1) (k-1) + (k-1)
6 6
所以 a_6 = (-1) (4-1) + (4-1) = 732 種塗法 #
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.168.220.237