环染色问题的另一种思考方式

        接上文。

        一个环形的花坛，分成n块，有m种不同颜色的花可供种植，要求相邻区域颜色不能相同，共有多少种方法？

        另一种思考方式如下。

        如图，

        不妨先给①区域染色，共有种染色方法。

        然后，我们逆时针依次染色，每块区域都有种染色方法。

        因此，总共有种染色方法。

        但是，这里包含了①、②颜色相同的情况。

        因此，我们得到

        初始条件

        则

        因此

        这和之前用二阶数列递推的方法得出的结果相同。

        在本题的数列求通项中，两边同除以是常规操作，此后可以累加相消。