当前位置:首页 >> 学科竞赛 >>

计数问题竞赛讲义题二


计数问题竞赛讲义二
解排列、组合题的基本策略与方法 (1)合理分类与准确分步 (2)有序排列,无序组合 (3)排列、组合混合问题先选后排 (4)特殊元素、特殊位置优先 (5)正难则反,等价转化 (6)相邻问题捆绑处理 (7)不相邻问题插空处理策略(8)定序问题除法处理(9)分排问题直排处理(10)构造模型的策略 一.有条件限制的排列组合问题 例 1.甲组有 5 名男同学,3 名女同学;乙组有 6 名男同学、2 名女同学。若从甲、乙两组中各选出 2 名同 学,则选出的 4 人中恰有 1 名女同学的不同选法共有( ) 例 2. 甲、乙、丙 3 人站到共有 7 级的台阶上,若每级台阶最多站 2 人,同一级台阶上的人不区分站的位 置,则不同的站法种数是 (用数字作答) A.150 种 B.180 种 C.300 种 D.345 种 例 3.有 4 张分别标有数字 1,2,3,4 的红色卡片和 4 张分别标有数字 1,2,3,4 的蓝色卡片,从这 8 张 卡片中取出 4 张卡片排成一行.如果取出的 4 张卡片所标数字之和等于 10,则不同的排法共有 ________________种(用数字作答) . 例 4.某班班会准备从甲、乙等 7 名学生中选派 4 名学生发言,要求甲、乙两人至少有一人参加.当甲乙同 时参加时,他们两人的发言不能相邻.那么不同的发言顺序的种数为( ) A.360 B.520 C.600 D.720 例 5.由 1、2、3、4、5 组成没有重复数字且 1、2 都不与 5 相邻的五位数的个数是( ) A. 36 B. 32 C.28 D.24 例 6.把一同排 6 张座位编号为 1, 2,3, 4,5,6 的电影票全部分给 4 个人,每人至少分1 张,至多分 2 张,且这 两张票具有连续的编号,那么不同的分法种数是( )

A. 168

B. 96

C. 72

D. 144

例 7.将 2 个 a 和 2 个 b 共 4 个字母填在如图所示的 16 个小方格内,每个小方格内至多填 1 个字母,若使 相同字母既不同行也不同列,则不同的填法共有多少种?(用数字作答)。 2 2 2 2 解: 2 个 a 既不同行也不同列的填法有 C4 A4 =72 种, 使 同样, 2 个 b 既不同行也不同列的填法也有 C4 A4 =72 使 2 种,故由乘法原理,这样的填法共有 72 种,其中不符合要求的有两种情况:2 个 a 所在的方格内都填有 b 的情况有 72 种;2 个 a 所在的方格内仅有 1 个方格内填有 b 的情况有 C16 A9 =16×72 种。所以,符 2 合题设条件的填法共有 72 ?72?16×72=3960 种。 例 8.有 4 位同学在同一天的上、 下午参加“身高与体重”、 “立定跳远”、 “肺活量”、 “握
1 2

力”、“台阶”五个项目的测试,每位同学上、下午各测试一个项目,且不重复. 若上午不 测“握力”项目,下午不测“台阶”项目,其余项目上、下午都各测试一人. 则不同的安排 方式共有______________种(用数字作答).
二.鞋子配对问题 例 1.现有 5 双型号不同的鞋,从中任取 4 只,按下列条件各有多少种不同的取法? (1)互不配对 (2)恰有 1 双配对 (3)恰有 2 双配对 例 2.某电视台邀请了 6 位同学的父母共 12 人,请这 12 人中的 4 位介绍对子女的教育情况,如果这 4 位 中恰有一对是夫妻,那么不同的选择方法有多少? 三.分组分配问题 本类问题主要集中了三类问题:分组问题,不定向分配问题,定向分配问题 例 1.将 6 位志愿者分成 4 组,其中两个组各 2 人,另两个组各 1 人,分赴世博会的四个不同场馆服务,不 同的分配方案有多少种(用数字作答)? 例 2.将 5 名志愿者分配到 3 个不同的奥运场馆参加接待工作, 每个场馆至少分配一名志愿者的方案种数为 A. 540 B. 300 C. 180 D. 150

