几种染色问题的计数法

排列组合中涂色问题的常见方法及策略与涂色问题有关的试题新颖有趣,其中包含着丰富的数学思想。

解决涂色问题方法技巧性强且灵活多变，故这类问题的利于培养学生的创新思维能力、分析问题与观察问题的能力，有利于开发学生的智力。

本专题总结涂色问题的常见类型及求解方法。

一、 区域涂色问题1、 根据分步计数原理，对各个区域分步涂色，这是处理染色问题的基本方法。

例1、 用5种不同的颜色给图中标①、②、③、④的各部分涂色，每部分只涂一种颜色，相邻部分涂不同颜色，则不同的涂色方法有多少种？分析：先给①号区域涂色有5种方法，再给②号涂色有4种方法，接着给③号涂色方法有3种，由于④号与①、②不相邻，因此④号有4种涂法，根据分步计数原理，不同的涂色方法有5434240⨯⨯⨯=2、 根据共用了多少种颜色讨论，分别计算出各种出各种情形的种数，再用加法原理求出不同的涂色方法种数。

例2、（2003江苏卷）四种不同的颜色涂在如图所示的6个区域，且相邻两个区域不能同色。

分析：依题意只能选用4种颜色，要分四类：（1）②与⑤同色、④与⑥同色，则有44A ； （2）③与⑤同色、④与⑥同色，则有44A ；（3）②与⑤同色、③与⑥同色，则有44A ； （4）③与⑤同色、② 与④同色，则有44A ；（5）②与④同色、③与⑥同色，则有44A ；所以根据加法原理得涂色方法总数为544A =120例3、（2003年全国高考题）如图所示，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着方法共有多少种？ 分析：依题意至少要用3种颜色1) 当先用三种颜色时，区域2与4必须同色， 2) 区域3与5必须同色，故有3A 种；① ②③ ④ ⑤⑥3) 当用四种颜色时，若区域2与4同色，4) 则区域3与5不同色，有44A 种；若区域3与5同色，则区域2与4不同色，有44A 种，故用四种颜色时共有244A 种。

由加法原理可知满足题意的着色方法共有34A +244A =24+2⨯24=723、 根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形的种数，再用加法原理求出不同涂色方法总数。

解题篇经典题突破方法高二数学2019年5月涂色问题的常见解进及策曜■江苏省盐城市时杨中学刘长柏对于涂色问题的解法，拨云破雾、还其本来面目，就会发现实质是用分类或分步计数原理导航，通过深入缜密分析题意，将原题化归为熟悉的排列、组合或综合题型，逐类分步推理求解的。

涂色问题的常见解法：根据分步计数原理，对各个区域分步涂色；根据共用了多少颜色分类讨论；根据不相邻区域是否同色分类讨论等。

一・根据分步计数原理，对各个区域分步涂色伸I f用红黄绿三种颜色给图1中的5个带状格子涂色。

要求每格涂一种颜色且相邻格子不能涂同一种颜色•共有多少种不同的涂法？图1分析：根据分步计数原理，对各个区域分步涂色，这是处理染色问题的基本方法。

解：从满足一格一颜色、邻格不同色的限制条件入手，分成三类：一类是左边三个邻格从红黄绿中任取3色，涂法有A；种，且右面两相邻格涂法有A；种。

共有Aj・A；=12（种）。

二类是左起4格涂成红绿红绿的类似模式有A；种，末一格涂法有A；种，共有A；・A；=12（种）。

三类是左起4格涂成红绿红黄的类似模式有A：种，其中产生与一类重复的有6种（如红绿红黄绿与一类的红绿红黄绿）。

综上得：A；A；+A；A；+（A：—6）=42（种）。

点评：带状区域的涂色问题的解法，与推导排列数公式A；的思想方法类似，可构造排好顺序的m个空位（格），从n个不同元素中任取m Cm^n'）个填充。

此类涂色题一般可转化成有限制条件的排列或组合问题。

练习1：用5种不同的颜色给图2中标①、②、③、④的各部分涂色，每部分只涂一种颜色•相邻部分涂不同颜色，则不同的涂色方法有多少种？解：先给①号区域涂色有5种方法，再给②号涂色有4种方法，接着给③号涂色方法有3种•由于④号与①、②不相邻，因此④号有4种涂法，根据分步计数原理，不同的涂色方法有5X4X3X4=240（种）。

二、根据共用了多少颜色分类讨论制2如图3所示，花坛内有5个花池，有5种不同颜色的花卉可供栽种，每个花池内只能栽种同颜色的花卉，相邻两池的花卉颜色不同，则最图3多有多少种栽种方案？分析：本题要完成的事件是花池内栽种花卉；由于5种不同颜色的花卉可供选择，所以可选择3种、4种、5种不同颜色的花卉栽种•可见有3类方法可独立完成这件事，而每一类又不能“一次性”完成，所以分步进行。

