tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合






排列与组合

本节主要有:排列组合公式及应用;处理排列组合问题的常用方法:如插空法、捆绑法 等;可重复排列及圆排列公式等基本内容.

A 类例题
例 1 四个不同的小球放入编号 1、2、3、4、的四个盒中,则恰有一个空盒的放法有____ 种。 分析 排列组合中诸如把教师医生分到各

所学校;把不同的小球放入盒中等问题都可以归 类为分组问题,分组问题解题的原则是: “分组先分堆” . 解 把 4 个球分成“2、1、1”三堆,有
2 1 1 C4 C 2 C1 2 A2

种分法,把三堆球分别放入四个盒子的

3 任三个中,有 A4 种放法,由乘法原理,恰有一个空盒的放法共有

2 1 1 C4 C 2 C1 2 A2

3 · =144 种. A4

说明:本题也可以分类讨论求解,若 1 号盒空,2 号盒放二个球,3、4 号盒各放一个球有
2 2 =12 种放法;同理,若 1 号盒空,3 号盒放 2 个球,2、4 号盒各放一个球也是 12 种 C4 ? A2

放法;1 号盒空,4 号盒放 2 个球,2、3 号盒各放一个球同样是 12 种放法。所以,1 号盒空 共有 12×3 = 36 种放法。故满足题设的总放法种数为 4×36 = 144 种。 例 2 6 名同学排成一排。 (1)其中甲、乙两个必须排在一起的不同排法有______种.(1997 年全国高考题) (2)甲乙两人不能相邻的排法有______种. 分析 排列组合中,处理“在与不在” 、 “邻与不邻” 、 “接与不接”等问题时,常常利用捆 绑法或插空法.
5 解⑴把甲、乙两人看作 1 人,这样 6 个人可看成 5 个人,共有 A5 种排法,甲、乙两人 5 2 有 2 种顺序,故共有 A5 · A2 ? 240 种.
4 2 ⑵ 先排其他 4 名同学,有 A4 种,再把甲乙两人插入到 4 名同学的 5 个空挡中有 A5 种, 4 所以共有 A4 · A52 =480 种.

情景再现
1.3 名医生和 6 名护士被分配到 3 所学校为学生体检,每校分配 1 名医生和 2 名护士, 不同的分配方式共有 ( ) A.90 种 B.180 种 C.270 种 D.540 种 (1998 年全国高考题) 2.某校从 5 名优秀学生干部中选出 4 人分别参加“资源” 、 “生态”和“环保”三个夏令 营,要求每一个夏令营活动至少有选出的一人参加,且每人只参加一个夏令营活动,则不同 的参加方案有( )种

A.90 C.270

B.180 D .540

B 类例题
例 3 在正方体的 8 个顶点, 12 条棱的中点, 6 个面的中心及正方体的中心共 27 个点中, 共线的三点组的个数是 A 57 B 49 C 43 D 37 (1998 年全国数学联赛) 分析 正方体中,共线三点组的两个端点可能有三种情形:①两端点都是顶点;②两端点 都是面的中心;③两端点都是棱的中点,除此之外没有别的情形.
2 解 两端点都是顶点的共线组有 C8 ? 28 个,两端点都是面的中心的共线组有 3 个,两端

点都是棱的中点的共线组有

12 ? 3 ? 18 个。所以满足条件的共线组共有 49 个. 2

说明:分类讨论是解决较复杂的排列组合问题的常用思想,分类讨论的关键是找到合适的 分类标准,做到不重不漏。 例 4 某城市在中心广场建造一个花 圃,花圃分为 6 个部 分(如右图所示) ,现要栽种 4 种不同颜色 的花,每部分栽种 一种且相邻部分不能栽种同样颜色的花, 不同的栽种方法有______种. (2003 年江苏高考题) 分析 本题是近几年出现的排列组合问题中难度最大的问题之一。基本思想是运用分步记 数原理。
1 解 如图所示,把花坛视为一个圆环,先排区域 1,有 C 4 ? 4 种.由于 1 与其余 5 个位置

均相邻,故其余 5 个位置共有 3 种颜色可选.由任两个相邻位置不能同色,故必有 2 种颜色
1 1 各种两块地,第一种颜色只有一块地,有 C3 种方法,另两种颜色种 4 个位置,只有两种 ? C5 1 1 1 选择,故共有 C4 ? C3 ? C5 ? 2 ? 120 种.

