当前位置:首页 >> 数学 >>

高一数学竞赛讲稿(第9次)


济南雨露高一数学竞赛班数学教学案(第 9 次)
排列与组合
竞赛热点
1.分类计数原理 完成一件事情,有 m 类方法,而每一类方法中分别有 n1 , n2 ,?, nm 种方法,不论采用这些方法中的任 何一种,都能独立地完成这件事情,那么完成这件事情共有 N ? n1 ? n2 ? ? ? nm 种方法。 2.分步计数原理 完成一件事情,有 m 个步骤,而每一个步骤分别有 n1 , n2 ,?, nm 种方法,那么完成这件事情共有

N ? n1 · n2 ·…· nm 种方法。
3.排列 从 n 个不同的元素中,任取 m( m ? n) 个不同的元素,按照一定的顺序排成一列,叫做从 n 个不同的元 素中取出 m 个元素的一个排列。 4.排列数公式
m An ? n(n ? 1)(n ? 2) ? (n ? m ? 1) ?

n! (m ? n). (n ? m)!

5.组合 从 n 个不同的元素中,任取 m( m ? n) 个不同的元素并成一组,叫做从 n 个不同元素中取 m 个元素的 一个组合。 6.组合数公式及其性质
m Cn ?

n! n(n ? 1)(n ? 2) ? (n ? m ? 1) ? (m ? n). m!(n ? m)! m(m ? 1)(m ? 2) ?3 ? 2 ? 1

m n?m m m m ?1 Cn ? Cn , Cn (m ? n). ?1 ? C n ? C n

7.有重复的排列 从 n 个不同元素中取出 m 个元素,元素允许重复,按照一定的顺序排成一列,这种排列称为可重复排 列,其排列数为 n m . 8.不尽相异的元素的全排列 设 n 个元素可分为 k 组,每一组中的元素是相同的,不同组中的元素是不同的,其中第 i 组中元素个 数为 ni 个( i ? 1,2,?, k ) , n1 ? n2 ? ? ? nk ? n ,这 n 个元素的全排列叫做不尽相异的元素的全排列,其 排列数为

n! . n1!n2 !? nk !

9.圆排列 从 n 个元素中任取 m 个不同的元素,仅按元素之间的相对位置而不分首尾排成一圈,这种排列称为 n
1

m 个不同元素的 n 圆排列,其排列数为 C n (m ? 1)!,特别地, n 个不同元素的圆排列数为 (n ? 1)!.

10.重复组合 从 n 个不同元素中任取 m 个允许元素重复出现的组合叫做 n 个不同元素的 m 个可重复组合, 其组合数
m 为 Fnm ? C n ? m ?1 ( m, n ? N , 且允许m ? n).

11.多组组合 把 n 个不同的元素分成 k 组,第 i 组有 ni 个元素( i ? 1,2,?, k ) ,且 n1 ? n2 ? ? ? nk ? n ,分组方法 的总数为

n! . n1!n2 !? nk !

12.处理常见的排列组合问题的策略 (1)特殊元素优先安排; (2)合理分类与准确分步; (3)先选后排; (4)相邻问题捆绑处理; (5)不相邻问题插空解决; (6)先整体后局部的原则; (7)构造模型处理问题。

解题示例
例 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 · A4 =144 种.

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

法;同理,若 1 号盒空,3 号盒放 2 个球,2、4 号盒各放一个球也是 12 种放法;1 号盒空,4 号盒放 2 个 球,2、3 号盒各放一个球同样是 12 种放法。所以,1 号盒空共有 12×3 = 36 种放法。故满足题设的总放 法种数为 4×36 = 144 种。 例 2 在正方体的 8 个顶点,12 条棱的中点,6 个面的中心及正方体的中心共 27 个点中,共线的三点 组的个数是 _________(1998 年全国数学联赛) 分析 正方体中,共线三点组的两个端点可能有三种情形:①两端点都是顶点;②两端点都是面的中心; ③两端点都是棱的中点,除此之外没有别的情形.
2 解 两端点都是顶点的共线组有 C 8 ? 28 个,两端点都是面的中心的共线组有 3 个,两端点都是棱的中点的

12 ? 3 ? 18 个。所以满足条件的共线组共有 49 个. 2 说明:分类讨论是解决较复杂的排列组合问题的常用思想,分类讨论的关键是找到合适的分类标准,做到 不重不漏。
共线组有
2

