Question

【题目】把一个圆分成n（n≥2）个扇形，依次记为，每一扇形都可用红、白、蓝三种不同颜色的任一种涂色，要求相邻的扇形的颜色互不相同，问有多少种涂色法？

Answer 1

【答案】

【解析】

设涂法总数为.

当时，先对涂色有三种涂法，涂色后，继涂，只有2种涂法，因而.

下面确定递归关系.

若先涂，有3种涂法；继涂，只有2种涂法，然后涂，若只求与颜色不同，则有2种涂法，…，如此下去，最后图，如只要求与颜色不同（这里未涉及与的颜色）仍有2种涂法，这样总共有种涂法，但此种涂法可分为两类；一类是与的颜色不同，这种涂法符合要求，总数为；另一类则是与的颜色相同，这种涂法不符合题设要求.如果把和合并，看成一个扇形，这类涂法相当于把圆分成个扇形，按题设要求的涂法，其总数为，于是得递归关系：

，即.

为求，令，则上式变成，得且，

∴，∴，

∴，

故总共有种涂法.