组合染色问题：用m(m≥2)种颜色去涂1×n(n≥2)棋盘,每个方格涂一用m(m≥2)种颜色去涂1×n(n≥2)棋盘,每个方格涂一种颜色,使得相邻方格颜色相异,首末两格也异色且m种颜色都要用

Answer 1

首先,将它想象成首尾相接,第二个格子开始选色一直选到最后一个,有两种情况:第二个与最后一个颜色一样或不同.假设涂n个格子方法为Fn,Fn=(m-2)Fn-1+(m-1)Fn-2,(加号两边对应两种情况,相当于一个递推式,颜色相同那种情况,第二个和最后一个看成一个格子,就相当于涂n-2的情况）然后就是将其换成通项,F1=0,F2=m(m-1) (F1的情况首尾相当于同色所以是0),以下利用特征根（若不清楚,可以查一下）,得出Fn=(-1)^(n-1)A+(m-1)^(n-1)B,利用F1,F2可得出A=1-m,B=m-1
带入Fn即可,答案正确已验证.若有不清楚可再问我,