例 3 某城市在中心广场建造一个花圃, 花圃分为 6 个部分 (如右图所示) , 现要栽种 4 种不同颜色的花, 每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有___种. 分析 本题是近几年出现的排列组合问题中难度最大的问题之一。 基本思想是运用分步记数原理。
1 解 如图所示 ,把花坛视为一个圆环,先排区域 1,有 C 4 ? 4 种.由于 1 与其

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

例 4 四面体的顶点和棱的中点共 10 个点, 取 4 个不共面的点, 不同的取法 有____种. 分析 从所有的取法中减去共面的取法。其中 4 点共面的情形有三类:第一类,
4 取出的 4 个点位于四面体的同一个面内有 4C 6 种;第二类,取任一条棱上的 3 个点及该棱对棱中点,共 6

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

说明 “排除法”是常用方法之一,其难点在于排除那些不合条件的组合。 例 5 整数 1,2,…,n 的排列满足:每个数或者大于它之前的所有数,或者小于它之前的所有数. 试 问有多少个这样的排列? 分析 由特殊到一般,找出递推关系式. 解 记所求的排列的个数是 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. 例 6 设三位数为 n ? abc ,若以 a, b, c 为三条边的长可以构成一个等腰(含等边)三角形,则这样 的三位数 n 有______个。 思路分析:从等边三角形和等腰(非等边)三角形入手,分类计数,加以解决。 解:以 a, b, c 为三条边的长可构成三角形,显然 a, b, c 不能为零,即 a, b, c ? {1,2,3,?,9}. (1)若构成等边三角形,则 a ? b ? c 可取 {1,2,3,?,9} 中任何一个值,所以这样的三位数的个数为
1 n1 ? C9 ? 9.

(2)若构成非等边的等腰三角形,设这样的三角形个数为 n2 ,且等腰三角形三边长为 a1 , b1 ? c1 .
2 当 a1 ? b1 ? c1 时,即腰大于底边时,此时三角形由数对 ( a1 , b1 ) 唯一确定,有 C9 个;

3

2 当 a1 ? b1 ? c1 时,即腰小于底边时,这时数对 ( a1 , b1 ) 有 C9 个,但必须 b1 ? a1 ? 2b1 才能构成三角形,

而不能构成三角形的数对 ( a1 , b1 ) 是

a1
b1
共 20 种情况。

9

8

7

6

5

4

3 1

2 1

1,2,3,4

1,2,3,4

1,2,3

1,2,3

1,2

1,2

2 故此时非等边的等腰三角形只有 C9 ? 20 个。 2 2 同时,每个数对 ( a1 , b1 ) 可形成 C3 个三位数 abc ,所以 n2 ? C3 (C92 ? C92 ? 20) ? 156.

故 n ? n1 ? n2 ? 165 ,选 C。 点评:此题综合运用了枚举法和组合的基础知识,在计数时,必须根据问题的特点确定一个分类或分 步的标准,标准不能重复和遗漏,同时枚举法直观易懂,是理解排列组合问题的好方法。 例 7 在一个正六边形的六个区域栽种观察植物(如图) ,要求同一块中种同一种植物,相邻的两块种 不同的植物,现有 4 种不同的植物可供选择,则有几种栽种方案? 思路分析:这是一个环排列,我们给图中六块区块依次标上字母 A,B,C,D,E,F。 按 A,C,E 所种植物分类解决。 解:按间隔三块 A, C , E 种植植物的种数,分以下三类: (1)若 A, C , E 种同一种植物,有 4 种种法。当 A, C , E 种植后, B, D, F 可从剩余的三种植物中各选 一种植物(允许重复) ,各有 3 种方法,此时共有 4 ? 3 ? 3 ? 3 ? 108 种方法。
2 (2)若 A, C , E 种二种植物,有 A4 种种法,当 A, C , E 种植后,若 A, C 种同一种,则 B 有 3 种种法, 2 ,此时共有 A4 ? 3 ? (3 ? 2 ? 2) ? 432 D, F 各有两种种法;若 C , E 或 E , A 种同一种,相同(只是次序不同)

种。
3 3 (3)若 A, C , E 种三种植物,有 A4 种种法,此时 B, D, F 各有 2 种种法;此时共有 A4 ? 2 ? 2 ? 2 ? 192

