基于分类事件和分步事件计数原理的涂色问题求解

林叶宾 陈颖频

【摘 要】涂色问题是高考数学的难点题型，笔者在长期的一线教学中摸索出一套基于分类事件和分步事件计数原理的通用解法，该方法巧妙地将涂色问题理解成数列递推问题，逐步缩小讨论区域，最终确定总涂色方案。本文通过一道高考题对该方法加以验证和演示。

【关键词】涂色问题;分类事件;分步事件;数列递推

【中图分类号】G633.6  【文献标识码】A  【文章编号】1671-8437（2021）16-0181-03

对于涂色问题这一高考数学的难点题型[1-2]，笔者根据实践教学经验探索出了一套基于分类事件和分步事件计数原理的通用解法，该方法巧妙将涂色问题理解成数列递推问题，逐步缩小讨论区域，最终确定总涂色方案。本文将系统介绍该方法，并通过一道高考题对该方法加以验证和演示。

1   涉及的知识与符号定义

1.1  分步计数原理与分类计数原理

计数的基本方法有两种，一种是分步计数，反映了步骤之间的计数关系;另一种是分类计数，反映了一个步骤内不同事件间的计数关系。通过计数的基本概念和方法，结合独立事件和相关事件，即可从本质上抓住涂色问题的解题核心。

1.1.1  分步事件及其在填涂问题中的建模

考虑到填涂过程中，填涂区域有先后次序，而先填入的颜色会影响后续区域的填涂，因此，可将填涂颜色的先后过程理解为计数问题中的分步问题。

1.1.2  分类事件及其在填涂问题中的建模

由于涂色问题存在区域间颜色相异的约束条件，可将一个区域的备选颜色集合分成“独立事件集”和“相关事件集”。“独立事件集”指备选填涂颜色中与已填涂颜色没有交集的集合。“相关事件集”指备选填涂颜色中与已填涂颜色有交集的颜色元素集合。对同一区域的备选填涂颜色，可将其分类为两种事件，即与已填涂颜色有交集的颜色集合以及与已填涂颜色没有交集的集合。

1.2  所涉及数学符号的定义

为方便后续讨论，下面介绍本文涉及的数学符号及其定义。

（1）假定一个区域的备选颜色集记为α，设α元素个数为Nα;

（2）假定“已填入图中的颜色集”记为β;

（3）“相关事件集”定义为δ=α∩β，则δ元素个数

为Nδ;

（4）“独立事件集”定义为将备选颜色集去除“相关事件集”后，剩余元素的集合，“独立事件集”记为 χ，该集合满足 χ∩β=，设 χ元素个数为Nχ，则有Nχ=Nα

?Nδ。

2   提出方法

涂色区域变多，则计数的步骤增多，因此，解决涂色问题最常规的方法就是先定下部分区域的颜色，让所需填涂的区域总数下降，再分析剩余未填涂区域的着色计数量，填涂前的计数量和填涂后的计数量存在某种递推关系，只需要确定这种递推关系，即可将涂色问题转换为数列递推问题。假定涂色数列已经递推到第i步（0 ≤ i ≤ m），已填涂i个区域，将这个阶段的涂色计数量记为am?i，笔者提出的方法就是要解决从am?i到am?i?1的递推问题。

对一个区域的备选事件，则将其分类为“独立事件集”和“相关事件集”来递推。下面分别讨论这两种情况：第一，当填入的颜色为“独立事件集”时，任意选择该集合的一种颜色都不会影响总计数量。根据这一原理，可以“独立事件集”中任意颜色放入需要填入的区域，然后将计数数列的“独立事件集”计数数列加以递推;第二，当填入颜色为“相关事件集”时，则需要结合已经填入颜色的区域来递推涂色计数数列。考虑到“相关事件集”中的颜色与已填涂区域的颜色有交集会影响相邻区域的涂色，因此需要对“相关事件集”中的每个颜色单独讨论。

根据分类计数原理，可将am?i进一步分解成两种计数，一种是针对“独立事件集”的计数，另一种是基于“相关事件集”的计数，即：

am?i=am?i|χ+am?i|δ       ＼* MERGEFORMAT （1）

其中，am?i|χ表示下一个要涂色区域的填涂颜色为 χ集合时的计数量，am?i|δ表示下一个要涂色区域的填涂颜色为δ集合时的计数量。

下面分别讨论两种计数的递推方法。

假定下一个区域Ω的备选事件α含有Nα种颜色，Nα=Nδ+Nχ，对于am?i|χ，考虑到 χ满足 χ∩β=，即“独立事件集”与已填涂颜色集无交集，则可选取 χ中的任意元素θ填入下一区域，对am?i|χ进行递推，具体递推公式

如下：

am?i|χ=Nχ         ＼* MERGEFORMAT （2）

对于am?i|δ，由于“相关事件集”δ含有与“已填入图中的颜色集”β有交集，则需要将δ中的每个颜色单独讨论，所以涂色问题真正的难点在于am?i|δ的递推。

