题目： 将圆分成 n n 个扇形,用 mm 种不同颜色染色,并且相邻的扇形不同色,问有多少种着色方法。

分析： 假设将圆分成 n n 个扇形符合题意的着色方法有 AnAn 种。 对第一个扇形着色有 m m 种，第二个扇形有 (m−1)(m−1) 种，第三个扇形有 (m−1) ( m − 1 ) 种 …… … … 第 n n 个扇形有 (m−1)(m−1) 种，但是这样着色会存在第 n n 个扇形和第一个扇形同颜色的情况，我们应该减去这样的情况。若第 nn 个扇形和第一个扇形同色，把这两个扇形合成一块，这就相当于 (n−1) ( n − 1 ) 个扇形用 m m 种颜色着色问题，它的解是 An−1An−1。由上可得出递推公式 An=m∗(m−1)n−1−An−1 A n = m ∗ ( m − 1 ) n − 1 − A n − 1 ，对这个式子移项化简得到 An−(m−1)n=−(An−1−(m−1)n−1) A n − ( m − 1 ) n = − ( A n − 1 − ( m − 1 ) n − 1 ) ，由此得到 An−(m−1)n A n − ( m − 1 ) n 是公比为 −1 − 1 的等比数列。 当 n=1 n = 1 ， A1=m A 1 = m ； 当 n=2 n = 2 ， A2=m(m−1) A 2 = m ( m − 1 ) ； 当 n≥3 n ≥ 3 ， An−(m−1)n=[A2−(m−1)2]∗(−1)n−2 A n − ( m − 1 ) n = [ A 2 − ( m − 1 ) 2 ] ∗ ( − 1 ) n − 2 ，化简得到 An=(m−1)n+(m−1)∗(−1)n A n = ( m − 1 ) n + ( m − 1 ) ∗ ( − 1 ) n

当然要是直接写算法求解的话，得到上面的递推公式就可以了，不需要解出后面的通项公式。