操作步骤l．编号取无菌平皿9套，分别用记号笔标明10-4、10-5、10-6。

(稀释度)各3套。

另取6支盛有4.5mL无菌水的试管，依次标是10-1、10-2、10-3、10-4、10-5、10-6。

2．稀释用lmL无菌吸管吸取lmL已充分混匀的大肠杆菌菌县液(待测样品)，精确地放0.5ml 至10-1的试管中，此即为10倍稀释。

将多余的菌液放回原菌液中。

将10-1试管置试管振荡器上振荡，使菌液充分混匀。

另取一支lml吸管插入10- 1试管中来回吹吸菌悬液三次，进一步将菌体分散、混匀。

吹吸菌液时不要太猛太快，吸时吸管伸人管底，吹时离开液面，以免将吸管中的过滤棉花浸湿或使试管内液体外溢。

用此吸管吸取10-1菌液lmL，精确地放0.5mL至10-2试管中，此即为100倍稀释。

……其余依次类推。

放菌液时吸管尖不要碰到液面，即每一支吸管只能接触一个稀释度的菌悬液，否则稀释不精确，结果误差较大。

3.取样用三支1mL无菌吸管分别吸取10-4、10-5和10-6的稀释菌悬液各lmL，对号放入编好号的无菌平皿中，每个平皿放0.2mL。

不要用lmL吸管每次只靠吸管尖部吸0.2mL稀释菌液放入平皿臼，这样容易加大同一稀释度几个重复平板间的操作误差。

4．倒平板．尽快向上述盛有不同稀释度菌液的平皿中倒入融化后冷却至45℃左右的牛肉膏蛋白胨培养基约15毫升/平皿，置水平位置迅速旋动平皿，使培养基与菌液混合均匀，而又不使培养基荡出平皿或溅到平皿盖上。

由于细菌易吸附到玻璃器皿表面，所以菌液加入到培养皿后，应尽快倒入融化并于已冷却至45℃左右的培养基，立即摇匀，否则细菌将不易分散或长成的菌落连在一起，影响计数。

待培养基凝固后，将平板倒置于37℃恒温培养箱中培养。

5．计数培养48h后，取出培养平板，算出同一稀释度三个平板上的菌落平均数，并按下列公式进行计算，每毫升中菌落形成单位(cfu)=同一稀释度三次重复的平均菌落数×稀释倍数×5。