种。 根据加法原理,总共有 N ? 108 ? 432 ? 192 ? 732 种栽种方案。 引申:此题的原型为: “将圆分为 n( n ? 2) 个扇形,每个扇形用 r 种不同的颜色之一染色,要求相邻扇 形所染的颜色不同,问有多少种染色方法?” 设此题有 a n 种方法,将扇形按顺时针编号为 A1 , A2 , A3 ,?, An . 我们从 A1 开始依闪对扇形染色,使得除 A1 和 An 外,相邻扇形不同色,有 r ( r ? 1) n ?1 种不同的染色方 法,这时分两类为 A1 , An 同色,有 a n ?1 种; A1 和 An 不同色,有 a n 种。 因此 a n ? a n ?1 ? r ( r ? 1) n ?1 ,即 a n ? ( r ? 1) n ? ? a n ?1 ? r ( r ? 1) n ?1 ? ( r ? 1) n ,

a n ? (r ? 1) n ? ?[a n ?1 ? (r ? 1) n ?1 ].
4

所以数列 {a n ? ( r ? 1) n } 成等经数列,公比为 ? 1 ,易求得 a n ? ( r ? 1)(?1) n ? ( r ? 1) n . 特别地 n ? 6, r ? 4 时, a6 ? 732. 例 8 将 2 个 a 和 2 个 b 共 4 个字母填在如图所示的 16 个小方格内,每个小方格内至 多填 1 个字母,若使相同字母既不同行也不同列,则不同的填法共有多少种? 思路分析:此题是一道受限排列组合的综合题,按 a 先分类填入,再考虑 b 的填法。
2 2 解:使 2 个 a 既不同行也不同列的填法有 C 4 A4 ? 72 种,同理 2 个 b 既不同行也不 2 2 同列的填法有 C 4 A4 ? 72 种。

故由乘法原理可知,这样的填法共有 72 ? 72 种。其中有两种不符合要求的情况;2 个 a 所填的方格内
1 2 都填有 b 的情况有 72 种;2 个 a 所填的方格内仅有 1 个方格内填有 b 的情况有 C16 · A9 ? 16 ? 72 种。

所以,符合题设条件的填法共有 72 2 ? 72 ? 16 ? 72 ? 3960 种。 引申:①此题从简单化列式计算,突出了“正难则反”的转化意识,简单快捷。
2 2 ②假如 2 个 a 排空位置时,有 C 4 A4 ? 72 种。

不妨取如图情况。 若 1 个 b 在从左向右数的第 1 列时,另一个 b 有 9 ? 8 ? 8 ? 25 种填法;若 1 个 b 在第 2 列时,另一个 b 排在第 3 列或第 4 列,共有 6 ? 6 ? 6 ? 18 种填法;若 1 个 b 在第 3 列时, 另一个 b 只能在第 4 列,共有 4 ? 3 ? 12 种填法。 综上可知,符合条件的实数集合 A ? {a1 , a 2 ,?, a100 } 与 B ? {b1 , b2 ,?, b50 }. 已知从 A 到 B 的映射 f 使得 B 中每个元素都有原象且 f ( a1 ) ? f ( a 2 ) ? ? ? f ( a100 ) , 试求这样的映射个数为多少? 思路分析: 依据 f ( a1 ) ? f ( a 2 ) ? ? ? f ( a100 ) 可知, 这是一个组合问题, 且使 B 中每个元素都有原象, 可考虑构造模型去解决。 解:不失一般性,设 b1 ? b2 ? ? ? b50 ,将 A 中元素 a1 , a 2 ,?, a100 按顺序分为非空的 50 组。 即 x1 ? x 2 ? ? ? x50 ? 100 (其中 x1 , x 2 ,?, x50 ? 0 ,且 x1 , x 2 ,?, x50 ? N ? )的解的个数就是此题所求 的映射个数。
50 ?1 49 构造隔板法模型可知方程 x1 ? x 2 ? ? ? x50 ? 100 的正整数解为 C100 ?1 ? C 99 . 49 所以所求映射共有 C99 种。 n

点评:此题实质为“ n 种不同元素有重复取 k 个的组合数” ,即为方程
n

?x
i ?1

i

? k 的非负整数解的组数,

也就是方程

?y
i ?1

i

n ?1 k ? n ? k 的正整数解的组数 C n ? k ?1 ? C n ? k ?1 .

例 9 8 个女孩,25 个男孩围成一个圆圈,每两个女孩间至少站有 2 个男孩,问共有多少种不同的排 列方法?(只把圆旋转一下就重合的排法认为是相同的)
5

