10.2排列染色问题.ppt

课题课题:排列排列(典型例题典型例题)(第二课时第二课时)导航：感受导航：感受“整除整除”，“排队排队”，“染色染色”问题的处问题的处理技法理技法典例回顾典例回顾:例例1.4男男3女坐成一排女坐成一排,1).共有多少种排法共有多少种排法?2).某人必须在中间某人必须在中间,有多少种排法有多少种排法?3).某二人只能在两端某二人只能在两端,有多少种排法有多少种排法?4).某人不在中间和两端某人不在中间和两端,有多少种排法有多少种排法?5).甲乙必相邻甲乙必相邻,有多少种排法有多少种排法?6)甲乙不相邻甲乙不相邻,有多少种排法有多少种排法?7).甲乙两人间必相隔一人甲乙两人间必相隔一人,有多少种排法有多少种排法?8)4男必相邻男必相邻,有多少种排法有多少种排法?9)4男相邻男相邻,3女也相邻女也相邻,有多少种排有多少种排法法?10)3女不相邻女不相邻,有多少种排法有多少种排法?11)4男不相邻男不相邻,有多少种排法有多少种排法?12)4男不在两端有多少种排法男不在两端有多少种排法?13)甲在乙的左边有多少种排法甲在乙的左边有多少种排法?14)4男不等高男不等高,按高矮顺序排列按高矮顺序排列,有多少种排法有多少种排法?解题回顾解题回顾:本题是处理排队问题的经典类型本题是处理排队问题的经典类型,从中体会不同的限制从中体会不同的限制条件下的求解方法条件下的求解方法.*练习练习1.(2006年江苏卷）今有年江苏卷）今有2个红球、个红球、3个黄球、个黄球、4个白球，个白球，同色球不加以区分，将这同色球不加以区分，将这9个球排成一列有个球排成一列有种不同的方法种不同的方法 例例2 由由1，2，3，4，5，6六个数字可以组成多少个六个数字可以组成多少个无重复且是无重复且是6的倍数的五位数？的倍数的五位数？分析数字特征：分析数字特征：6的倍数既是的倍数既是2的倍数又是的倍数又是3的倍数。其中的倍数。其中3的倍数又满足的倍数又满足“各个数位上的数字之和是各个数位上的数字之和是3的倍数的倍数”的特征。的特征。把把6分成分成4组，（组，（3，3），（），（6），（），（1，5），（），（2，4），每），每组的数字和都是组的数字和都是3的倍数。因此可分成两类讨论；的倍数。因此可分成两类讨论；第一类：由第一类：由1，2，4，5，6作数码；首先从作数码；首先从2，4，6中任选中任选一个作个位数字有一个作个位数字有 ，然后其余四个数在其他数位上全排，然后其余四个数在其他数位上全排列有列有 ，所以，所以第二类：由第二类：由1，2，3，4，5作数码。依上法有作数码。依上法有【练习练习1】由由1，2，3，4，5，6可以组成多少个可以组成多少个(1)无重复数字的无重复数字的2的倍数的的三位数的倍数的的三位数?(2)无重复数无重复数字字的的能被能被3整除的三位数整除的三位数?(3)无重复数无重复数字字的的且是且是6的倍数的三位数？的倍数的三位数？练习2:(05全国卷全国卷)在由数字0，1，2，3，4，5所组成的没有重复数字的四位数中，不能被5整除的数共有 个.(240种种,320种种)A简单的着色问题简单的着色问题例5.(03年)如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种.（以数字作答）72练习1.(03年)某城市在中心广场建造一个花圃，花圃分为6个部分（如图）.现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有 。（以数字作答）120练习练习2:用红、黄、蓝、白、黑用红、黄、蓝、白、黑5种颜色涂在种颜色涂在“田田”字形的字形的4个小方格个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法反复使用，共有多少种不同的涂色方法 图6解后思解后思:关于涂色问题关于涂色问题,一般来说一般来说,以以”某两个区域同色某两个区域同色或异色分类或异色分类”或或”以使用颜色的多少分类以使用颜色的多少分类”是常见的两是常见的两种思考方式种思考方式.例例6:用用5种颜色给图种颜色给图7中的中的5个车站的候车牌（个车站的候车牌（A、B、C、D、E）染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不同的染色方案？同的染色方案？图7作业作业:1.用用1、2、3、4、5、6、7、8组成没有重复数字的八位数，组成没有重复数字的八位数，要求要求1和和2相邻，相邻，3与与4相邻，相邻，5与与6相邻，而相邻，而7与与8不相邻，这样不相邻，这样的八位数共有的八位数共有 个个.2.用用0,1,2,3,4,5,6组成的无重数数字的四位数组成的无重数数字的四位数,能被能被3整除的有整除的有多少个多少个?3.7名师生站成一排表演节目名师生站成一排表演节目,其中老师其中老师1人人,男生男生4人人,女生女生2人人,在下列情况下在下列情况下,各有多少种不同的各有多少种不同的站法？站法？(1)两名女生相邻而站两名女生相邻而站;(2)4名男生互不相邻名男生互不相邻;(3)4名男生身高不等名男生身高不等,按从高到低一种顺序站按从高到低一种顺序站;(4)老师不站中间老师不站中间,女生不站两端女生不站两端.4.如如图图，一，一环环形花形花坛坛分成分成A、B、C、D四四块块现现有有4种不同的花供种不同的花供选选种，要求在每种，要求在每块块里种里种1种花，且相种花，且相邻邻的的2块块种不同的花，种不同的花，则则不同的种法不同的种法总总数数为为 A96 B84 C60 D485.5名男生、名男生、2名女生站成一排照像：名女生站成一排照像：（1）两名女生要在两端，有多少种不同的站法？）两名女生要在两端，有多少种不同的站法？（2）两名女生都不站在两端，有多少不同的站法？）两名女生都不站在两端，有多少不同的站法？（3）两名女生要相邻，有多少种不同的站法？）两名女生要相邻，有多少种不同的站法？（4）两名女生不相邻，有多少种不同的站法？）两名女生不相邻，有多少种不同的站法？（5）女生甲要在女生乙的右方，有多少种不同的站法？）女生甲要在女生乙的右方，有多少种不同的站法？（6）女生甲不在左端，女生乙不在右端，有多少种不同的站法？）女生甲不在左端，女生乙不在右端，有多少种不同的站法？6从从6名运动员中选出名运动员中选出4人参加人参加4400m接力赛，如果甲、乙两人接力赛，如果甲、乙两人都不能跑第一棒，那么共有多少种不同的参赛方案？都不能跑第一棒，那么共有多少种不同的参赛方案？7由由2，3，5，7组成没有重复数字的组成没有重复数字的4位数位数（1）求这些数字的和；（）求这些数字的和；（2）按从小到大顺序排列，）按从小到大顺序排列，5372是是第几个数？第几个数？8由数字由数字0，1，2，3，4，5组成没有重复数字的六位数，组成没有重复数字的六位数，其中个位数字小于十位数字的数共有多少个其中个位数字小于十位数字的数共有多少个 97个人按下列要求站成一排，分别有多少种不同的站法？个人按下列要求站成一排，分别有多少种不同的站法？（1）甲不站在左端；）甲不站在左端；（2）甲、乙都不能站在两端；）甲、乙都不能站在两端；（3）甲、乙不相邻；）甲、乙不相邻；（4）甲、乙之间相隔二人）甲、乙之间相隔二人