例 5.在某次乒乓球单打比赛中,原计划每 两名选手恰比赛一场, 但有 3 名选手各比赛了 2 场之后就退出了,这 样,全部比赛只进行了 50 场。那么,上述 3 名选手之间的比赛场数是 A.0 B.1 C.2 D.3 (1999 全国联赛) 分析 3 名选手共比赛了 6 场, 设他们之间比赛了 x 场, 故只有这 3 名选手参加的比赛共 6-x 场.
2 解 设三名选手之间的比赛为 x 场,共有 n 名选手参赛,由题得 50 = Cn ?3 ? 6 ? x ,即

(n ? 3)(n ? 4) ? 44 ? x ,由于 0≤x≤3,经检验知,仅当 x= 1 时,n = 13 为正整数,故选 B. 2
说明 求解简单的二元一次不定方程时,可逐个代入检验是否满足题设. 例 6 四面体的顶点和棱的中点共 10 个点,取 4 个不共面的点,不同的取法有 ( ) A.150 种 B.147 种 C.144 种 D.141 种 分析 从所有的取法中减去共面的取法。其中 4 点共面的情形有三类:第一类,取出的 4
4 个点位于四面体的同一个面内有 4C6 种;第二类,取任一条棱上的 3 个点及该棱对棱中点,

共 6 种;第三类,由中位线构成的平行四边形,两组对边分别平行于四面体相对的两条棱, 有 3 种.
4 4 解 由上述分析知共有 C10 ? 4C6 ? 6 ? 3 ? 141 种.

说明 “排除法”是常用方法之一,其难点在于排除那些不合条件的组合。

情景再现
3.如图,点 p1,p2,?,p10 分别是四面体顶点或棱的中点。那么,在同一平面上的四 点组(p1,pi,pj,pk)(1 < i < j ≤10) 有_______个. (2002 年全国联赛)

4.四边形 ABCD 被其对角线分为 4 个不同的三角形△OAB、△OBC、△OCD、△OAD (O 为对角线的交点) ,若每个三角形用 4 种颜色的一种染色,那么出现相邻三角形均不同色 的四边形的概率是 ( ) A.

9 32

B.

19 64

C.

5 15

D.

21 64

5.某赛季足球比赛的计分规则是:胜一场,得 3 分;平一场,得 1 分;负一场,得 0 分, 一球队打完 15 场,积 33 分。若不考虑顺序,该队胜、负、平的情况共有 A.3 种 B.4 种 C.5 种 D.6 种 6.原有 m 个同学准备在暑假中开展通信活动,每人都必须给另外(m-1)个同学写一封信, 后来又有 n 个同学对这个活动感兴趣,若已知 n > 1,且由于增加了 n 个同学而又多写了 74 封信,则原有同学的人数 m = ________________.

C 类例题

例 7 8 个女孩和 25 个男孩围成一圈,任何两个女孩之间至少站两个男孩,问共有多少 种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的).(1990 年全国联赛) 分析 以 1 个女孩和 2 个男孩为一组,且使女孩恰好站在两个男孩中间,余下的 9 个男 孩和这 8 个组被看成是 17 个元素,显然这 17 个元素任意的圆排列是满足题意的.
9 解 先从 25 个男孩中选出 9 个男孩共有 C 25 种可能。其次,上述 17 个元素的圆排列 16 16 数为 p16 种. 再次,分在 8 个组内的 16 个男孩在 16 个位置上的排列是 p16 ,所以总的排列方

法数为:
9 16 16 C25 ?P 16 ? P 16 ?

25! 16! . 9!

链接 1.在 A={a1,a2,?,an}的 n 个元素中,每次取出 r 个元素排在一 个圆环上,叫做一个圆排列,圆排列有三个特点:第一,无头无尾;第 二,按同一方向旋转后仍是同一圆排列;第三,两个圆排列只有在元素 不同或者元素相同,但元素之间的顺序不同,才是不同的圆排列. 2.圆排列计数公式:从 n 个元素中取 r 个不同的元素进行圆排列, 圆排列数为
r pn . 特别地,当 r = n 时,圆排列数为(n-1)! r 3.项链问题:从 n 个相异的珠子中,每次取出 r 颗穿成一个项链, 因其正反相对的两个圆排列在穿成一个项链的完全相同,故项链数为 r pn . 2r