3   举例

下面通过一道高考题详细阐述该方法。

例1：（2003年天津卷理科）某城市在中心广场建造一个花圃，花圃分为6个部分（如图1）。现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，栽种方法有多少种？

解：（1）假定填入颜色分别是①、②、③、④，根据上文提到的方法，在尚未涂色之前，i=0，m=6，β=，因此填涂A区域时，所有颜色事件都可以理解成是“独立事件集”χ的元素，也即α= χ={①，②，③，④}，Nχ=4，δ=α∩β=，则am?i|δ=0，根据式有：

a6=a6?0=a6?0|χ+a6?0|δ=a6?0|χ ＼* MERGEFORMAT （3）

考虑到此时的“独立事件集”χ已经包含了所有颜色，可将a6?0|χ简记为a6，则根据式得：

a6=Nχa5①→A=4a5①→A      ＼* MERGEFORMAT （4）

其中，a5①→A表示将“独立事件集”χ中元素①放入区域A前提下，剩余5个区域的计数总量。此时，拓扑图将退化为图2，显然，涂色问题已经简化为对a5①→A的计算。

（2）下面根据图2递推a5①→A。图2中，“已填入图中的颜色集”β={①}，假定接下来填涂的区域是B区域，根据第3节提出的方法，需分析B区域的备选事件，考虑到B区域和A区域的颜色不能相同，则有此时的α=χ={②，③，④}，此时Nχ=3，显然， χ∩β=，“独立事件集”χ已经包含了所有颜色，δ=α∩β=，则根据式有：

a5①→A=           ＼* MERGEFORMAT （5）

其中，表示将①放入区域A，②放入区域B前提下的计数量，其拓扑图如图3所示。

（3）根据图3进一步递推，设下一个填涂区域为区域F，图3中，β={①，②}，备选颜色集合为α= χ={③，④}，此时，Nχ=2，根据式有：

=2              ＼* MERGEFORMAT （6）

其中，表示将①放入区域A，②放入区域B，

③放入区域F前提下的计数量，其拓扑图如图4所示。

（4）根据图4递推。设下一个填涂区域为区域E。图4中，区域E的备选事件α={②，④}，已选颜色集β={①，②，③}，可见δ=α∩β={②}，则 χ=Cα β={④}，此时需将备选事件进行分类讨论，根据式有：

=a2|χ+a2|δ=+   ＼* MERGEFORMAT （7）

要计算式需计算和，分别将两者对应的拓扑图画出来，易确定出和，下面先计算，其拓扑图如图5所示。

（5）根據图5计算。填涂区域D，此时备选事件α={①，④}，β={①，②，③}，δ=α∩β={①}，故需要对备选事件中的颜色①和颜色④分别讨论，则根据式有：

=+       ＼* MERGEFORMAT （8）

篇幅所限，这里不再绘制和的拓扑图，根据的空间涂色分布可知=1。同理，=1，则有=+=2。

（6）计算，其拓扑图为图6所示。填涂区域

D，此时备选事件α={①，②}，β={①，②，③，④}，δ=

α∩β={①，②}，χ=，根据式有，

=+        ＼* MERGEFORMAT （9）

显然，=1，而=2。因此，=+=1+2=3。

将上述计算结果回溯可得：

=24×（+）

=24×（2+3）=120      ＼* MERGEFORMAT （10）

本文提出的方法巧妙利用了数列递推和分类、分步事件计数原理解决涂色问题，利用通项公式的上下标帮助完成涂色拓扑图的绘制，是一种简单且直观的解题

方法。

【参考文献】

[1]北京天利考试信息网.中国高考全编[M].拉萨：西藏人民出版社，2011.

[2]杜志建.高考复习讲义[M].乌鲁木齐：新疆青少年出版社，

2014.

【作者简介】

林叶宾（1984～），男，汉族，福建漳州人，本科，中学一级教师。研究方向：高中数学教学。

【通讯作者】

陈颖频（1986～），男，汉族，福建漳州人，博士，讲师。研究方向：时频分析技术、数字图像处理、计算机视觉。

Coloring Problem Solution Based on Classified Event and Counting Principle of Step-by-Step Event

Yebin Lin 1  Yingpin Chen 2

（1. Gangwei Middle School of Longhai town， Zhangzhou， Fujian， 363000; 2. College of Physics and Information Engineering， Minnan Normal University， Zhangzhou， Fujian， 363000）

Abstract： Coloring problem is a difficult problem in college entrance examination of mathematics. In the long-term front-line teaching， the author has explored a set of general solutions based on the principle of classified events and step-by-step event counting. This method skillfully understands the coloring problem as a sequence recurrence problem， gradually reduces the discussion area， and finally determines the total coloring scheme. This paper verifies and demonstrates the method by a college entrance examination question.

Key words： coloring problem; classification events; step-by-step events; sequence recurrence