§106染色、错排等问题与递推法一、错排问题：三、其他问题：二、染色问题：2.走楼梯问题：3.汉诺塔问题：4.概率问题：1.条型域：2.环型域：①无心环型域②有心环型域3.其他型：§106递推法解染色、错排等问题1.传球(踢毽子)问题：概率与统计简述总体样本抽样估计推断回归分析相关分析分布列及期望概率计数计数问题总述复杂的计数问题简单的计数问题排列组合型计数原理型十大题型两理两数四原则十大题型递推法①相邻——捆绑法⑧错排：二元1种；三元2种；四元9种……②不邻(相离)——插空法⑥分组相同元素——0-1法不同元素——公式法⑩染色——递推法⑨定序——倍缩法(等概率法)；插空法两理两数四原则十大题型递推法③在与不在④含与不含⑤至多与至少特殊优先直接法正难则反间接法——⑦分配均匀分配非均匀分配先分组后分配分组1.相同元素的分组：2.不同元素的非均匀分组：3.不同元素的均匀分组：4.不同元素的混合分组：①将2n个不同元素均匀的分成2组,共有种分法②将3n 个不同元素均匀的分成3组,共有种分法先均匀后非均匀参分配常规法处理分配1.不同元素的分配：2.相同元素的分配(分组)：先分组后分配将n个相同元素分成k组，共有种分法注：将n个相同元素看成是n个“0”然后将k-1个隔板“1”插入n-1个空位即可0000……00所以称为0—1法；隔板法；挡板法0—1法含与不含：在与不在：至多与至少：特殊优先直接法正难则反间接法定序1.倍缩(等概率)法：本质上、是不尽相异元素的全排列已知n个元素中，有m1个元素相同，又有m2个元素相同不尽相异元素的全排列公式则这n个元素所有的排列数为：称其为不尽相异元素的全排列……又有mk个元素相同(m1+m2+…+mk≤n)含与不含：在与不在：至多与至少：特殊优先直接法正难则反间接法定序1.倍缩(等概率)法：本质上、是不尽相异元素的全排列2.逐个插空法：相邻问题捆绑法1.定义：n元中有m个元素要求排在一起的排列2.解法：先捆可邻成大元次变个数全排列不邻(相离)问题插空法1.定义：n元中有m个元素都不能排在一起的排列2.解法：先排可邻后插空多元切忌间接法二元可用间接法亮灯空位是变式相间问题位置法相邻相离综合体一般解法位置法一、错排问题：三、其他问题：二、染色问题：2.走楼梯问题：3.汉诺塔问题：4.概率问题：1.条型域：2.环型域：①无心环型域②有心环型域3.其他型：§106递推法解染色、错排等问题1.传球(踢毽子)问题：一、错排：1.定义：某排列所有元素不在原位置的排列2.解法：①背诵法：②递推法：练习1.错排：(1)(1993年全国)同室四人各写一张贺年卡,先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡不同的分配方式有A.6种B.9种C.11种D.23种【B】a2＝1；a3＝2；a4＝9；a5＝44……参新课课件§244的内容……(2)(1991年上海)设有编号为1，2，3，4，5的五个球，和编号为1,2,3,4,5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球,并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为A.20种B.30种C.60种D.120种解：N＝【B】二、染色问题：1.条型域：,相邻…32n1注1：染色基础是条型方法多多随爱好从头到尾逐个染乘法原理显神功练习2.条型域染色：区域不能同色,则共有种染法注2：隐含了颜色有剩余(3)如图，用5种不同的颜色给图中的4个格子涂色，每个格子涂一种颜色，相邻格子颜色不同则不同的涂色方法共有种解：如图,用k种颜色染n块区域，二、染色问题：1.条型域：,相邻…32n1区域不能同色,则共有种染法如图,用k种颜色染n块区域，给涂圆中n块区域涂色相邻的区域不同色，则2.环型域：①无心环型域:①公式法：②递推法：参新课课件附录37的内容……如图，用k种不同的颜色(4)如图,用5种不同的颜色,涂圆中颜色，相邻的区域不同色，则不同的染色方法有_____种析：练习3.无心环型域染色：4块区域，要求每个区域染一种解：(5)如图,用6种不同的颜色,涂圆中颜色，相邻的区域不同色，则不同的染色方法有_____种5块区域，要求每个区域染一种解：给涂圆中n块区域涂色相邻的区域不同色，则2.环型域：①无心环型域:①公式法：②递推法：参新课课件附录37的内容……如图，用k种不同的颜色②有心环型域无心环型域先染心(6)如图,用5种不同的颜色,涂圆中5块区域,要求则不同的染色方法有______种析1：A5有5种染色方法析2：剩余4块区域，4色染之综上，N＝5×84＝420练习4.有心环型域染色：每个区域染一种颜色，相邻的区域不同色，有心环型域无心环型域先染心给涂圆中n块区域涂色相邻的区域不同色，则2.环型域：①无心环型域:①公式法：②递推法：参新课课件附录37的内容……如图，用k种不同的颜色②有心环型域无心环型域先染心③其他型域：两理两数四优先……练习5.其他型域的染色：(7)用5种不同的颜色给四棱锥P-ABCD的5个面涂色要求每个面染一种颜色，相邻的两面不同色，则不同的染色方法有______种PDCBA到此，Ex6也……N＝5×84＝420三、其他问题：1.传球(踢毽子)问题：注1：该类问题；解法甚多，可参新课件附录37的内容……注2：该类问题等价于无心环型域的染色问题可转换成：k种颜色n块区域的无心环型域的染色问题k个人进行传球游戏，由甲先传，经过n次传球后，球仍回到甲手中的传球方法数(8)4个人进行传球游戏，由甲先传，经过4次传球后,球仍回到甲手中的传球方法共有A.21种B.24种C.27种D.42种练习6.传球(踢毽子)问题：可以转换成k种颜色n块区域的无心环型域的染色问题k个人进行传球游戏，由甲先传，经过n次传球后，球仍回到甲手中的传球方法数①现来看：甲→乙→丙→丁→甲的传球与4色4环染色的等价关系②甲→乙→丙→甲→丁③【A】一、错排问题：三、其他问题：二、染色问题：2.走楼梯问题：1.传球(踢毽子)问题：练习7.走楼梯问题：(9)欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有A.34种 B.55种 C.89种D.144种析：设走n级有an种走法，则故an=an-1+an-2i：当第一步是一步一级时，ii：当第一步是一步两级时，则余下的n-1级有an-1种走法则余下的n-2级有an-2种走法由递推可得a10=89易得，a1=1，a2=2【C】一、错排问题：三、其他问题：二、染色问题：2.走楼梯问题：3.汉诺塔问题：4.概率问题：1.传球(踢毽子)问题：上述问题，高考中暂未涉及，故从略有时间，有精力的同学，可参考新课课件附录37的内容……针对训练：预习：1.《精炼案》P：83Ex52.《新考案》P：152Ex5二项式定理及求特定项3.(2004年湖北)将标号为1,2,3,…,10的10个球，放入标号为1，2,…,10的10个盒子内，每个盒内放一个球,则恰好有3个球的标号与其所在盒子的标号不一致的放入方法共有_______种。