例 8 试求从集合 A={1,2,?,n}到集合 B={1,2,?,m}的映射的个数. 分析 在两个集合之间建立映射本质上是给集合 A 中的元素分步找象. 解 给 A 中元素分别找象,元素 1 有 m 种找法,元素 2 有 m 种找法,?,元素 n 有 m 种找法,故从 A 到 B 的映射的个数为 mn. 链接:允许元素重复出现的排列,叫做可重复排列,在 m 个不同的元素里,每次取出 n 个 元素,元素可重复出现,按一定的次序排成一排的排列数为 mn. 例 9 整数 1,2,?,n 的排列满足:每个数或者大于它之前的所有数,或者小于它之前 的所有数. 试问有多少个这样的排列?(第 21 届加拿大中学生数学竞赛) 分析 由特殊到一般,找出递推关系式. 解 记所求的排列的个数是 an. 显然,a1 = 1. 对于 n≥2,考虑最大的数 n,如果 n 排在第 i 位,则它之后的(n –i)个数排序完全确定, 即只能是 n – i,n – i – 1,?,1;而它之前的(i-1)个数有 ai-1 种排法,考虑到 n 的所有不同的 位置,由加法原理知 an = 1 + a1 + a2 + ? + an-1, 于是,an-1 = 1 + a1 + a2 + ? + an-2. 有 an = 2an-1,又 a1 = 1

故 an = 2n-1.

情景再现
7.某城市有 7 条南北向的街,5 条东西向的街,如果从城市的 O 点走向 A 点,最短的走 法有多少种? 8.用 6 个白珠、8 个黑珠、一个红珠串成一串,问共有多少种不同的串法? 9.有数学、物理、文学 3 个课外活动小组,6 个同学报名,每人限报一组,一共有多少 种报名的方法?

习题 17
A 1.8 次射击,命中 3 次,其中恰有 2 次连续命中的情形共有________种。 (1998 年湖南 联赛) 2.2 名医生和 4 名护士被分配到 2 所学校为学生体检,每校分配 10 名医生和 2 名护士, 不同的分配方法共有 ( ) A.6 种 B.12 种 C.18 种 D.24 种 (1998 年全国高考题) 3.如图,一个地区分为 5 个行政区域,现给地图着色, 要求相邻区域不得使用同一颜色, 现有 4 种颜色可供选择, 则 不同的着色方法共有_________种。 4.正六边形的中心和顶点共 7 个点,以其中 3 个点为顶 点的三角形有_______个。 5.n 个后乒乓球运动员(n≥4),每两个人都可以组成一 对双打选手,从中选出两对的选法有 ( )
4 A.3 C n 种 4 C.3 Cn ?1 种 4 B.6 C n 种 4 3 D.(6 C n +3 C n )种

6.已知两个实数集合 A={a1,a2,?,a100}与 B={b1,b2,?,b50},若从 A 到 B 的映射 f 使得 B 中每个元素都有原像,且 f(a1) ≤ f(a2) ≤ ?≤ f(a100),则这样的映射共有( ) 个
50 A. C100 48 B. C 99 49 C. C120 49 D. C 99

B 7.在一个正六边形的六个区域种观赏植物,如图,要求同一块中种同一植物,相邻的两 块种不同的植物,现有 4 种不同的植物可供选择,则有_______种栽种方案.

8.在 1,2,3,4,5 的排列 a1,a2,a3,a4,a5 中,满足条件 a1 < a2,a2 > a3,a3 < a4, a4 > a5 的排列个数是 ( ) A.8 B.10 C.14 D.16
5 9. “渐升数”是指每个数字比其左边的数字大的正整数,如 34689,已知有 C9 ? 126 个五位

“渐升数” ,若把这些数按从小到大的顺序排列,则第 100 个数是______________。 10. 把 1996 个不加区别的小球放在 10 个不同的盒子里, 使得第 i 个盒子中至少有 i 个球 (i=1,2,?,10) ,问不同放法的总数是多少? C 11.用六种不同颜色中的几种染一个正方体各面,要求相邻两面不同色,问有多少种不 同染色法?(两个染色正方形,如能通过转动、翻身使二者各面颜色对应相等,则认为是相 同染色法) (1996 年全国联赛) 12.4 对夫妇去看电影,8 人生成一排,若每位女性的邻座只能是丈夫或另外的女性,共 有多少种坐法? 本节“情景再现”解答:
2 2 1.A 3 3 ·C 6 ·C 4 =540 种
2 1 1 C4 C 2 C1 2 A2

