“无心”和“有心”染色问题

【摘要】 本文对“无心”和“有心”染色问题建立了递推数列模型，通过对递推数列模型的运算给出了公式，使得这两类问题的计算得到了简化.

【关键词】 “无心”染色 “有心”染色；递推数列

图 1 一、“无心”染色问题

如图1，将圆分成n（n≥2）个扇形S1，S2，…，Sn，

现用m m≥2 种颜色给这些扇形染色，每个扇形染

色，每个扇形染一种颜色且要求相邻扇形的染色互不

相同，问有多少种染色方法？

解析 设染色方法数为an.

（1）求初始值.n=2时，给S1染色有m种方法，继而给S2染色只有m-1种方法，（因S1与S2不同色），所以a2=m（m-1）.

（2）求递推关系.因S1有m种染色方法，S2有m-1种染色方法，S3有m-1种染色方法，…，Sn有m-1种染色方法（只保证Si+1与Si不同色，i=1，2，…，n-1；而不保证Sn与S1不同色），这样共有m（m-1）n-1种染色方法，这些染色方法可分为两类：

一类是Sn与S1不同色，这类方法有an种.另一类是Sn与S1同色，则将Sn与S1合并为一个扇形，并注意到此时Sn-1与S1不同色，故这时的染色方法有an-1种.由加法原理得：an+an-1=m（m-1）n-1.

（3）求an.

令bn= an （m-1）n ，则bn+ 1 m-1 bn-1= m m-1 ，

图 2 即：bn-1=- 1 m-1 （bn-1-1）.

可得：an=bn·（m-1）n=（m-1）n+（-1）n（m-1）.

例1 如图2，用4种不同的颜色，给一个六棱锥的侧面

染色，一种颜色染一个侧面，而且相邻面的颜色不能相同，

问有几种染色方法？

解析 如图3所示，可把立体图形连续压缩成平面图形，

该问题转化为无心染色问题，由m=4，n=6，可得an=（4-1）6+（-1）6（4-1）=36+3=732种.所以有732种染色方法.

图 3

二、“有心”染色问题

图 4 如图4，设用m（m≥4，m∈ N +）种颜色给n（n≥3，n∈ N +）边形的顶点和中心点（染色点=n+1）染色，每点染一色且相邻点染不同的色，不同的染色方法为aN.

解析 （1）先染A0，有m种染法；

（2）再染A1A2….

A1与A0不同色，有（m-1）种染法；A2与A0，A1不同色，有（m-2）种染法…

当n=3时，a3=（m-1）（m-2）（m-3）；

当n>3时，已知A1，A2有（m-1）、（m-2）种染法；

A3与A0，A2不同色，有（m-2）种染法；同理，A4，…，An-1均有（m-2）种染法.最后得到An，若考虑An与An-1不同色，仍有（m-2）种，则得：（m-1）（m-2）n-1种染法.

但该计算中有两种情况：一种是An与A1不同色，这符合要求，有an-1种染法，另一种是An与A1同色，这不符合要求，应排除，这时可以把An与A1合并看作一点，则得排除的染法为an-1种，故得：a3=（m-1）（m-2）（m-3），…，an=（m-1）（m-2）n-1-an-1，

递推得：an=（m-2）n+（-1）n·（m-2）.

综上 可得公式：aN=m（m-2）[（m-2）n-1+（-1）n]=m（m-2）n+ （-1）nm（m-2）.

（式中m≥4，m∈N+；n≥3，n∈N+）.

例2 若想给一个三棱锥S-ABC的每个顶点染上一种颜色，并使同一条棱的两端点异色，如果现有4种颜色可供使用，那么不同的染色方法的总数是多少？

图 5

解 如图5所示，可把立体图形

连续压缩成平面图形，该问题转化为

有心染色问题，由m=4，n=3，

可得aN=4（4-2）3+（-1）3×4×（4-2）=24种.

所以有24种染色方法.

【参考文献】

[1]刘华巧，李德胜.几类递推数列通项公式的推导及应用[J].高师理科学刊，2007，7.

[2]唐臂.递推数列的通项公式[J].科技创新导报，2010，11.

[3]曹汝成.组合数学[M].华南理工大学出版社，2012，7.

推荐访问:染色 有心 无心

---