最新排列组合中染色问题(精华版)
- 格式：ppt
- 大小：565.50 KB
- 文档页数：23
当前位置：文档之家 › 最新排列组合中染色问题(精华版)
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
分析：依题意至少要用3种颜色
3.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻 区域同色与不同色入手，分别计算出两种情形的种数，再用加 法原理求出不同涂色方法总数。
例4.用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内， 每个区域涂一种颜色，相邻两个区域涂不同的颜色，如果颜色可 以反复使用，共有多少种不同的涂色方法？
（3）②与⑤同色、③与⑥同色，则有
A
4 4
（4）③与⑤同色、②与④同色，则有 A
4 4
（5）②与④同色、③与⑥同色，则有 A
4 4
所以根据加法原理得涂色方法总数为
例8、（全国高考题）如图所示，一个地区分为5个 行政区域，现给地图着色，要求相邻区域不得使用同一颜色， 现有4种颜色可供选择，则不同的着方法共有多少种？
分析：显然，至少需要3三种颜色，由于有多种不同情况， 仍应考虑利用加法原 理分类、乘法原理分步进行讨论
结束语
谢谢大家聆听！！！
24
第一类：由1，2，4，5，6作数码；首先从2，4，6中任选
一个作个位数字有 A
1 3
，然后其余四个数在其他数位上全排
A N AA 列有 4 ，所以 1 4
4
1
34
第二类：由1，2，3，4，5作数码。依上法有
N AA 1 4
2
24
故 N=N1+N2=120(个 )
【练习1】由1，2，3，4，5，6可以组成多少个 (1)无重复数字的2的倍数的的三位数? (2)无重复数字的能被3整除的三位数? (3)无重复数字的且是6的倍数的三位数？
涂 2 色 ： A 5 2 2 0 ； 涂 3 色 ： C 1 2 A 5 3 1 2 0 ； 图6
涂 4 色 ： A 5 4 1 2 0 ， ∴ 共 有 2 0 1 2 0 1 2 0 2 6 0 种
解后思:关于涂色问题,一般来说,以”某两个区域同色或 异色分类”或”以使用颜色的多少分类”是常见的两种 思考方式.
**练习1.(2006年江苏卷）今有2个红球、3个黄球、4个白球， 同色球不加以区分，将这9个球排成一列有 种不同的方法
A99 A22 A33 A44
1260
例2 由1，2，3，4，5，6六个数字可以组成多少个 无重复且是6的倍数的五位数？
分析数字特征：6的倍数既是2的倍数又是3的倍数。其中3 的倍数又满足“各个数位上的数字之和是3的倍数”的特征。 把6分成4组，（3，3），（6），（1，5），（2，4），每 组的数字和都是3的倍数。因此可分成两类讨论；
4.根据相间区使用颜色的种类分类
例5如图， 6个扇形区域A、B、C、D、E、F，现给这6个区域着色， 要求同一区域涂同一种颜色，相邻的两个区域不得使用同一种颜色， 现有4种不同的颜色可有多少种方法？
四、面涂色问题
例9、从给定的六种不同颜色中选用若干种颜色，将一个正方体 的6个面涂色，每两个具有公共棱的面涂成不同的颜色，则不同 的涂色方案共有多少种？
排列组合中染色问题(精华版)
典例回顾:
例1. 4男3女坐成一排, 1).共有多少种排法? 2).某人必须在中间,有多少种排法? 3).某二人只能在两端,有多少种排法? 4).某人不在中间和两端,有多少种排法? 5).甲乙必相邻,有多少种排法? 6)甲乙不相邻,有多少种排法? 7).甲乙两人间必相隔一人,有多少种排法? 8)4男必相邻,有多少种排法? 9)4男相邻,3女也相邻,有多少种排法? 10)3女不相邻,有多少种排法? 11)4男不相邻,有多少种排法? 12)4男不在两端有多少种排法? 13)甲在乙的左边有多少种排法? 14)4男不等高,按高矮顺序排列,有多少种排法? 解题回顾:本题是处理排队问题的经典类型,从中体会不同的限制 条件下的求解方法.
D. 60 新疆 王新敞 奎屯
②
④
③ ①
①
③
④
②
①
③ ②
④
图一
若变为图二,图三呢?
图二
图三
(240种, 320种)
例5.(03年)如图，一个地区分为 5个行政区域， 现给地图着色， 要求相邻区域不得使用同一颜 色，现有4种颜色可供选择，则 不同的着色方法共有
72 种.（以数字作答）
练习2:用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格 内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以 反复使用，共有多少种不同的涂色方法
例6:用5种颜色给图7中的5个车站的候车牌（A、B、C、D、E） 染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不 同的染色方案？
涂 3 色 ： A 5 3 6 0 ； 涂 4 色 ： C 1 2 A 5 4 2 4 0 ； 涂 5 色 ： A 5 5 1 2 0 ， ∴ 共 有 6 0 2 4 0 1 2 0 4 2 0 种 图7
2、根据共用了多少种颜色讨论，分别计算出各种出各种 情形的种数，再用加法原理求出不同的涂色方法种数。
例7、（江苏卷）四种不同的颜色涂在如图所示的6个区域， 且相邻两个区域不能同色
分析：依题意只能选用4种颜色，要分四类：
（1）②与⑤同色、④与⑥同色，则有
A
4 4
（2）③与⑤同色、④与⑥同色，则有
A
4 4
练习2:(05全国卷Ⅱ)在由数字0，1，2，3，4，5所
组成的没有重复数字的四位数中，不能被5整除的数
共有
个.
简单的着色问题
例 3 如图一,要给①,②,③,④四块区域分别涂
Байду номын сангаас
上五种颜色中的某一种,允许同一种颜色使用多次,但
相邻区域必须涂不同颜色,则不同涂色方法种数为
( A)
A. 180
B. 160
C. 96
3.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻 区域同色与不同色入手，分别计算出两种情形的种数，再用加 法原理求出不同涂色方法总数。
例4.用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内， 每个区域涂一种颜色，相邻两个区域涂不同的颜色，如果颜色可 以反复使用，共有多少种不同的涂色方法？
（3）②与⑤同色、③与⑥同色，则有
A
4 4
（4）③与⑤同色、②与④同色，则有 A
4 4
（5）②与④同色、③与⑥同色，则有 A
4 4
所以根据加法原理得涂色方法总数为
例8、（全国高考题）如图所示，一个地区分为5个 行政区域，现给地图着色，要求相邻区域不得使用同一颜色， 现有4种颜色可供选择，则不同的着方法共有多少种？
分析：显然，至少需要3三种颜色，由于有多种不同情况， 仍应考虑利用加法原 理分类、乘法原理分步进行讨论
结束语
谢谢大家聆听！！！
24
第一类：由1，2，4，5，6作数码；首先从2，4，6中任选
一个作个位数字有 A
1 3
，然后其余四个数在其他数位上全排
A N AA 列有 4 ，所以 1 4
4
1
34
第二类：由1，2，3，4，5作数码。依上法有
N AA 1 4
2
24
故 N=N1+N2=120(个 )
【练习1】由1，2，3，4，5，6可以组成多少个 (1)无重复数字的2的倍数的的三位数? (2)无重复数字的能被3整除的三位数? (3)无重复数字的且是6的倍数的三位数？
涂 2 色 ： A 5 2 2 0 ； 涂 3 色 ： C 1 2 A 5 3 1 2 0 ； 图6
涂 4 色 ： A 5 4 1 2 0 ， ∴ 共 有 2 0 1 2 0 1 2 0 2 6 0 种
解后思:关于涂色问题,一般来说,以”某两个区域同色或 异色分类”或”以使用颜色的多少分类”是常见的两种 思考方式.
**练习1.(2006年江苏卷）今有2个红球、3个黄球、4个白球， 同色球不加以区分，将这9个球排成一列有 种不同的方法
A99 A22 A33 A44
1260
例2 由1，2，3，4，5，6六个数字可以组成多少个 无重复且是6的倍数的五位数？
分析数字特征：6的倍数既是2的倍数又是3的倍数。其中3 的倍数又满足“各个数位上的数字之和是3的倍数”的特征。 把6分成4组，（3，3），（6），（1，5），（2，4），每 组的数字和都是3的倍数。因此可分成两类讨论；
4.根据相间区使用颜色的种类分类
例5如图， 6个扇形区域A、B、C、D、E、F，现给这6个区域着色， 要求同一区域涂同一种颜色，相邻的两个区域不得使用同一种颜色， 现有4种不同的颜色可有多少种方法？
四、面涂色问题
例9、从给定的六种不同颜色中选用若干种颜色，将一个正方体 的6个面涂色，每两个具有公共棱的面涂成不同的颜色，则不同 的涂色方案共有多少种？
排列组合中染色问题(精华版)
典例回顾:
例1. 4男3女坐成一排, 1).共有多少种排法? 2).某人必须在中间,有多少种排法? 3).某二人只能在两端,有多少种排法? 4).某人不在中间和两端,有多少种排法? 5).甲乙必相邻,有多少种排法? 6)甲乙不相邻,有多少种排法? 7).甲乙两人间必相隔一人,有多少种排法? 8)4男必相邻,有多少种排法? 9)4男相邻,3女也相邻,有多少种排法? 10)3女不相邻,有多少种排法? 11)4男不相邻,有多少种排法? 12)4男不在两端有多少种排法? 13)甲在乙的左边有多少种排法? 14)4男不等高,按高矮顺序排列,有多少种排法? 解题回顾:本题是处理排队问题的经典类型,从中体会不同的限制 条件下的求解方法.
D. 60 新疆 王新敞 奎屯
②
④
③ ①
①
③
④
②
①
③ ②
④
图一
若变为图二,图三呢?
图二
图三
(240种, 320种)
例5.(03年)如图，一个地区分为 5个行政区域， 现给地图着色， 要求相邻区域不得使用同一颜 色，现有4种颜色可供选择，则 不同的着色方法共有
72 种.（以数字作答）
练习2:用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格 内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以 反复使用，共有多少种不同的涂色方法
例6:用5种颜色给图7中的5个车站的候车牌（A、B、C、D、E） 染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不 同的染色方案？
涂 3 色 ： A 5 3 6 0 ； 涂 4 色 ： C 1 2 A 5 4 2 4 0 ； 涂 5 色 ： A 5 5 1 2 0 ， ∴ 共 有 6 0 2 4 0 1 2 0 4 2 0 种 图7
2、根据共用了多少种颜色讨论，分别计算出各种出各种 情形的种数，再用加法原理求出不同的涂色方法种数。
例7、（江苏卷）四种不同的颜色涂在如图所示的6个区域， 且相邻两个区域不能同色
分析：依题意只能选用4种颜色，要分四类：
（1）②与⑤同色、④与⑥同色，则有
A
4 4
（2）③与⑤同色、④与⑥同色，则有
A
4 4
练习2:(05全国卷Ⅱ)在由数字0，1，2，3，4，5所
组成的没有重复数字的四位数中，不能被5整除的数
共有
个.
简单的着色问题
例 3 如图一,要给①,②,③,④四块区域分别涂
Байду номын сангаас
上五种颜色中的某一种,允许同一种颜色使用多次,但
相邻区域必须涂不同颜色,则不同涂色方法种数为
( A)
A. 180
B. 160
C. 96