2.先选出 4 人有 C 4 5 种选法,把 4 人分成“2,1,1”三堆,有
2 1 1 C4 C 2 C1 2 A2

种分法,共有

4 C5 ×

×A 3 3 =180 种。

3.首先,在每个侧面上除 P1 点外尚有五个点,其中任意三点添加 P1 后组成的 4 点组都
3 在同一平面,这样的三点组有 C 3 5 个,三个侧面共有 3 C 5 个。其次,含 P1 的每条棱上的三点

组添加底面与它异面的那条棱上的中点组成的四点也在一个平面上,这样的四点组有 3 个, 故共有 3 C 3 5 +3=33 个。

4.分别以 S1、S2、S3、S4 依次记 △OAB、△OBC、△OCD、△ODA,显然,若不考虑相邻三角形不同色的要求,则共 4 有 4 =256 种涂法。

下面先对 S1 和 S3 涂色 i)S1 和 S3 同色,它们共有 4 种选择, S2 和 S4 各有 3 种选择,所以此时共有 4×3×3=36 种不同涂法。

对每一对选择,

ii)S1 和 S3 不同色,它们共有 C 2 4 =12 种选择,对每一种选择,S2 和 S4 各有 3 种选择, 所以此时共有 12×2×2=48 种不同涂法。 所以相邻三角形均不同色的四边形出现的概率为
36 ? 48 21 ? 256 64

5.设胜 x 场,平 y 场,则负(15―x―y)场,得 3x+y=33,又 y=33-3x≥0 ∴x≤11,且 x+y≤15,共有 ?
? x ? 11 ? x ? 10 ? x ? 9 ;? ;? 三种情形。 ?y ? 0 ?y ? 3 ?y ? 6

2 6.由题得 C 2 m ? n -C m =74 即

(m ? n)(m ? n ? 1) m(m ? 1) - =74,即 n(2m+n-1)=148 2 2

=22×37,由于 n 与 2m+n-1 有不同的奇偶性,故只能解得 n=4,2m+3=37 有 m=17 整数解。 7.每条东西向的街被分成 6 段,每段不妨都用相同的 a 表示,共有 6 个 a。每条南北向 的街被分成 4 段,用 4 个 b 表示,含有 6 个 a 和 4 个 b 的一种全排列,对应于从 0 到 A 的一 种走法。例如排列 aaabaabab,对应于上图中箭头所示的走法,故走法有
10! =210 种。 6!4!

8.这是一个圆排列问题,如固定红珠,则为线排列,故除红珠外其余的 14 个珠子共有 N1=
P77 P33 P44
14 P14

P66 P88

=3003 种串法,14 个珠子关于红珠对称或不对称有两种情形:①对称共有 N2=

=35 种;②不对称有 N3=N1-N2=2968 种,又同色珠子换位后的相同的串法是重复

的串法,因此关于红球不对称的串法有 N4=

1 N3=1484 种,所以共有 N=N2+N4=1519 种 2

不同串法。 9.可重复排列,共有 36=729 种报名方法。 习题解答 1.把两次连续命中与一次命中的情形看成 2 个元素插入可知共有 30 种。或用穷举法把 满足条件的情形一一列举出来 2.B.分组先分堆 3.先排 1 区,有 4 种方法,再排 2 区,有 3 种方法,如果 3、5 两区同色,则 4 区有 2 种方法,否则 4 区只有一种方法。另外 3、5 两区本身还有两种选择,故共有 4×3×(1+2) ×2=72 种。 4.用“排除法” ,从 7 个点中任取三点有 C 3 7 种取法,其中 3 个点在一直线上的有 3 个, 故共有 C 3 7 -3=32 个。 5.n 个运动员两两配对有
n(n ? 1) 4 对,从中选出两对共有 C 2 n ( n ?1) =3C n ?1 。 2 2

6.不防设 b1<b2<?<b50,把 A 中元素 a1,a2,?,a100 按顺序分为非零的 50 组,定义 映射 f:A→B,使第 i 组的元素在 f 之下的像都是 bi(i=1,2,?,50) ,易知这样的 f 满足 题设,每个这样的分组都一一对应满足条件的映射。于是,满足条件的映射 f 的个数与 A 按下
49 49 标顺序分为 50 组的分法数相等,而 A 的分法数为 C 99 ,则这样的映射共有 C 99 个。