思路分析:从圆排列转化为线排列求解,然后再还原圆排列。 解:如设女孩中有一个 A,对任何满足要求的一个圆排列,令从 A 排头按顺时 针方向排列一直线排列 ABCD… 现以○表示女孩所站位置, ? 表示男孩所站位置,现在角 ? ABCD…○的右侧 至少有两个 ? 。让每个○“吸收”了右侧相邻的两个 ? ,画成一个⊕,于是每个○、

? 排列,对应一个⊕, ? 排列 ○ ? ? ? ○ ? ? ? ? ○ ? ? ? ? ? ○ ? ??
⊕? ⊕? ? ⊕? ? ?

⊕…

7 7 后一种位置是 8 个 “⊕” 与 25 ? 16 ? 9 个 “? ” 共 17 个元素, 并且以⊕为首位的排列, 共有 C 7 ? 9 ? C16 7 个,即男、女所处位置的排列有 C16 个,女孩站上去(A 固定在首位)有 7!种方法,男孩子站上去有 25!

种方法。
7 故总的排列数为 C16 ·7!25!=

16!25! . 9!

引申:此题还可转化为隔板模型解决。 以 8 个女孩为组长,将 25 个男孩分入该 8 组,每组内男孩数记为 x1 , x 2 ,?, x8 , 则 x1 ? x2 ? ? ? x8 ? 25, ( xi ? 2, i ? 1,2, ? 8) 即 ( x1 ? 1) ? ( x2 ? 1) ? ? ? ( x8 ? 1) ? 17 , ( xi ? 1, i ? 1,2, ? ,8)
8?1 7 于是由隔板法可求出符合条件的方程组的解的个数为 C17 ?1 ? C16 . 7 即 25 个男孩分入 8 组,每组至少 2 人的分组方法有 C16 种

8 个组排成每组以女孩为头的圆排列有 (8 ? 1)! ? 7! 种排列方法,再将 25 个男孩站入的方法数为 25!.
7 所以总的排列数为 C16 · 7! · 25! ?

16!25! . 9!

例 10 有 n 个人,已知他们任意 2 个至多通电话一次,他们任意 n ? 2 个人之间通电话的总数相等,都 等于 3k ( k ? N ? ) ,求 n 的所有可能的值。 思路分析:通过算两次建立等式求解。
n?2 解:设 n 个人之间通话的总次数为 m ,因为 n 个人可形成 C n 个 n ? 2 人组,而 n ? 2 人之间的通话总 n?2 次数都为 3k ,所以所有 n ? 2 人组中通话次数的总和为 C n · 3k . n?4 n?4 另一方面, 上述计数中, 每一对通话的人属于 C n 故每 2 人间一次通话重复计算了 C n ? 2 个 n ? 2 人组, ?2 n?2 Cn ? 3k n(n ? 1) ? 3k ? n?4 Cn (n ? 2)(n ? 3) ?2

次,所以 m ?

6

(1)若 3 不整除 n ,即 (3, n) ? 1 ,有 ( n ? 3, n) ? 1 , ( n ? 3,3k ) ? 1. 又 ( n ? 2, n ? 1) ? 1 ,所以 n ? 3 | n ? 1. 即

n ?1 2 为正整数。 ?1? n?3 n?3

所以 n ? 3 | 2, n ? 3 ? 2, n ? 5.
2 k 又 Cn ? 2 ? 3 ? 2, ∴ n ? 5.

故 n ? 5. (2)若 3 整除 n ,则 3 | n ? 3,3 ? | n?2, 即 (3, n ? 2) ? 1, ( n ? 2, n ? 1) ? 1. 所以 n ? 2 | n ,即

n 2 为正整数. ?1? n?2 n?2

所以 n ? 2 | 2 ,即 n ? 2 ? 2 ,即 n ? 4 ,这与 n ? 5 矛盾。 由(1) 、 (2)可知, n 只能为 5。另一方面,若 n ? 5 个人,其中每 2 人通电话一次,则任意 n ? 2 ? 3
2 人之间通话的次数都为 C3 ? 3 满足题目要求。

故所求的正整数只有一个, n ? 5. 点评:此题是组合与数论的综合题,有一定的难度。 例 11 求方程 2 x1 ? x2 ? x3 ? ? ? x9 ? x10 ? 3 的非负整数解的个数。 例 12 凸 n 边形的任意 3 条对角线不相交于形内的一点,问: (1)这些对角线将凸 n 边形分成多少个区域? (2)这些对角线被交点分成了多少条线段?

7


