排列组合中染色问题

1、.1 排列组合典型例题排列组合典型例题 排队排队”，“染色染色”问题问题 .2 典例回顾典例回顾: 例例1. 4男男3女坐成一排女坐成一排, 1).共有多少种排法共有多少种排法? 2).某人必须在中间某人必须在中间,有多少种排法有多少种排法? 3).某二人只能在两端某二人只能在两端,有多少种排法有多少种排法? 4).某人不在中间和两端某人不在中间和两端,有多少种排法有多少种排法? 5).甲乙必相邻甲乙必相邻,有多少种排法有多少种排法? 6)甲乙不相邻甲乙不相邻,有多少种排法有多少种排法? 7).甲乙两人间必相隔一人甲乙两人间必相隔一人,有多少种排法有多少种排法? 8)4男必相邻男必相邻,有多少

2、种排法有多少种排法? 9)4男相邻男相邻,3女也相邻女也相邻,有多少种排法有多少种排法? 10)3女不相邻女不相邻,有多少种排法有多少种排法? 11)4男不相邻男不相邻,有多少种排法有多少种排法? 12)4男不在两端有多少种排法男不在两端有多少种排法? 13)甲在乙的左边有多少种排法甲在乙的左边有多少种排法? 14)4男不等高男不等高,按高矮顺序排列按高矮顺序排列,有多少种排法有多少种排法? 解题回顾解题回顾:本题是处理排队问题的经典类型本题是处理排队问题的经典类型,从中体会不同的限制从中体会不同的限制 条件下的求解方法条件下的求解方法. .3 *练习练习1.(2006年江苏卷）今有年江苏卷）

3、今有2个红球、个红球、3个黄球、个黄球、4个白球，个白球， 同色球不加以区分，将这同色球不加以区分，将这9个球排成一列有个球排成一列有种不同的方法种不同的方法 9 9 234 234 1260 A A A A .4 例例2 由由1，2，3，4，5，6六个数字可以组成多少个六个数字可以组成多少个 无重复且是无重复且是6的倍数的五位数？的倍数的五位数？ 分析数字特征：分析数字特征：6的倍数既是的倍数既是2的倍数又是的倍数又是3的倍数。其中的倍数。其中3 的倍数又满足的倍数又满足“各个数位上的数字之和是各个数位上的数字之和是3的倍数的倍数”的特征。的特征。 把把6分成分成4组，（组，（3，3），（）

4、，（6），（），（1，5），（），（2，4），每），每 组的数字和都是组的数字和都是3的倍数。因此可分成两类讨论；的倍数。因此可分成两类讨论； 第一类：由第一类：由1，2，4，5，6作数码；首先从作数码；首先从2，4，6中任选中任选 一个作个位数字有一个作个位数字有 ，然后其余四个数在其他数位上全排，然后其余四个数在其他数位上全排 列有列有 ，所以，所以 第二类：由第二类：由1，2，3，4，5作数码。依上法有作数码。依上法有 1 3A 4 4A 14 341NA A 14 242NA A 12 =+=120() N N 故个 N .5 【练习练习1】由由1，2，3，4，5，6可以组成多少个可以

5、组成多少个 (1)无重复数字的无重复数字的2的倍数的的三位数的倍数的的三位数? (2)无重复数字的无重复数字的能被能被3整除的三位数整除的三位数? (3)无重复数字的无重复数字的且是且是6的倍数的三位数？的倍数的三位数？ 练习2:(05全国卷全国卷)在由数字0，1，2，3，4，5所 组成的没有重复数字的四位数中，不能被5整除的数 共有 个. .6 (240种种, 320种种) A 简单的着色问题简单的着色问题 .7 例4:用n种不同颜色为下列两块广告牌着色(如图甲、乙所示）， 要求在a,b,c,d四个区域中相邻（有公共边界）的区域不用同 一颜色。 （1）若n=6，为甲着色时有多少种不同方法？

6、（2）若为乙着色有120种方法，求n. a b c d 甲 a b c d 乙乙 （1）480 （2）n=5 .8 例5.(03年)如图，一个地区分为 5个行政区域， 现给地图着色， 要求相邻区域不得使用同一颜 色，现有4种颜色可供选择，则 不同的着色方法共有 种.（以数字作答） 72 .9 练习练习2:用红、黄、蓝、白、黑用红、黄、蓝、白、黑5种颜色涂在种颜色涂在“田田”字形的字形的4个小方格个小方格 内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以 反复使用，共有多少种不同的涂色方法反复使用，共有多少种不同的涂色方法 图6 涂

7、 2 色： 2 5 20A ；涂 3 色： 13 25 120C A ； 涂 4 色： 4 5 120A ，共有20120 120260种 解后思解后思:关于涂色问题关于涂色问题,一般来说一般来说,以以”某两个区域同色或某两个区域同色或 异色分类异色分类”或或”以使用颜色的多少分类以使用颜色的多少分类”是常见的两种是常见的两种 思考方式思考方式. .10 例例6:用用5种颜色给图种颜色给图7中的中的5个车站的候车牌（个车站的候车牌（A、B、C、D、E） 染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不 同的染色方案？同的染色方案？ 图

8、7 涂 3 色： 3 5 60A ；涂 4 色： 14 25 240C A ； 涂 5 色： 5 5 120A ，共有60240120420种 .11 2、根据共用了多少种颜色讨论，分别计算出各种出各种 情形的种数，再用加法原理求出不同的涂色方法种数。 例7、（江苏卷）四种不同的颜色涂在如图所示的6个区域， 且相邻两个区域不能同色 分析：依题意只能选用4种颜色，要分四类： （1）与同色、与同色，则有 4 4 A 4 4 A 4 4 A（2）与同色、与同色，则有 （3）与同色、与同色，则有 （5）与同色、与同色，则有 4 4 A （4）与同色、与同色，则有 4 4 A 所以根据加法原理得涂色方法

9、总数为 .12 例8、（全国高考题）如图所示，一个地区分为5个 行政区域，现给地图着色，要求相邻区域不得使用同一颜色， 现有4种颜色可供选择，则不同的着方法共有多少种？ 分析：依题意至少要用3种颜色 .13 3.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻 区域同色与不同色入手，分别计算出两种情形的种数，再用加 法原理求出不同涂色方法总数。 例4.用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内， 每个区域涂一种颜色，相邻两个区域涂不同的颜色，如果颜色可 以反复使用，共有多少种不同的涂色方法？ .14 4.根据相间区使用颜色的种类分类 例5如图， 6个扇形区域A、B、C、D、E、F，现给这6个区域着色， 要求同一区域涂同一种颜色，相邻的两个区域不得使用同一种颜色， 现有4种不同的颜色可有多少种方法？ .15 .16 .17 .18 .19 .20 四、面涂色问题四、面涂色问题 例9、从给定的六种不同颜色中选用若干种颜色，将一个正方体从给定的六种不同颜色中选用若干种颜色