7.考虑 A、C、E 种同一种植物,此时共有 4×3×3×3=108 种, 考虑 A、C、E 种二种植物,此时共有 3×4×3×3×2×2=432 种方法,考虑 A、C、E 种三种植物,共有 P 3 4 ×2×2×2=192 种方法。故总计有 108+432+192=732 种方法。

8.由 a1<a2,a2>a3,a3>a4,a4>a5 可知,要么 a2=5,要么 a4=5(a1、a3、a5 不可能 是最大者) ,且 a2≥3,a4≥3,a3≤3。①若 a2=5,则 a4=4 或 3。当 a4=4 时,有 3!=6 种,当 a4=3 时,有 2!=2 种,这时共有 6+2=8 种;②同理当 a4=5 时,也有 8 种,故共 有 16 种。 9.前 3 位数是 123 的五位“渐升数”共有 5+4+3+2+1=15 个数。同理,前 3 位数 分别是 124,125,126,127 的五位“渐升数”分别有 10,6,3,1 个。即前两位数是 12 的五位渐升数有 35 个,类似可得前两位数是 13,14,15,16 的五位“渐升数”分别有 20 个,10 个,4 个,1 个。从而首位是 1 的五位“渐升数”共有 35+20+10+4+1=70 个。 同理,前两位数是 23 的五位“渐升数”共有 10+6+3+1=20 个。前 2 位是 24 的五位“渐

升数”共有 6+3+1=10 个。所以第 100 个“渐升数”是 24789。 10.先在第 i 盒里放入 i 个球(i=1,2,?,10)这时共放了 1+2+3+?+10=55 个
9 球,还余下 1941 个球,转化为把 1941 个球放入 10 个盒子中(有的盒中不放球) ,有 C 1950 种

放法。 11.分四种情形讨论:1°有 3 6 种颜色,将一种颜色染下底,则上底有 5 种染法,按 圆排列,其余 4 个侧面有 3!种染法,共有 5×3!=30 种;2°用 5 种颜色,选 5 种颜色有 C5 6 种方法,再选一种染上下底,有 5 种,固定一种颜色朝东,朝西一面有 3 种选法,共有
4 2 1 C5 6 ×C 5 ×3 = 90 种;3°用 4 种颜色,选 4 色,再选其中两种各染一对对面有 C 6 ×C 4 =90

3 种。4°用 3 种色,选 3 色有 C 3 6 种,每种染相对两面,染出的都是同一种,故共有 C 6 =20

种。故共有 30+90+90+20=230 种。 12.先把女性排定,有 4!种方法,女性与女性之间若坐男性(包括这些女性的丈夫)必 不少于两个。同样,在男性与男性之间坐着的女性也必不少于两个,把座位连在一起的女性 也必不少于两个,把座位连在一起的女性视为一组,则 4 位女性的分组有 4,3+1,2+2,2 +1+1,1+1+1+1 这 5 种,孤立坐着的女性必须在这一排座位的两端,所以 1+1+1+1 方案不合要求,女性分成 2+1+1 时,两端必须坐着女性,这时男性只能分成 2+2,即女男 男女女男男女,男性的排法只有 1 种,女性分种 2+2 时,有 4 类: 女女男男男男女女 , 女女男男男女女男 或 男女女男男男女女 , 女女男男女女男男 或 男男女女男男女女 , 男女女男男女女男,男性的排法分别有 2,1,1,1 种,女性分为 3+1 时,有三类:女女女男男男男女或女男男男男女女女,男男女女女男男女 或女男男男女女女男,男性的排法分别有 2,1,1 种,女性 4 人连排时,有三类,女女女女 男男男男或男女女女女男男男,男男女女女女男男,男性的排法分别有 3! ,2! ,2!种,于是 排法总数为 4! (1+2+2×1+2×1+1+2×2+2×1+2×1+2×3!+2×2!×2! )=816 种。

w。w-w*k&s%5¥u


推荐相关:

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合_学科竞赛_高中教育_教育...显然这 17 个元素任意的圆排列是满足题意的. 9 解 先从 25 个男孩中选出...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com