相关文章:
高一数学竞赛讲稿(第9次).pdf
高一数学竞赛讲稿(第9次) - 济南雨露高一数学竞赛班数学教学案(第 9 次)
高中数学竞赛夏令营讲稿_图文.ppt
高中数学竞赛夏令营讲稿 - 高中数学竞赛夏令营讲稿 第一部分【几个著名定理】 1
高一数学竞赛辅导讲义--第1-4讲.doc
高一数学竞赛辅导讲义--第1-4讲_高一数学_数学_高中教育_教育专区。高一数学
雨露高一数学竞赛讲稿_图文.doc
故这样的操作经过有限次就一定终止. 解 2 取目标函数 f(x1,x2,x3,x4,x5)...高一数学竞赛讲稿(第9次... 暂无评价 7页 免费 雨露3稿 21页 免费 雨露...
高一数学竞赛讲座3:高一数学竞赛讲座.doc
C E F D 9 H A G B 江苏省泰州中学高一数学竞赛讲稿 塞瓦定理及应
高一趣味数学竞赛.doc
高一趣味数学竞赛_高一数学_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档高一趣味数学竞赛_高一数学_数学_高中教育_教育专区。福鼎三中第十三届“...
高中数学竞赛“代数问题”高级讲稿.doc
高中数学竞赛“代数问题”高级讲稿浙江省杭州第十四中学 马茂年 (中国奥数高级教练、数学特级教师) 知识方法 在高中数学竞赛中,代数方面的问题是多种多样的,主要包括...
高一数学竞赛培训教材(有讲解和答案).doc
高一数学竞赛培训教材(有讲解和答案) - -1高一数学思维训练教师版 为学服务,
新高一竞赛不等式入门讲课讲稿.doc
高一竞赛不等式入门讲课讲稿_高一数学_数学_高中教育_教育专区。不等式在竞赛中很重要,该文档为新高一不等式入门讲课所用,想要答案联系qq ...
高一数学竞赛试题及答案.doc
y0=1, 经检验知,点(0,1),(-2,1)均在圆 C 上,因此,圆 C 过定点. 高一数学竞赛试题 第 12 页共 14 页 高一数学竞赛试题 第 13 页共 14 页 9、...
2015年福建省高一数学竞赛试题参考答案.doc
2015年福建省高一数学竞赛试题参考答案 - 2015 年福建省高一数学竞赛试题
通过竞赛在普通高中培养数学优秀生的实践与反思(发言稿).doc
通过竞赛在普通高中培养数学优秀生的实践与反思(发言稿) - 通过竞赛在普通高中培养数学优秀生的实践与反思 广州市第八十九中学 袁伟林 近年来, 随着广州市示范性...
函数迭代和函数方程(数学竞赛讲稿).doc
函数迭代和函数方程(数学竞赛讲稿) - 第一讲 一、基本知识简述 1. 函数迭代 设 f 是 D ? D 的函数,对任意 x ? D ,记 f 数f f (n) (n) (0) ...
高中数学说课比赛一等详细讲稿.doc
高中数学说课比赛一等详细讲稿_高二数学_数学_高中教育_教育专区。关于《随机事件
高一数学竞赛讲座2函数方程与函数迭代.doc
(1) , (2) 9 江苏省泰州中学高一数学竞赛讲稿 函数方程 高一数学备课组
高一数学竞赛培训教材.doc
暂无评价|0人阅读|0次下载|举报文档高一数学竞赛培训教材_高一数学_数学_高中
高一数学竞赛选拔题(解答).doc
高一数学竞赛选拔题(解答) - 余姚中学高一数学竞赛选拔题(解答) (考试时间:90 分钟) (每题 10 分,满分:100 分) 1. (2008 年北京大学自主招生试题) 求证:...
高一数学竞赛辅导计划.doc
暂无评价|0人阅读|0次下载|举报文档高一数学竞赛辅导计划_学科竞赛_高中教育_教育...第 7 讲 反证法、数学归纳法 第 8 讲 等差数列与等比数列 第 9 讲 递归...
高中数学新课程理念讲稿2 doc.doc
高中数学新课程理念讲稿2 doc_专业资料。面向 21 ...高一和高二对部分数 学特别优秀的学生开始数学竞赛...和发展的空间,具体 课程组合建议见《标准》第 9 ...
高一上学期数学竞赛试题.doc
高一上学期数学竞赛试题 - 滕州一中 2014 级掀起冬季学习热潮联赛试题 高一数学 命题人:石 分钟. 磊 2014 年 12 月 本试卷分第 I 卷(选择题)和第 II 卷(...
更多相关标签: