数学选修2-3-涂色问题

高考数学轻松搞定排列组合难题二十一种方法

排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。

教学目标

1.进一步理解和应用分步计数原理和分类计数原理。

2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力

3.学会应用数学思想和方法解决排列组合问题.

复习巩固

1.分类计数原理(加法原理)

完成一件事，有n类办法，在第1类办法中有1m种不同的方法，在第2类办法中有2m种不同的方法，…，在第n类办法中有nm种不同的方法，那么完成这件事共有：

12nNmmmL

种不同的方法．

2.分步计数原理（乘法原理）

完成一件事，需要分成n个步骤，做第1步有1m种不同的方法，做第2步有2m种不同的方法，…，做第n步有nm种不同的方法，那么完成这件事共有：

12nNmmmL

种不同的方法．

3.分类计数原理分步计数原理区别

分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。

分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．

解决排列组合综合性问题的一般过程如下:

1.认真审题弄清要做什么事

2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。

3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.

4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略

一.特殊元素和特殊位置优先策略

例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数.

解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.

先排末位共有13C

1 / 3 涂色问题解题通法

定理1(直线型结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的直线型结构图涂色，则总的不同涂法有11nmnLmm种.

证明：由分步计数原理按序号逐个涂色即可。

定理2(星型结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的星型结构图涂色，则总的不同涂法有11nmnSmm种.

证明：由分步计数原理按序号逐个涂色即可。

定理3(环形结构)：用(2)mm种颜色给如图所示的由(3)nn个区域组成的环形结构图涂色，则总的不同涂法有111nnmnRmm种.

证明：1mmmnnnRRL(mnL中头尾不同的涂法数为mnR，头尾相同时,头尾看作一个区域，涂法数为1mnR)，即111nmmnnRRmm，

∴1111nnmmnnRmRm，求通项即可

或1221mmmnnnRmRmR

定理4(全连通型结构)：用()mmn种颜色给由n个区域组成的全连通型结构图(任何两个区域都连通，如图)涂色，则总的不同涂法有mnnmTA种.

证明：任何两个区域都连通，所以颜色各不相同。

方法应用

例1.将三种作物种植在如图所示的5块试验田里，每块种植一种作物且相邻的试验田不能种植一种作物，不同的种植方法有 种.(以数字作答)

答：结构抽象如右图，涂法数为：515132255333122148642LLC

例2.某城市在中心广场建造一个花圃，花圃分为6个部分(如图).现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有

种.(以数字作答)

2 / 3

答：结构抽象如右图，涂法数为：55354431311120R(先涂中间)

目录

考点一：基本计数原理 ........................................................................................................................... 2

题型一、分布加法原理 ......................................................................................................... 2

题型二、分布乘法原理 ......................................................................................................... 4

题型三、基本计数原理的综合运用 .................................................................................. 5

课后综合巩固练习 .............................................................................................................................................. 6

考点一：基本计数原理

加法原理

分类计数原理：做一件事，完成它有n类办法，在第一类办法中有1m种不同的方法，在第二类办法中有2m种方法，……，在第n类办法中有nm种不同的方法．那么完成这件事共有12nNmmm种不同的方法．又称加法原理．

乘法原理

分步计数原理：做一件事，完成它需要分成n个子步骤，做第一个步骤有1m种不同的方法，做第二个步骤有2m种不同方法，……，做第n个步骤有nm种不同的方法．那么完成这件事共有12nNmmm种不同的方法．又称乘法原理．

试卷第1页，总14页 第1讲排列与组合

A组

一、选择题

1．将6名报名参加运动会的同学分别安排到跳绳、接力，投篮三项比赛中（假设这些比赛都不设人数上限），每人只参加一项，则共有x种不同的方案，若每项比赛至少要安排一人时，则共有y种不同的方案，其中xy的值为（ ）

A．1269 B．1206 C．1719 D．756

【答案】A

【解析】

将6名报名参加运动会的同学分别安排到跳绳、接力，投篮三项比赛中（假设这些比赛都不设人数上限），每人只参加一项，则共有63729x种不同的方案，若每项比赛至少要安排一人时，则首先将6人分成3组，3组的人数为2,2,2或1,2,3或1,1,4，这样无序分组的方法有222114123642654653323290CCCCCCCCCAA种，然后将3个小组与3个比赛对应，又有33A种，则共有3390540yA种不同的方案，所以7295401269xy，故选择A，注意无序分组中均匀分组与非均匀分组的计数区别，否则会犯错.

2．某校周四下午第三、四两节是选修课时间,现有甲、乙、丙、丁四位教师可开课。已知甲、乙教师各自最多可以开设两节课,丙、丁教师各自最多可以开设一节课.现要求第三、四两节课中每节课恰有两位教师开课（不必考虑教师所开课的班级和内容）,则不同的开课方案共有（ ）种。

A、20 B、19 C、16 D、15

【答案】B

【解析】

不同的开课方案分四类：

第一类，只有甲、乙两人开课，他们每人开设两节，只有一种方案；

第二类，甲乙两人开课，同时，丙丁两个中恰有一人开课，这样的方案有1112228CAA种；

第三类，甲乙两人中只有一人开课，丙丁两人均开课，这样的方案有12224AA；

第四类，甲乙丙丁四人全部开课，第人一节，这样的方案共有22426CC种；