组合染色问题：用m ( m ≥ 2)种颜色去涂1 × n( n ≥ 2) 棋盘,每个方格涂一

题目

组合染色问题：用m ( m ≥ 2)种颜色去涂1 × n( n ≥ 2) 棋盘,每个方格涂一
用m ( m ≥ 2)种颜色去涂1 × n( n ≥ 2) 棋盘,每个方格涂一种颜色,使得相邻方格颜色相异,首末两格也异色且m种颜色都要用到的涂色方案有多少
（m-1）^n+（-1）^n（m-1）
求思路过程,怎么想怎么考虑怎么理解?以什么方式计算?思路最好和答案形式吻合.

答案

首先,将它想象成首尾相接,第二个格子开始选色一直选到最后一个,有两种情况:第二个与最后一个颜色一样或不同.假设涂n个格子方法为Fn,Fn=(m-2)Fn-1+(m-1)Fn-2,(加号两边对应两种情况,相当于一个递推式,颜色相同那种情...