例 3.星期天,有 3 家人约好外出自驾游,每家都有三口人(两个大人一个孩子) ,现在他们准备开 A,B,C 三辆车,并且规定: (1)每辆车限坐 4 人; (2)每辆必须有一个大人开车; (3)三个孩子不能乘坐同一辆 车。问满足上述三个条件的乘车方法有多少种?(9180)
1

四.插空处理题型 例 1.马路上有编号为 1~10 的十盏路灯,为节电又不影响照明,可以将其中的三盏关掉,但不能同时关 掉相邻的两盏或三盏,也不能关掉两端的路灯,问有多少满足条件的关灯方案?(20) 例 2.某仪表显示屏上有 7 个小孔,每个小孔可显示 0 或 1,若每次显示其中三个小孔,但相邻两孔不能 同时显示,则这个显示屏可以显示多少不同的信号?(80) 例 3. 一排有 14 个具有编号的座位, 3 个人来坐, 现 要求他们都不坐两边且两人之间必须至少有 1 个空位, 问有多少种不同的坐法?(720) 例 4. 一排有 14 个具有编号的座位,现 3 个人来坐,要求他们每两人之间必须至少有 3 个空位,问有多少 种不同的坐法?(336) 例 5.5 个数码 1 和 4 个数码 0 组成一个二进制的 9 位数. (1)其中奇数有多少个? (70) (2)数码 0 不排在一起的偶数有多少个?(10) (3)恰有两个 0 连在一起,其余 0 不连在一起的有多少个?(20) 例 6. 某停车场有连成一排的 9 个停车位, 现有 5 辆不同型号的车需要停放, 按下列要求各有多少种停法? (1)5 辆车停放的位置连在一起; (2)有且仅有两车连在一起; (3)为方便车辆进出,要求任何 3 辆车不能在一起. 五.隔板模型问题 不定方程 x1 ? x2 ? ? ? xk ? n(n ? k ) 的正整数解的组数为 C n ?1 ,非负整数解的组数为 C n ? k ?1 例 1.将 20 个完全相同的小球放入编号为 1,2,3,4,5 的 5 个不同的盒子,每个盒中至少有一个小球, 那么这 20 个球有多少种不同的投放方案? 例 2.将 20 个完全相同的小球放入编号为 1,2,3,4,5 的 5 个不同的盒子,每个盒子的小球数不小于编 号数,那么这 20 个球有多少种不同的投放方案? 例 3.将 24 个志愿者名额分配给 3 个学校,则每校至少有一个名额,则不同的分配方法共有多少种? 例 4. (2008)将 24 个志愿者名额分配给 3 个学校,则每校至少有一个名额且各校名额互不相同的分配方 法共有多少种? 解析:设分配给 3 个学校的名额数分别为 x1 , x2 , x3 ,则每校至少有一个名额的分法数为不定方程:
k ?1 k ?1

x1 ? x2 ? x3 ? 24 .
的正整数解的个数, C 23 ? 253 .
2

又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有 31 种. 综上知,满足条件的分配方法共有 253-31=222 种. 例 5.设两个集合 A ? {a1 , a 2 , a3 ,?, a15 } , B ? {b1 , b2 , b3 ,?, b10 } ,若从 A 到 B 的映射 f 使得 B 中的每 一个元素都有原象,且 f (a1 ) ? f (a 2 ) ? ? ? f (a15 ) ,则这样的映射共有多少个? 例 6.在 1,2,3,?,14 中,按数从小到大的顺序取出 a1 , a 2 , a3 ,使同时满足 a 2 ? a1 ? 4 ,a3 ? a 2 ? 4 , 则满足条件的不同取法有多少种? 例 7.求不等式 x ? y ? z ? 10 的正整数解的个数. (84) 例 8.方程 2 x1 ? x2 ? x3 ? ? ? x10 ? 3 有多少个非负整数解.(174) 解析:注意到 x1 是重根,且只能取 1,或 2. 例 9. (2005)如果自然数 a 的各位数字之和等于 7,那么称 a 为“吉祥数” .将所有“吉祥数”从小到大 排成一列 a1 , a 2 , a3 ,?, 若 a n ? 2005 ,则 a5 n ? 。

