每日一题[101]圆排列

试题节选自北大附中2016届行知理科高二第3学段数学荣誉作业2．

1、一个圆环形花坛，分为$5$个区域（如图所示），每个区域种植一种花卉，有$4$种不同颜色供选，要求相邻区域种植的花卉颜色不同，求不同的花卉种植方法数．

2、将第1题中的区域数由$5$个替换为$n$个，求不同的花卉种植方法数．

3、将第2题中的花卉颜色数由$4$个替换为$m$个，求不同的花卉种植方法数．

---

直接处理问题3，对区域的总数$n$使用递推方法，设不同的花卉种植方法数为$a_n$，则有$a_1=m$，$a_2=m(m-1)$．

递推方法一　选定起点，将问题看成排成一个队列，需要满足首尾花卉不同．
那么不同的方案数有$m(m-1)^{n-1}$种．然后再考虑将首尾“拼接”起来，此时如果首尾的颜色不同，那么对应$a_n$种方法数；如果首尾的颜色相同，那么对应$a_{n-1}$种方法数．这样就得到了递推公式

$$a_n+a_{n-1}=m(m-1)^{n-1},n\geqslant 3.$$
递推方法二　选定起点，考虑起点开始的三个区域，则对应$n+1$个区域的花卉种植方法可以用两种方式得到：
一种是在$n$个区域的花卉种植方法的基础上，在第一、二个区域之间插入一种不同颜色的花卉，此时得到的$n+1$个区域的花卉种植方法开头三个区域花卉各不相同；
另一种是在$n-1$个区域的花卉种植方法的基础上，将第一个区域中部插入一种不同颜色的花卉，此时得到的$n+1$个区域的花卉种植方法开头三个区域花卉为$ABA$的形式，即一、三区域花卉相同．
因此可以得到递推公式 $$a_{n+1}=(m-2)a_n+(m-1)a_{n-1},n\geqslant 3.$$ 从两个递推公式均可推出通项公式为 $$a_n=\begin{cases} m,n=1,\\(m-1)\cdot (-1)^n+(m-1)^n,n=2,3,\cdots.\end{cases}$$