排列组合中的涂色问题北师大PPT学习教案

1、会计学1排列组合中的涂色问题北师大排列组合中的涂色问题北师大涂色问题【例1】 思路探索 第1页/共35页第2页/共35页第3页/共35页2345553A +2A +A法 按涂色区域分类第4页/共35页【训练1】 ABCD第5页/共35页344422A +A =72法 ：三色或四色涂完第6页/共35页A第7页/共35页第8页/共35页区域涂色问题1.根据分步计数原理，对各个区域分步涂色，这是处理 染色问题的基本方法。例1、用5种不同的颜色给图中标、的各部分涂色，每部分只涂一种颜色，相邻部分涂不同颜色，则不同的涂色方法有多少种？分析：先给号区域涂色有5种方法，再给号涂色有4种方法，接着给号涂色方法

2、有3种，由于号与、不相邻，因此号有4种涂法，根据分步计数原理，不同的涂色方法有5 4 3 4240 第9页/共35页2、根据共用了多少种颜色讨论，分别计算出各种出各种 情形的种数，再用加法原理求出不同的涂色方法种数。例2、（2003江苏卷）四种不同的颜色涂在如图所示的6个区域， 且相邻两个区域不能同色 分析：依题意只能选用4种颜色，要分四类：（1）与同色、与同色，则有44A44A44A（2）与同色、与同色，则有（3）与同色、与同色，则有（5）与同色、与同色，则有44A （4）与同色、与同色，则有44A所以根据加法原理得涂色方法总数为第10页/共35页例3、（2003年全国高考题）如图所示，一个

3、地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着方法共有多少种？分析：依题意至少要用3种颜色 第11页/共35页 234441 2 43 5A =242 2 43 52 43 52A =48法 ：按区域分、同色且 、同色，共种、同色且 、异色或 、异色且 、同色共种由加法原理得第12页/共35页3.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形的种数，再用加法原理求出不同涂色方法总数。例4.用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内，每个区域涂一种颜色，相邻两个区域涂不同的颜色，如果颜色可

4、以反复使用，共有多少种不同的涂色方法？第13页/共35页C第14页/共35页第15页/共35页4.根据相间区使用颜色的种类分类例5如图， 6个扇形区域A、B、C、D、E、F，现给这6个区域着色，要求同一区域涂同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种不同的颜色可有多少种方法？第16页/共35页第17页/共35页第18页/共35页第19页/共35页第20页/共35页第21页/共35页第22页/共35页面涂色问题例9、从给定的六种不同颜色中选用若干种颜色，将一个正方体的6个面涂色，每两个具有公共棱的面涂成不同的颜色，则不同的涂色方案共有多少种？分析：显然，至少需要3三种颜色，由于有多种

5、不同情况，仍应考虑利用加法原理分类、乘法原理分步进行讨论第23页/共35页第24页/共35页第25页/共35页第26页/共35页第27页/共35页 、如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？第28页/共35页解: 按地图A、B、C、D四个区域依次分四步完成, 第一步, m1 = 3 种, 第二步, m2 = 2 种, 第三步, m3 = 1 种, 第四步, m4 = 1 种,所以根据乘法原理, 得到不同的涂色方案种数共有 N = 3 2 11 = 6 种。第29页/共35页 、如图,要给地图

6、A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？ 若用2色、4色、5色等,结果又怎样呢？ 答:它们的涂色方案种数分别是 0、 4322 = 48、 5433 = 180种等。思考：第30页/共35页.如图,用5种不同颜色给图中的A、B、C、D四个区域涂色, 规定一个区域 只涂一种颜色, 相邻区域必须涂不同的颜色, 不同的涂色方案有 种。ABCD分析：如图，A、B、C三个区域两两相邻，A与D不相邻，因此A、B、C三个区域的颜色两两不同，A、D两个区域可以同色，也可以不同色，但D与B、C不同色。由此可见我们需根据A与

7、D同色与不同色分成两大类。解：先分成两类：第一类，D与A不同色，可分成四步完成。第一步涂A有5种方法，第二步涂B有4种方法；第三步涂C有3种方法；第四步涂D有2种方法。根据分步计数原理，共有5432120种方法。根据分类计数原理，共有120+60180种方法。第二类，A、D同色，分三步完成，第一步涂A和D有5种方法，第二步涂B有4种方法；第三步涂C有3种方法。根据分步计数原理，共有54360种方法。第31页/共35页、某城市在中心广场建造一个花圃，花圃分为6个部分（如右图）现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种.（以数字作答） 6 5 4 3 2 1（1）与同色，则也同色或也同色，所以共有N1=43221=48种；所以，共有N=N1+N2+N3=48+48+24=120种. （2）与同色，则或同色，所以共有N2=43221=48种；（3）与且与同色，则共N3=4321=24种 解法一：从题意来看6部分种4种颜色的花，又从图形看知必有2组同颜色的花，从同颜色的花入手分类求第32页/共35页6、将种作物种植在如图所示的块试验田里，每块种植一种作物且相邻的试验田不能种植同一种作物，不同的种植方法共有种（以数字作答）425、如图，是5个相同的正方形，用红、黄、蓝、白、黑5种颜色涂这些正方形，使每个正方形涂一种颜色，且相邻的正方形涂