六.容斥原理:设全集 U 是有限集合, A1 , A2 , ?, An 是 U 的子集,则有

2

(1) A1 ? A2 ? ? ? An ?

?| A | ? ? A ? A
i ?1 i 1?i ? j ? n i

n

j

?

1?i ? j ? k ? n

?A ?A
i

j

? Ak ? ? ? ?? 1?

n ?1

A1 ? A2 ? ? ? An

(2) A1 ? A2 ? ? ? An = A1 ? A2 ? ? ? An = U - A1 ? A2 ? ? ? An 特别地,当 n ? 2 时, A1 ? A2 ? A1 ? A2 ? A1 ? A2 ; 当 n ? 3 时, A1 ? A2 ? A3 = A1 ? A2 ? A3 ? A1 ? A2 ? A1 ? A3 ? A2 ? A3 + A1 ? A2 ? A3 . 例 1.一次会议有 2001 位数学家参加,每人至少有 1335 位合作者,证明:可以找到 4 位数学家,他们中 每两位都合作过。 解 析 : 设 与 a i 合 作 过 的 数 学 家 的 集 合 为 Ai , 并 且 设 数 学 家 a1与a2 合 作 过 , 则

| A1 ? A2 |?| A1 | ? | A2 | ? | A1 ? A2 |? 1335 ? 1335 ? 2001 ? 0
所以有数学家 a3 ? A1 ? A2 ,即 a3与a1 , a 2 都合作过。 又因为 | A1 ? A2 ? A3 |?| A1 ? A2 | ? | A3 | ? | A1 ? A2 ? A3 |

?| A1 | ? | A2 ? | A3 | ? | A1 ? A2 | ? | A1 ? A2 ? A3 | ? 3 ?1335 ? 2 ? 2001 ? 3
所以必有 a 4 ? A1 ? A2 ? A3 ,即 a 4 与 a1 , a 2 , a3 都合作过。 所以总有 4 位数学家,他们中每两位都合作过。 例 2.由数字 1,2,3 组成的 n 位数中,要求 1,2,3 每个数字至少出现一次,求所有这种 n 位数的个数. 解析:由数字 1,2,3 组成的 n 位数的集合记作 S , | S |? 3 。设 S 中所有不含 k 的 n 位数的集合记作
n

Ak (k ? 1,2,3) ,则 Ak 是 S 中所有含有数字 k 的 n 位数的集合。
A1 ? A2 ? A3 即是 S 中同时含有数字 1,2 和 3 的 n 位数的全体构成的集合,有公式 2 得: A1 ? A2 ? A3 ?| S | ? | A1 | ? | A2 | ? | A3 | ? | A1 ? A2 | ? | A2 ? A3 | ? | A1 ? A3 | ? | A1 ? A2 ? A3 |
因为 Ak 是 S 中所有不含 k 的 n 位数的集合,所以 | Ak |? 2
n

Ai ? A j 是所有不含数字 i, j 的 n 位数的集合,所以 | Ai ? A j |? 1,1 ? i ? j ? 3
因为 | A1 ? A2 ? A3 |? 0 所以满足条件的 n 位数的个数为 | A1 ? A2 ? A3 |? 3 ? 3 ? 2 ? 3
n n

例 3.有 4 对夫妇站成一排,没有任何一对夫妇相邻的站法有多少种?

第 夫 相 的 列 解析:记 S ? {8人 全 列 } , Ai ? {S中 i对 妇 邻 排 的 排

(i ? 1,2,3,4), 则 }

8 2 7 | S |? A8 , | Ai |? A2 ? A7 ,原题即求 | A1 ? A2 ? A3 ? A4 | ,易算得:

2 2 6 | Ai ? A j |? A2 ? A2 ? A6 (1 ? i ? j ? 4)

3

2 2 2 5 | Ai ? A j ? Ak |? A2 ? A2 ? A2 ? A5 (1 ? i ? j ? k ? 4)
2 4 | A1 ? A2 ? A3 ? A4 |? ( A2 ) 4 ? A4

