Question

排列组合涂色问题

如图，一环形花坛分成 四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为 给出思路，谢谢~

Answer 1

从A开始往后看,A有4中选择,B有3种,且AB不同.
如果C与A相同,C只有1种选择,D有3种
如果C与A不同,C有2种选择,D有2种
所以结果为4*3*(3*1+2*2)=84
扩展:一般的,设n块
环形
地里要种m种花(设为a(n)),则将n-1片花坛从任意点处断开,此时
断点
左右不相同,断点处可以种m-2种花,于是a(n)包含2*a(n-1);而断点左右相同的情况下,可以再断点种m-1种花,此时将两个断点合并,其
种类
数等价于a(n-2).于是a(n)=(m-2)*a(n-1)+(m-1)*a(n-2).解该递推
关系
得:(具体
解法
请参考
组合数学
的递推关系式的
特征方程
解法)
a(n)=(m-1)^n+(m-1)*(-1)^n.