Question

【題目】把一個圓分成n（n≥2）個扇形，依次記為，每一扇形都可用紅、白、藍三種不同顏色的任一種涂色，要求相鄰的扇形的顏色互不相同，問有多少種涂色法？

Answer 1

【答案】

【解析】

設涂法總數為.

當時，先對涂色有三種涂法，涂色后，繼涂，只有2種涂法，因而.

下面確定遞歸關系.

若先涂，有3種涂法；繼涂，只有2種涂法，然后涂，若只求與顏色不同，則有2種涂法，…，如此下去，最后圖，如只要求與顏色不同（這里未涉及與的顏色）仍有2種涂法，這樣總共有種涂法，但此種涂法可分為兩類；一類是與的顏色不同，這種涂法符合要求，總數為；另一類則是與的顏色相同，這種涂法不符合題設要求.如果把和合并，看成一個扇形，這類涂法相當于把圓分成個扇形，按題設要求的涂法，其總數為，于是得遞歸關系：

，即.

為求，令，則上式變成，得且，

∴，∴，

∴，

故總共有種涂法.