所以由公式可算得 | A1 ? A2 ? A3 ? A4 |? 13824 例 4. (贝努利装错信封问题)若(1,2,?, n )的一个排列( i1 , i 2 ,?, i n )满足 i1 ? 1 , i2 ? 2 ,?,

in ? n ,则称( i1 , i 2 ,?, i n )为(1,2,?, n )的一个错位排列.试求(1,2,?, n )的所有错
位排列的个数. 解析: n!(1 ?

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

例 5.设 ? (n) ( n 为正整数)表示小于 n 且与 n 互素的数的个数,求 ? (n) . 分析: ? (2) ? 1 , ? (3) ? 2 , ? (4) ? 2 , ? (10) ? 4 ,当 p 是素数时, ? ( p) ? p ? 1 注意到算术基本定理:对任意不小于 2 的正整数 n 都可以唯一表示为

n ? p1 1 p 2 2 ? p k k ,其中 p i 为 n 的质因数, ? i 是正整数
解:由算术基本定理可得

?

?

?

n ? p1 1 p2 2 ? pk

?

?

?k

,其中 p i 为 n 的质因数, ? i 是正整数,

设 U ={1,2,3,?, n }, Ai ? a a ? 0(mod pi ), a ? U , i ? 1,2,3,?, k , 注意 Ai 实际上是 p i 的倍数的集合,则 Ai 是指不是 p i 的倍数的集合, A1 ? A2 ? ? ? Ak 即表示从 1 到 n 中与 n 互素的数的个数,注意到

?

?

Ai ?

n n n , Ai ? A j ? ,?, A1 ? A2 ? ? ? Ak ? pi ? p j p1 p 2 ? p k pi

于是 ? (n) = A1 ? A2 ? ? ? An = A1 ? A2 ? ? ? An = U - A1 ? A2 ? ? ? An =n-

?A
i ?1 k

k

i

?

1?i ? j ? k

?A ?A
i

j

? ? ? (?1) k A1 ? A2 ? ? ? Ak

=n?

?p
i ?1

n
i

?

1?i ? j ? k

?

n n 1 1 1 ? ? ? (?1) k )(1 ? ) ? (1 ? ) . = n(1 ? pi ? p j p1 p 2 ? p k p1 p2 pk

七.递推方法 1.(斐波那契数列)一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一 对小兔子来.如果所有兔都不死,那么刚出生的一对小兔子一年以后通过繁殖可以得到多少对兔 子? 理解:每月的大兔子数为上月的兔子数,每月的小兔子数为上月的大兔子数,即上上月的兔子 数,相加. 2. (汉诺塔问题)设有 5 个银圈,大小不同,从大到小排列在三根金棒中的一根.这些银圈要搬到另一根 金棒上,每次搬一个.第三根金棒作为银圈暂时摆放用.在搬动过程中,仍要保持大圈在下,小圈在上,
4

问至少要搬动多少次,才能将所有银圈从一根棒搬到另一根,且搬完后银圈相对位置不变? ( a n ? 2a n ?1 ? 1) 3. (贝努利装错信封问题) (1, ?,n ) 推导 2, 的所有错位排列的个数为 n!(1 ? 提示: a n ? (n ? 1)( a n ?1 ? a n ?2 ) ,其中 a1 ? 0 , a 2 ? 1 , a3 ? 2 4. (环形涂色问题)一个圆形花坛分为两部分,中间小圆部分种植草坪和绿色灌木,周围的圆环分为

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

n (n ? 3, n ? N ? ) 份,种植 m 种不同颜色的花,要求相邻两部分种植不同颜色的花.
(1)如图 1,圆环分成的 3 等份为 a1 , a 2 , a3

,有多少不同的种植方法?如图 2,圆环分成的 4 等份为

a1 , a 2 , a3 , a 4 ,有多少不同的种植方法?(2)如图 3,圆环分成的 n 等份为 a1 , a 2 , a3 ,?, a n ,有多少不同
的种植方法?
3 ?a 3 ? Am ? m( m ? 1)( m ? 2) ? 分析可得: ? ?a n ?1 ? m( m ? 1) n ?1 ? a n ?

a n ? (m ? 1)[( m ? 1) n ?1 ? (?1) n ] ]
八.其它的排列组合 1.圆排列 (1)由 A ? {a1 , a 2 , a3 ,?, a n } 的 n 个元素中,每次取出 r 个元素排在一个圆环上,叫做一个圆排列(或 叫环状排列) . (2)圆排列有三个特点: (i)无头无尾; (ii)按照同一方向转换后仍是同一排列; (iii)两个圆排列只 有在元素不同或者元素虽然相同,但元素之间的顺序不同,才是不同的圆排列. (3)在 A ? {a1 , a 2 , a3 ,?, a n } 的 n 个元素中,每次取出 k 个不同的元素进行圆排列,圆排列数为 例 1.有 5 对夫妻围圆桌就座,任何一对夫妻都必须相邻,问有多少种不同的入座方法?(768) 例 2.用 A, B, C, D, E, F 六种不同的颜色给正方体的各个面涂色,并使相邻面必须涂不同的颜色,共有多 少种不同的涂色方式?(230) 2.不尽相异元素的全排列 如 果 n 个 元 素 中 , 有 p1 个 元 素 相 同 , 又 有 p 2 个 元 素 相 同 , ? , 又 有 p s 个 元 素 相 同 ( p1 ? p 2 ? ? ? p s ? n ) ,这 n 个元素全部取出的排列叫做不尽相异的 n 个元素的全排列,它的排列数 是
k An . k

n! p1!? p 2 !?? ? p s !

例 3.现有 10 张卡片,每张卡片上写有 1、2、3、4、5 中的某个数字,其中 3 张 1,3 张 2,2 张 3,1 张 4,1 张 5,任意取出 4 张,可组成多少个不同的四位数? 3.可重复组合 (1)从 n 个元素,每次取出允许重复的 k 个元素,并成一组叫从 n 个元素取出 k 个的可重复组合. (2)定理:从 n 个元素每次取出 k 个元素有重复的组合数为: H n ? C n ? ( k ?1) .
k k

5


相关文章:
几何中的计数问题二练习题
几何中的计数问题二练习题_学科竞赛_小学教育_教育专区。几何中的计数问题练习题 一、填空题 (每小题 5 分) 1、.下列图形各有几条线段 ( )条 ( )条 ( ...
计数问题竞赛讲义题一
计数问题竞赛讲义一一.分类加法计数原理与分步乘法计数原理 1.分类加法计数原理 完成一件事情,有 n 类不同方案,在第 1 类方案中有 m1 种不同的方法,在第 2 ...
四年级奥数计数问题(二)
四年级奥数计数问题(二)_学科竞赛_小学教育_教育...中国领先的个性化教育品牌 超锐教育学科教师辅导讲义 ...四年级奥数题:图形的计... 6页 免费 四年级...
组合计数问题题解议
本题中需要先从第一行开始染色, 根据题目要求按照第二行与第一行染的黑格是否...组合计数问题是数学竞赛中常见的一类问题,解决这类问题的基本方法有: (1) 运用...
计数问题讲义
题目 使用教具 计数问题 讲义、笔、纸 教学 目标 1.掌握加法原理和乘法原理 2...中加法原理与乘法原理的区别 参考教材 知识纵横计数问题是数学竞赛中常见的问题。...
数学竞赛讲义组合计数
数学竞赛讲义组合计数_学科竞赛_高中教育_教育专区。数竞必备,组合计数 ...注 本题为 1996 年联赛试题,是历年来一试计数问题中最复杂的一道,其背景与...
第八讲 几何中的计数问题(二)
第八讲 几何中的计数问题(二)_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档第八讲 几何中的计数问题(二)_学科竞赛_小学教育_教育专区。 ...
几何中的计数问题二
几何中的计数问题二_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档几何中的计数问题二_学科竞赛_小学教育_教育专区。 ...
二年级上册奥数第2课《数数与计数二》试题附答案
二年级上册奥数第2课《数数与计数二试题附答案_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载二年级上册奥数第2课《数数与计数二试题附答案_学科...
小学高段奥数《计数问题》作业
小学高段奥数《计数问题》作业_学科竞赛_小学教育_教育专区。杨老师高段奥数辅导...小学四年级经典奥数题图... 8页 2下载券 [小学奥数辅导系列讲座]... 4页...
更多相关标签: