排列組合題目，圓被半徑分成n個區域，相鄰塗異色
一個圓被半徑分割成\(n\)等份用\(k\)種顏色來塗,每一區域塗一色,相鄰異色,顏色可以重複,不一定k種顏色全用,求證塗法為\((k-1)(-1)^n+(k-1)^n\)[解]設用\(k\)種顏色塗\(n\)個區域,相鄰異色塗法有[color=red][color=black]\(a_n\)[/color],則\(a_n+a_n-1=k(k-1)^{n-1}\)[/color]
紅色部分是如何來的呢?麻煩知道老師能分享一下,謝謝! [quote]原帖由 [i]chu1976[/i] 於 2008-4-13 01:32 PM 發表 [url=https://math.pro/db/redirect.php?goto=findpost&pid=656&ptid=499][img]https://math.pro/db/images/common/back.gif[/img][/url]
一個圓被半徑分割成n等份用k種顏色來塗,每一區域塗一色,相鄰異色,顏色可以重複,不一定k種顏色全用,求證塗法為(k-1)(-1)^n+(k-1)^n
[解]設用k種顏色塗n個區域,相鄰異色塗法有[color=red][color=black]a_n[/color],則a_n+a_n-1=k(k-1)^n-1[/color]
紅色部分是如何來的呢?麻煩知道老師能分享一下,謝謝! [/quote]
由第 1 區開始圖顏色，有 k 種顏色可以用，
第 2 區必須跟第 1 區異色，所以有 k-1 種顏色可以用，
第 3 區必須跟第 2 區異色，所以有 k-1 種顏色可以用，
‧
‧
‧
第 n-1 區必須跟第 n-2 區異色，所以有 k-1 種顏色可以用，
第 n 區必須跟第 n-1 區異色，所以有 k-1 種顏色可以用。
所以以上共有 k(k-1)^{n-1} 種塗色法。
可是這個數據並不是 a_n ，因為第 n 區可能跟第 1 區同色或是異色，
所以這個數據包含有 n 個區域相鄰塗異色，以及 n-1 個區域相鄰塗異色(第 n 區與第 1 區同色)的情況，
所以這個數據是 a_n + a_{n-1}，故 a_n + a_{n-1} = k(k-1)^{n-1} for all n>=3，
再加上遞迴關係式的初始條件 a_2 = k(k-1) 與 a_3=k(k-1)(k-2) ，可以求出 a_n (以 n 及 k 表示)。
[color=Red][b]註：a_1 + a_2 並不會滿足上面的遞迴關係式，但是 a_2 + a_3, a_3 + a_4, .... 之後才會滿足上面的遞迴條件。[/b][/color]
[color=Red][b] 感謝 ptt 的 moun9 網友提醒。2011/04/10[/b][/color]
額外的補充：這個題目也可以改成 k 個球員要互相傳籃球的問題，教練隨便選一球員，由該球員開始傳球給其他人，此 k 位球員互傳了 n+1 次之後，又回到剛開始第一個傳出去的球員的手上，求方法數。做法跟上面一模一樣。
解題的其它部分，在全教會的 thepiano 老師有寫了，
討論串：h ttp://forum.nta.org.tw/examservice/showthread.php?t=42668 連結已失效
另外，其它相關資料，
1. [url=https://math.pro/db/viewthread.php?tid=741&;extra=#pid1296]https://math.pro/db/viewthread.php?tid=741&;extra=#pid1296[/url]
2. 陽明高中數學科 羅驥韡老師的《舊的圖色文題，新的計算方法》
[url=http://www.scribd.com/full/14174890?access_key=key-sqcrk2qz34pt63qgyvr]http://www.scribd.com/full/14174890?access_key=key-sqcrk2qz34pt63qgyvr[/url] 經由您的解釋我比較容易看得懂!
感謝您肯花時間來解這一題唷! 討論數學的感覺很好，
謝謝。 [color=red][color=black]不好意思關於此句[[/color]因為第 n 區可能跟第 1 區同色或是異色[/color][color=black]]我是覺得應該是[/color][color=#ff0000]第 n-1 區可能跟第 1 區同色或是異色[/color] 為什麼你會這樣覺得呢? 因為第n區與第1區不就有可能同色
這樣子不符合題意[相鄰異色]!
若有觀念錯誤麻煩指正 k(k-1)^{n-1} 並不是 a_n 喔～
你可以先想看看 k(k-1)^{n-1} 是怎麼來的～
就會發現，
因為在塗第 n 塊的時候，並沒有特別避開說要與第 1 塊不同，
而 a_n 的定義有要求第 n 塊跟第一塊要異色，
也因此 [color=Red][b]k(k-1)^{n-1} 比 a_n 多[/b][/color]，
而多多少呢？[color=Red][b]多出來的數目就是 a_{n-1}[/b][/color]
原因就是～當初在算 k(k-1)^{n-1} 時，
有可能會遇到第 n 塊跟第一塊相同的情況，
如果第 n 塊跟第 1 塊相同，就變成 n-1 格相鄰都途異色的區域囉！
題意[相鄰異色]，是限制在 a_n 上面，所以 k(k-1)^{n-1} 並不是 a_n，
k(k-1)^{n-1} 比 a_n 還要多！ 感謝你的解惑,讓我更清楚囉! 補充資料
h ttp://forum.nta.org.tw/examservice/showthread.php?t=21240 連結已失效
使用\( a_{n-1}+a_n=k \cdot (k-1)^{n-1} \)解題
中一中 賴老師工作室
[url=http://jflai.blogspot.com/2007/12/blog-post_7984.html]http://jflai.blogspot.com/2007/12/blog-post_7984.html[/url]
使用\( a_{n+1}=(k-2)a_n+(k-1)a_{n-1} \)解題
排列組合之塗色問題 台北縣立三民高中 楊建泰老師
101.4.10補充
連結已失效，請下載附加檔案
h ttp://blog.cshs.ntct.edu.tw/math/%e5%b0%88%e9%a1%8c%e7%a0%94%e7%a9%b6/
2011.6.11補充
用紅、黑、黃3種顏色塗下列9個不同的區域如下圖，規定每區需塗一色，顏色可以重複使用，但相鄰部分不得塗同色，則共有幾種不同的塗法？
(100玉井工商，[url=https://math.pro/db/thread-1131-1-1.html]https://math.pro/db/thread-1131-1-1.html[/url])
100.9.29補充
以O為圓心的圓上有n個相異點，依序為\( A_1 \)、\( A_2 \)、\( A_3 \)、…、\( A_n \)，此n個點將圓分割為\( A_1 O A_2 \)、\( A_2 O A_3 \)、\( A_3 O A_4 \)、…、\( A_n O A_1 \)等n個扇形區域。在m種不同顏色的色筆中任選一種顏色塗其中任一扇形區域，每區域一色，相鄰區域不同色，全部的方法數有\( S(n,m) \)，若\( S(n+2,m)=p S(n+1,m)+k S(n,m) \)，求\( p-k= \)？
(98彰化女中，[url=https://math.pro/db/viewthread.php?tid=741&page=1#pid1296]https://math.pro/db/viewthread.php?tid=741&page=1#pid1296[/url])
101.4.30補充
阿花參加著色比賽，主辦單位提供八種色筆，圖形為五格的圓形轉盤(如右圖，可以旋轉但不可以翻轉)，若規定顏色可以重複使用但是同色不可以相鄰，則阿花有種著色方式？
(RA628.swf)
投擲一顆公正六面骰子n次(各面為1,2,3,4,5,6點)，依序紀錄點數為\( x_1,x_2,x_3,…,x_n \)，設滿足\( (x_1-x_2)(x_2-x_3)(x_3-x_4)…(x_{n-1}-x_n)(x_n-x_1)\ne 0 \)的機率為\( P_n \)。求\( P_n+6 \cdot P_{n+1} \)之值(以n表之)
(101台中一中，感謝Ellipse提供同色不相鄰的解法)
[url=https://math.pro/db/viewthread.php?tid=1334&page=1#pid5252]https://math.pro/db/viewthread.php?tid=1334&page=1#pid5252[/url]
101.8.2補充
A-BCD為空間中的一正四面體，O為其中心，質點P可以在A、B、C、D、O中自由移動，而且規定從其中一點移動至另外一點稱為一步，若定義質點P從O點出發，最後又回到O點共走了n步的方法數為\( a_n \)，\( n \ge 2 \)(例如\( a_2=4 \) )，則\( a_{10}= \)
(101文華高中代理，[url=https://math.pro/db/thread-1462-1-1.html]https://math.pro/db/thread-1462-1-1.html[/url])
weiye提供的另解，[url=https://math.pro/db/viewthread.php?tid=1462&page=2#pid7008]https://math.pro/db/viewthread.php?tid=1462&page=2#pid7008[/url]
109.7.21補充
將一個固定不動的圓分成10個相等的扇形，並用紅藍綠三種顏色加以著色，相鄰的扇形顏色不同，則有[u] [/u]種著色方法。
(109文華高中代理，[url]https://math.pro/db/thread-3368-1-1.html[/url])
110.3.19補充
某校新建的教學大樓一樓共有8個班級，每個班級的班牌都是相同的大小，若學校想用紅，綠，藍，黃四種顏色將班牌上色，每個班牌只上一色，上色的要求如下:
(1)相鄰的兩個班級班牌不同色
(2)第一個班級與第八個班級的班牌顏色不同
(3)四種顏色均須用到
根據以上考量，請問有幾種不同的上色方法？
(108嘉義高中代理，[url]https://math.pro/db/thread-3369-1-1.html[/url])
著色問題另一種想法（俞老師）
列位所見，徇為精闢略抒管窺，敬請卓參
謝謝
回復 11# 俞克斌 的帖子
第五行(ii) 異色:等同 a2 擠入....
上方a2部分筆誤, 應更正為a3...
此方法與舊版數學101的P.259例題4類似
但俞老師解說顯然更清楚了^^ [size=3]一個圓用其半徑分割成 n (n ≥ 2) 個相異扇形，用 k (k ≥ 1) 種顏色來塗色。每一扇形塗一色, 相鄰扇形皆異色, 顏色可以重複使用且不一定 k 種顏色全用。[/size]
[size=3][/size]
[size=3]求證: 塗法數 [size=4]a[/size][size=2]n [/size][size=3]= [/size](k-1)ⁿ + (-1)ⁿ (k-1)
[/size][size=3][/size]
[size=3][/size]
[size=3]之前拜讀過的方法，大致上都是基於 [size=4]a[/size][size=2]n [/size]與之前項 ( [size=4]a[/size][size=2]n₋₁ [/size]或 [size=4]a[/size][size=2]n₋₁ [/size]與 [size=4]a[/size][size=2]n₋₂ [/size]) 的關係 (遞迴關係)。現用另一個思維--取捨原理，來考慮這個題目。[/size]
[size=3][/size]
[size=3][size=4]a[/size][size=2]n [/size][size=3]= (k 色塗 n 區方法數) - (前項中，存在相鄰區同色的聯集)[/size][/size]
[size=3][/size]
[size=3]= kⁿ - C(n,1)*kⁿ⁻¹ + C(n,2)*kⁿ⁻² -......+C(n,n-1)*(-1)ⁿ⁻¹ k + C(n,n)*(-1)ⁿ [color=red]k [/color][/size][size=1][color=navy](註[/color][color=navy])[/color][/size]
[size=3][color=#000080][/color][/size]
[size=3][color=#000080]= [color=#000000][color=blue]kⁿ - C(n,1)*kⁿ⁻¹ + C(n,2)*kⁿ⁻² -......+C(n,n-1)*(-1)ⁿ⁻¹ k + C(n,n)*(-1)ⁿ[/color] [/color][color=red]- C(n,n)*(-1)ⁿ + C(n,n)*(-1)ⁿ k[/color][/color][/size]
[size=3][color=#ff0000][/color][/size]
[size=3][color=#ff0000][color=#000000]=[color=blue] (k-1)ⁿ [/color]+ [/color][color=red](-1)ⁿ (k-1) [/color][color=black](配合二項式定理，得證)[/color][/color][/size]
[size=3][color=#ff0000][/color][/size]
[size=3][color=#ff0000][color=black][/color][/color][/size]
[size=3][color=#ff0000][color=black]註:[/color][color=black] 這裡最後一項是 C(n,n)*(-1)ⁿ [/color][color=black]k (各區皆同色，有 k 種方法) 而非依之前規律的 C(n,n)*(-1)ⁿ，是因為最後"環繞一圈"之故: 若本題各區域呈一直線，則規律將保持 (當然這種情況一般會用乘法原理簡單解，不太會想用取捨原理)。[/color][/color][/size]
[size=3][color=#ff0000][color=black]心得: 歸納規律時，應考慮驗證極端情況是否可成立 -- 這是例外常發生之處。[/color][/color][/size]
[size=3][/size]
[size=3]---------------------------------------------[/size]
[size=3][/size]
[size=3]另一個想法: 經由古典機率求方法數 (亦應用遞迴式)[/size]
[size=3][/size]
[size=3]考慮問題: 由第 1 區開始，以順時針方向依序將下一區塗色，過程中在不與上一區同色的前提下隨機選色。則第 n 區與第 1 區異色的機率為?[/size]
[size=3][/size]
[size=3]令 P[size=2]m[/size] 表示第 m 區與第 1 區異色的機率，則有:[/size]
[size=3][/size]
[size=3]P[size=2]m[/size] = [(k-2) /(k-1)] * P[size=2]m[size=3]₋₁[/size][/size] + (1 - P[size=2]m[size=3]₋₁[/size][/size]) = 1 - [P[size=2]m[size=3]₋₁ /(k-1)]，m ≥ 2; 且 P₁ = 0[/size][/size][/size]
[size=3][/size]
[size=3]⇒ P[size=2]n[/size] = [-1 /(k-1)]ⁿ⁻² *(1 /k) + (k-1) /k[/size]
[size=3][/size]
[size=3]所求塗法數 [size=4]a[/size][size=2]n [/size]= k*(k-1)ⁿ⁻¹ *P[size=2]n[/size] =[color=black] (k-1)ⁿ + (-1)ⁿ (k-1)[/color][/size]
頁:
[1]