小题(难)[递推关系]{计数原理，染色问题，传球问题，种植问题}

作者: 7300T | 来源:发表于2019-05-02 12:27 被阅读78次

有一个圆形区域被分成5块（如图1），在每一块区域内种植植物，相邻的两块区域种植不同的植物，现有4种不同的植物选择，求共有多少种不同的种植方法.

图1
请你先尝试自己解答一下

尝试解答
【问题特征】计数问题.
【问题的解答】
思路1利用两个基本原理.
解法1 本题可归结为涂色问题：用4种不同颜色给每一块区域涂色，相邻的两块区城不能同色，所有的涂色方法分为两类：（1）A，C同色，先涂A，C有4种方法，再涂B，D有3种方法，然后涂E有2种方法，故A，C同色的涂法种数为.
（2）A，C异色，先涂A，B，C有4×3×2种方法.
①若A，D同色，涂E有3种方法
②若A，D异色，先涂D有2种方法，再涂E有2种方法.故A，C异色的涂法种数为，
因此，所有的涂色方法种数为.
思路2 利用递推数列.
解法2 设一个圆形区域被分成n块扇形，如图2，用4种不同颜色给每一块区城涂色，相邻的两块区域不能同色，所有的涂色方法种数为,不管1，n异色的涂色方法种数为，这些涂色方法分为两类

图2
（1）1，n异色，有种涂法；
（2）1，n同色，相当于把第1，n块扇形合并为一块扇形，圆形被分成n-1块扇形，故有种涂法.
据分类加法计数原理，.
而，所以，，
故共有240种不同的种植方法.
【注意点】
1.解决计数问题需学会合理地分类、分步.
2.利用递推数列解决计数问题的基本思想是把问题一般化，再特殊化，关键是利用两个基本原理建立递推关系.【相关问题】
1，如图3，某城市的中心广场建造一个花圃，花圃分6个部分，现要栽种4种不同颜色的花，每部分裁种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有___种.

图3

尝试解答

【答案与提示】

提示：问题等价于用4种不同的颜色涂图4中的6个不同区域，相邻的两个区域不能同色.

图4

分两步完成.
第一步，涂6有4种方法；
第二步，涂其余5个区域，又相当于将一个圆分成5个扇形，用3种颜色给5个扇形涂色，相邻的两个扇形不能同色，为此，将问题一般化，将一个圆分成，n个扇形，用3种颜色给n个扇形涂色，相邻的两个扇形不能同色，所有涂法种数为 $a_n$ ,则 $a_n+a_{n-1}=3\times 2^{n-1}（n\geq 3）$ .，而 $a_1=3，a_2=3×2=6$ ，所以 $a_3=6$ ， $a_4=18$ ， $a_5 =30$ 因此，涂其余5个区域有30种方法.
据分步乘法计数原理，涂色方法种数为N=
4×30=120，即不同的栽种方法种数为120.

2.4个人互相传球，要求接球后马上传给别人.由甲传球，并作为第一次传球，求经过5次传球仍回到发球人甲手中的传球方式的种数.

尝试解答

【答案与提示】

提示：由甲发球，经n次传球后仍回到甲手中的传球方式种数记为 $a_n$ ，首先，由甲发球，球传出后自然不能回到他手中，故 $a_1=0$ .再考察经两次传球情形：先由甲发球给其他三人中的一位，再由此人传回给甲，故 $a_2=3$ .
上述讨论启发我们作一般的讨论，经n-1次传球后，不同的传球方式共有3-1种，这些方式可分为两类：一类是再经第n次传球后仍回到甲手中的 $a_n$ .种不同的传球方式；一类是经第n-1次传球正好落入甲手中的 $a_{n-1}$ 种不同的传球方式，故有 $a_n+a_{n-1}=3^{n-1}$
因此， $a_3=6，a_4=21，a_5=60$ ，故经过5次传球仍回到发球人甲手中的传球方式的种数为60.