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

数学竞赛讲义:排列与组合


数学竞赛讲义:排列与组合
【赛点直击】
一、两个基本原理 加法原理 设 A 为完成一件事情的所有方法的集合,它可以划分为 n 个互不相交的非空子集 A1, A2,?,An,|Ai|=mi(i=1,2,?,n),那么完成这件事情的总方法数为: N=|A|=m1+m2+?+mn;使用加法原理的关键在于对所计数的对象进行完全分类. 乘法原理 设 A 为完成一件事情的

所有方法的集合,且完成这件事情需要几个步骤,实现第 i(i=1,2,?,n)个步骤的方法的集合为 Ai,|Ai|=mi,那么完成这件事情的总方法数为 N=|A|=m1×m2×?×mn;使用乘法原理的关键在于对所计数的对象进行完全分步. 二、相异元素的排列与组合 n! m ? n ? (n ? 1) ? ? (n ? m ? 1) ? (1)从 n 个不同元素中,任取 m 个不同元素的排列数是 An ; (n ? m)!
n! (2)从 n 个不同元素中,任取 m 个不同元素的组合数是 C ? ; ( n ? m )!
m n

n 个元素的不全相异元素的全排列个数为

n! ,证明如下: n1!n2 !...nk !

先把每组中的元素看作是不相同的,则 n 个不同元素的全排列数为 n ! ,然后分别将每个组的元素 还其本来面目——每个组的元素是相同的,则在这 n ! 个全排列中,每个排列都重复出现了 n1 !n2 !...nk ! 次,所以不全相异元素的全排列数为

n! . n1!n2 !...nk !

六、多组组合 定义 将 n 个不同的元素分成 k 组的组合称为 n 个不同元素的 k-组合. 对于一个 n 个不同元素的 k-组合,若第 i 组有 n i 个元素,( i ? 1,2,...,k ),则不难证明不同的分 组方法数为 C n 1
n , n2 ,..., nk

?

n! 事实上, 我们把分组的过程安排成相继的 k 个步骤: 第一步, 从n个 n1!n2 !...nk !
n

三、圆排列 定义 从 n 元集中任取 r 个不同元素,仅按元素之间的相对位置而不分首尾排成一个圆圈,这种
r 排列称为 n 个不同元素的 r-圆排列,其排列数记为 H n .

n1 2 不同元素中选 n1 个,有 C n 种方法;第二步,从 n ? n1 个元素中选 n2 个有 Cn? n1 种方法,??,第 k
k 步,从 n ? n1 ? n2 ? ... ? nk ?1 个元素选 nk 个元素,有 Cn? ( n1 ? n2 ?...? nk ?1 ) 种方法,再由乘法原理得证.

n

Ar 由定义,不难求得: H 与组合数 C 和排列数 A 的关系为: H ? C (r ? 1)!? n . r
r n r n r n
r n r n

七、重复组合 定义 从 n 个不同的元素中任取 r 个允许重复出现的组合称为 n 个不同元素的 r—可重组合.
r 不难证明,n 个不同元素的 r—可重组合的个数为 Cn ?r ?1 .

事实上设已将某 r 个不同元素在圆周上排好,并从某个元素开始将它们依次记为 A1 , A2 ,?, Ar , 事 实 上 , 设 ( a1 , a2 ,...,ar ) 是 取 自 {1,2, ? ,n} 中 的 任 一 r- 可 重 复 组 合 , 并 设 现在保持这个顺序不变,让 A1 去任意选择圆周上的 r 个位置之一,有 r 种不同的选择,这 r 种选择所 对应的排列形式不同实则相同由于 r 个元素的全排列数为 r ! ,故 r 个元素的圆排列数为 (r ? 1)!,故 n 个元素的圆排列数为 C (r ? 1)!.
r n

a1 ? a 2 ? ... ? a r , b2 ? a2 ? 1, 令 bi ? ai ? i ? 1(1 ? i ? r ) , 从而 b1 ? a1 , ?, b3 ? a3 ? 2 ,
br ? ar ? r ? 1,显然下面两组数是一对一的:
a1 ? a2 ? ... ? ar , 1 ? a1 ? a2 ? 1 ? a3 ? 2 ? ... ? ar ? r ? 1 ? n ? r ? 1
设 A ? ?(a1 , a2 ,...,ar ) | ai ?{1,2,...,n}, a1 ? a2 ? ... ? ar ?,

四、重复排列 定义 从 n 元集中允许重复地任取 r 个元素排成一列,称为 n 个不同元素的 r-可重排列. 利用乘法原理易证明, n 个不同元素的 r-可重排列数为 n , 这类问题一般可直接用乘法原理求解. 五、不全相异元素的全排列 定义 设 n 个元素可分为 k 组,每一组中的元素是相同的,不同组间的元素是不同的,其中第 i 组的元素个数为 n i (i ? 1,2,...,k ) , n1 ? n2 ? ... ? nk ? n ,则这 n 个元素的全排列称为不全相异元素 的全排列.
r

B?

?(b1 , b2 ,...,br ) | bi ?{1,2,...,n ? r ? 1}, b1 ? b2 ? ... ? br ?,则由 A、B 之间存在一一对应,可

r 知 | A |?| B |? Cn ?r ?1 ,得证.

在 上 述 证 明 中 , 设 r- 可 重 复 组 合 a1 , a2 ,...,ar 中 含 有 x1 个 1 , x2 个 2 , ? , xn 个 n , 则

x1 ? x2 ? ... ? xn ? r ,且显然有( a1 , a2 ,...,ar )与( x1 , x2 ,...,xn )一一对应,因此我们立即可得:
r 定理 1 不定方程 x1 ? x2 ? ... ? xn ? r 的非负整数解的个数为 Cn ?r ?1 .

数应与前 4 位数字之和被 3 除的余数有关:当该余数为 2 时,个位上可为 1,4,7 中的一个;当该余 数为 1 时,个位上可为 2,5,8 中的一个;当该余数为 0 时,个位上可为 0,3,9 中的一个,总之, 不论前 4 位数如何,个位数字都有 3 种可能情况.所以这类五位数的个数为 8×9×9×9×3=17496, 因此,含数字 6 而又可被 3 整除的五位数的个数为 30000-17496=12504 种可能. 例 4.从 1,2,3,4,??,49 中取出六个不同的数字,其中至少有两个是相邻的取法种数是多 少? 解:设 a1 , a2 ,
, a6 是取自 1,2,3,4,??,49 中的六个不同的数,不妨设 a1 ? a2 ? ? a6 ,显

?1 定理 2 不定方程 x1 ? x2 ? ... ? xn ? r 的正整数解的个数为 Crn? 1 .

证 明 : 令 yi ? xi ? 1 , 其 中 xi ? 1 , ( x1 , x2 , . . x . n, ) 是 已 知 方 程 的 正 整 数 解 , 则

y1 ? y2 ? ... ? yn ? r ? n

(*),由定理 1 知,方程(*)有 Cn?( n?r )?1 ? Cr ?1 ? Cr ?1 个正整数解.

r ?n

r ?n

n?1

然 a1 ? a2 ? 1 ? a3 ? 2 ? a4 ? 3 ? a5 ? 4 ? a6 ? 5 ,且 a1 , a2 ? 1, a3 ? 2, a4 ? 3, a5 ? 4, a6 ? 5互不相同的充要条件 是: a1 , a2 ,
, a6 中不含相邻的数. , a6 ) 对应于 (a1 , a2 ? 1, a3 ? 2, a4 ? 3, a5 ? 4, a6 ? 5) ,则在取自 1 至 49 之间的六个

【赛题解析】
例 1.在由 n2 个小方格组成的正方形中,有多少个由整数个小方格组成的大小或位置不同的正方 形? 解:由整数个小方格组成的大小位置不同的正方形可分成 n 类,第 k 类为 k×k 的正方形,共有

作六元数组 (a1 , a2 ,

不同且没有相邻的数构成的六元组集合与所有取自 1 至 44 之间的六个不同的数构成的六元组集合之间
6 建立了一一对应,因此这两个集合中六元组的个数都为 C44 ,而 1 至 49 之间的六个不同的数构成的六

(n ? k ? 1) 2 个 (k=1,2,…,n) , 于 是 由 加 法 原 理 得 所 求 正 方 形 的 总 个 数 为
n 1 N ? ? (n ? k ? 1) 2 ? n(n ? 1)(2n ? 1) . 6 k ?1

6 6 6 元组的个数为 C49 ,于是,其中有相邻数的六元组的个数为 C49 . ? C44

说明:此题将问题进行分类,直接用加法及乘法原理进行求解,两个原理是解决排列组合问题最 基本的工具. 例 2.设整数 a,b,c 为三角形三边,a+b=n∈N,1?c?n-1,求这样的整边三角形的个数 解:不妨设 b?a,有 1?a?[

说明:本题通过对应的方法将数相邻的问题转化为元素互异的问题,从而得到求解,对应的方法 是解决排列组合问题的一种常用方法. 例 5.如图 ABCDEF 为六边形,一只青蛙开始在顶点 A 处,它每次可随意跳到相邻两个顶点之一. (1)若在 5 次内跳到 D 点,则停止跳动;若 5 次内不能跳到 D 点,跳完 5 次也停止跳动.问这只 青蛙从开始到停止,可能出现的不同跳法有几种? E D (2)若青蛙共跳 12 次,最终跳回到 A 点的不同跳法有几种? 解:(1)由条件,青蛙的跳法只可能出现两种情况: F C ① 跳 3 次到达 D 点,有 2 种跳法. ②跳 5 次停止(前 3 次不到 D 点),注意到前 3 次的 2 种跳法中,有 2 种到达 D 点,故前 3 次有 2 ? 2 ? 6 种跳法,而后 2 次有 2 种跳法,因
3
2 3

n ],这样的整边三角形可分为两类. 2

第一类:c 为最大边,令 a ? i ,则 b ? n ? i ,n-i?c?n-1,这样的三角形有 (n ? 1) ? (n ? i) ? 1 ? i 个; 第二类: c 不为最大边, 则 b ? c, c ? a ? b , 故 b ? a ? n ? 2i ? c ? n ? i , 故 n ? 2i ? 1 ? c ? n ? i ? 1, 这样的三角形有 (n ? i ? 1) ? (n ? 2i ? 1) ? 1 ? i ? 1 .

A

B

? n ? 由加法原理,使 a+b=n 的整边三角形的个数为 f (n) ? ? (i ? i ? 1) ? ? [ ] ? . ? 2 ? i ?1
例 3.有多少个能被 3 整除而又含有数字 6 的五位数? 解:易知,在由 10000~99999 这 90000 个五位数中,共有 30000 个可被 3 整除,下面先求其中不 含数字 6 的有多少个. 这件事情可分步来完成:在最高位,不能为 0 和 6,因此有 8 种可能的情况,在千、百、十位上, 不能为 6,各有 9 种可能的情况,在个位上,不能为 6,且应使整个五位数能被 3 整除,因此所出现的

n [ ] 2

2

此有 6 ? 2 ? 24 种跳法.由①、②可知,共有 2+24=26 种不同的跳法.
2

(2)设青蛙每逆时针跳一步记为+1,每顺时针跳一步记为-1,共跳 12 次,将所有这些数相加,若其 和为 6 的倍数,则青蛙跳回 A 处,若其和不为 6 的倍数,则青蛙不可能跳回原处,若其和为 0,则必 为 6 个+1 和 6 个-1 相加,共有 C12 种可能;若其和为 6,则必为 9 个+1 和 3 个-1 相加,共 C12 种;若 其和为-6,则必为 3 个+1 和 9 个-1 相加,共 C12 种;若其和为 12,则有 1 种可能,若其和为-12,也
3 6 3

6 3 有一种可能,因此满足要求的不同跳法总数为 C12 ? 2C12 ? 2 种.

3 a5 + a4 =48,同理, a 4 ? a3 =24,而 a3 ? A3 ? 6 ,∴ a5 =30,故最后的结果为:30×4=120 种.

例 6.将一个四棱锥 S-ABCD 的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有 5 种颜色可供使用,那么不同的染色方法的总数是多少?
3 解法一:由题设,四棱锥 S-ABCD 的顶点 S、A、B 所染的颜色互不相同,它们共 A5 种染色方法.

此问题可一般化为:把一个圆分成 n(n ? 2) 个扇形,依次记为 S1 , S 2 ,?, S n , 每个扇形都可用红、 白、蓝三种不同颜色之任一种涂色,且三种颜色均至少用一次,要求相邻的扇形颜色互不相同,问有 多少种涂色法?
S4 S5 S1 S3

当 S、A、B 已染好时,不妨设其颜色分别为 1、2、3,若 C 染颜色 2,则 D 可染颜色 3、4、5 之 一,有 3 种染法;若 C 染颜色 4,则 D 可染颜色 3 或 5,有 2 种染法;若 C 染颜色 5,则 D 可染颜色 3 或 4,也有 2 种染法,由此可见,当 S、A、B 已染好时,C 与 D 还有 7 种染法,从而总的染色方法
3 数为 7× A5 =420 种.

略解:同上可得: an ? an?1 ? 3 ? 2 n?1 , n ? 4,5,6,? , a3 ? 6 . 若 没 有 条 件 “ 颜 色 均 至 少 用 一 次 ” , 结 果 为

S2

an ? an?1 ? 3 ? 2n?1 , n ? 4,5,6,?, a2 ? 6 .
更一般的情形是:把一个圆分成 n(n ? 2) 个扇形,依次记为 S1 , S 2 ,?, S n , 每个扇

解法二:满足题设条件的染色至少要用三种颜色. (1)若恰用三种颜色,可先从 5 种颜色中任选一种染顶点 S,再从余下的四种颜色中任选两种染 A、 B、C、D 四点,此时只能 A 与 C、B 与 D 分别同色,故有 C ? C C ? 60 种方法;
1 5 2 4 1 2

形都可用 r 种不同颜色之任一种涂色,要求相邻的扇形颜色互不相同,问有多少种涂色法? 有 an ? an?1 ? r ? (r ?1)n?1 , n ? 4,5,6, ,可得 an ? (r ? 1)(?1) n ? (r ? 1) n

(2)若恰用四种颜色染色,可以先从 5 种颜色中任选一种染顶点 S,再从余下的四种颜色中任选两种
2 染 A 与 B,由于 A 与 B 颜色可以交换,故有 A4 种染法,再从余下的两种颜色中任选一种染 D 或 C,
1 2 1 1 而 D 与 C 中另一个只需染与其相对顶点同色即可,故有 C5 A4 C2C2 ? 240种方法; 5 (3)若恰用 5 种颜色染色,易知有 A5 ? 120种染法.

说明:当我们用集合划分的方法对问题进行分类计数时,有时不可能一次性获得成功,这就需要 通过建立递推关系来求解,我们把这种计数方法称为递推方法. 例 7.设集合 A={1,2,3,?,366},如果 A 的一个二元子集 B={a,b}满足 17|a+b,则称 B 具有性质 P. (1) 求 A 的具有性质 P 的所有二元子集的个数; (2) 求 A 的两两不相交且具有性质 P 的所有二元子集的个数. 解:(1)a+b≡0(mod17),即 a≡k(mod17)且 b≡17-k(mod17),k=0,1,2,?,16, 将 1,2,3,?,366 按模 17 可分为 17 类[0],[1],?[16]; 因 366=17×21+9,故|[1]|=|[2]|=?=|[9]|=22,|[10]|=|[11]|=?=|[16]|=|[0]|=21, 欲 17|a+b,当且仅当 a,b∈[0]或 a∈[k],b∈[17-k], 当 a,b∈[0]时,具有性质 P 的二元子集的个数为 C 21 个; 当 a∈[k],b∈[17-k],k=1,2,?,7 时,具有性质 P 的二元子集有 7C22 C21 个; 当 a∈[8],b∈[9]时,具有性质 P 的二元子集有 C21C21 个; 所以 A 的具有性质 P 的二元子集总个数为 C21 ? 7C22 C21 ? C21C21 ? 3928个.
2 1 1 1 1 1 1 1 1 2

综上所知,满足题意的总染色方法数为 60+240+120=420 种. 类题:(2003 年高考江苏第 15 题) 某城市在中心广场建造一个花囿,花囿分为 6 个部分(如图),现要 栽种 4 种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的 花,不同的栽种方法有 ______________种(以数字作答). 解法一:1、2、3 两两相邻,颜色应互不相同,故有 A4 种不同种法; 1、2、3 种好后,用树图方法不难得到 4、5、6 共有 5 种种法,由乘法原理得共有 A4 × 5=120 种种法. 解法二:先种 1,有 4 种颜色可选取,2、3、4、5、6 形成一个圆环,要求用 3 种颜色涂上,且相 邻的颜色不同即可转化为如下问题:将一个圆分成 5 个扇形,将三种颜色涂入其中,相邻的扇形涂不 同的颜色.先涂 S1 ,有三种涂法,再涂 S 2 ,有两种涂法,再涂 3、4 各有两种涂法,再涂 5,如果只 要求它与 4 颜色不同,则仍有两种涂法,这样共有 3×2×2×2×2=48 种涂法,但这 48 种涂法中有两 类: 一类 5 与 1 颜色不同, 这种涂法符合题意,其数设为 a5 一类 5 与 1 颜色相同,这种涂法不合题意, 如果把 5 与 1 合并看成一个扇形,这类涂法就相当于把圆分成 4 个扇形,按题设要求,其数为 a4 ,即
3 3

说明:如果把子集换成数对(a,b),则共有 2×3928 个. (2)为使二元子集两两不交,可作如下搭配: a,b∈[0]时,共有 10 个子集; a∈[k],b∈[17-k],k=1,2,?,7,有 21 个子集; 当 a∈[8],b∈[9]时,有 22 个子集.

故 A 的具有性质 P 的两两不交的二元子集共有 10+7×21=179 个. 例 8.8 个女孩和 25 个男孩围成一圈,任何两个女孩之间至少站两个男孩,问共有多少种不同的 排列方法(只要把圈旋转一下就重合的排法认为是相同的). 解:以 1 个女孩和 2 个男孩为一组,且使女孩恰好站在两个男孩中间,余下的 9 个男孩和这 8 个
16 组被看成是 17 个元素,显然这 17 个元素任意的圆排列数为 A16 种再次,分在 8 个组内的 16 个男孩在 9 16 16 16 16 个位置上的排列是 A16 ,所以总的排列方法数为: C25 A16 A16 .

k Fn ? ? C n ? k ?1 . k ?0

n [ ] 2

若将所跨的每一级台阶,此人均用红、白两种颜色做上记号,则标有不同颜色的路线共有

?C
i ?0

n [ ] 2

i n ?i

? 2 n?2i ? 3n ? 1 种,其递推关系式为 an ? 2an?1 ? an?2 , a1 ? 2, a2 ? 5 .

例 11.把 n 个不同的球,分别装入 m 个盒子中,使其中 m1 个盒子中每个都有 p1 个球, m2 个盒 子 中 每 个 都 有 p 2 个 球 , ? , mk 个 盒 子 中 每 个 都 有 p k 个 球 , 这 里 ,

说明:此题为圆排列问题.

1,2,...,n?到集合 B ? ? 1,2,...,m?的映射的个数. 例 9.试求从集合 A ? ?
解:由映射的定义知,每一个到 B 的映射对应着 m 个不同元素的 n -可重排列,故从 A 到 B 的映 射的个数为 m . 例 10.一段楼梯共有 12 级台阶,某人上楼时,有时一步迈一台阶,有时一步迈两台阶,问此人 共有多少种上楼的方法? 解:现将“一步迈两级台阶”这一动作记为 a,因为楼梯共有 12 级台阶,故动作 a 至多只能做 6 次;再记“一步迈一级台阶”的动作为 b,则上楼的整个过程由 k 个 a 及 12-2k 个 b 组成,这里 k 可取 0,1,2,3,4,5,6,对于某个 k,其全排列数为:
n

m ? m1 ? m2 ? ...? mk , n ? p1m1 ? p2m2 ? ...? pk mk ,求下列情况下,各有多少种不同放法:(1)盒
子均不相同;(2)装有相同数目的球的盒子相同. 解:(1)这是一个将 n 个不同元素分为 m 组的多组组合,故不同的放法数有

f ?

n! ; ( p1!) ( p2 !) m2 ...( pk !) mk
m1

(2)因为相同数目的球的盒子相同(不加区别),故所求放法数为

[k ? (12 ? 2k ]! (12 ? k )! ? ,因此,上楼的 k!(12 ? 2k )! k!(12 ? 2k )!

f . m1!m2 !...mk !

例 12.电视台在 n 天内共播出 r 次商业广告,问若每天至少播 p 次广告( np ? r ),就每天播出 广告的次数而言,共有几种播出方法? 解 : 设 第 i 天 播 出 广 告 x i 次 , 由 题 设 知 : x1 ? x2 ? . . . ? xn ? r , xi ? p(i ? 1,2,...,n) , 令

方法共有:

? k!(12 ? 2k )! =233 种.
k ?0

6

(12 ? k )!

解法 2:以 k=4 为例,即 4 个两级,4 个一级,相当于共 8 步,其中有四步为两级,即相当于从 8
4 步中选 4 步跨两级,其余跨一级,故结果应为 C8 ;

yi ? xi ? p ,则 y1 ? y2 ? ... ? yn ? r ? np ? 0 ,故问题转化为求上述不定方程的非负整数解的个数,
从而知广告播放的方法数为 C( r ?np)?n?1 .
r ?np

一般地上楼的整个过程由 k 个 a 及 12-2k 个 b 组成, 相当于共跨 k+(12-2k)=12-k 步,其中有 k 步为
k a,故结果为 C12 ? k ,这里 k 可取 0,1,2,3,4,5,6,故最终结果为

?C
k ?0

6

k 12 ? k



巩 固 练 习
1.n 名同学(n?3)站成一圈,其中 A、B 两人不能相邻的站法有多少种? 解:n 名同学站成一圈有(n-1)!种站法,其中使 A、B 相邻的站法有 2×(n-2)!种,从而 A、B 不相 邻的站法为(n-1)!-2×(n-2)!=(n-3)(n-2)!种站法. 2.设集合 A、B 的并集为一个 n 元集,A≠B. (1) 若(A,B)与(B,A)视为不同的对,则这样的 A、B 共有多少个? (2) 若(A,B)与(B,A)视为相同的对,则这样的 A、B 共有多少个? 解:(1)设集合 A 中有 k 个元素,则集合 B 中必含有 A 中没有的 n-k 个元素,再加上 A 的 k 个

解法 3: 设走 n 次台阶的方法总数为 an , 对每种走法可划分为两类第一类: 第一步走 1 级, 有 a n ?1 种走法;第二类:第一步走 2 级,有 an?2 种走法,故 an ? an?1 ? an?2 ,且 a1 ? 1, a2 ? 2 ,故易得

a12 ? 233.
因 Fibonacci 数列 {Fn } 满足 F1 ? F2 ? 1, F3 ? 2 ,故 a n ? Fn ?1 ,由上面的一些方法还可知:

k k 元素中取 0 个、1 个、?k 个,故共有 C n 2 个,故总数为

?C
k ?0

n

k n

2 k = 3n 个,除去 A 与 B 相同(均为

7. n 个人 (n ? 3) 站成一圈,其中某指定的两人 A、B 肯定不相邻的站法有多少种? 答案: (n ? 1)!?2(n ? 2)!. 8.甲、乙两队各出 7 名队员按事先排好的顺序出场参加围棋擂台赛,双方先由一号队员比赛, 负者被淘汰,胜者再与负方 2 号队员比赛,??,直到一方队员全部淘汰为止,另一方获得胜利,形 成一种比赛过程,那么所有可能出现的比赛过程的种数是多少? 解:不妨先设甲方胜出,则问题等价于求方程 x1 ? x2 ? ... ? x7 ? 7 的非负整数解的个数,有
7 6 7 6 6 C7 ?7?1 ? C13 种,同理,乙方胜的比赛过程也有 C7?7?1 ? C13 种,故可能出现的比赛过程有 2C13 种.

全集)的 1 个,共 3 -1 个; (2)由题意,(A,B)与(B,A)一一对应,故结果为

n

1 n (3 ? 1) 个. 2

3.在一个正六边形的六个区域栽种观赏植物,如图,要求同一块中种同一植物,相邻的两块种 不同的植物,现有 4 种不同的植物可供选择,则有多少种不同的栽种 方案. 解:考虑 A、C、E 种同一种植物,此时共有 4×3×3×3=108 种; 考虑 A、 A F B C、E 种两种植物,此时共有 3×4×3×3×2×2=432 种方法;考虑 A、 C、E 种三
3 种 植 物 , 此 时 共 有 C4 × 2 × 2 × 2=192 种 方 法 ; 故 总 计 有

E

D

C

9.有男生 n ? m 人,女生 m 人( m, n ? 1 ),(1)这 n ? 2 m 个人排成一列,女生不相邻,首尾 都是男生,有多少种排法? (2))这 n ? 2 m 个人围成一圈,女生不相邻,有多少种排法?
m m 解:(1) (n ? m)! An ? m?1 ;(2)先作男生圆排列,然后插入,共 (n ? m ? 1)! An ? m .

108+432+192=732 种方案. 4.如图,矩形 ABCD 的边在网格线上,并且 AB 是 AD 的 k 倍(k 为正整数),考虑沿网格的边 从 A 到 C 所有可能的最短路径.证明:在这些路径中,含 AB1 的条数是含 AD1 的条数的 k 倍. 解:含 AB1 的最短路径,除 AB1 外,还应含 横向的
n m-1 节,纵向的 n 节,因此共有 Cm ? n?1 条,同理,

含 AD1

10.方程 2 x1 ? x2 ? x3 ? ... ? x10 ? 3 的非负整数解共有多少个? 解:由题意, x1 ? 0,1 ,故分情况讨论如下:
3 若 x1 ? 0 ,则 x2 ? x3 ? ... ? x10 ? 3 ,非负整数解的个数为: C9 ?3?1 ? 165; 1 若 x1 ? 1 ,则 x2 ? x3 ? ... ? x10 ? 1 ,非负整数解的个数为: C9 ?1?1 ? 9 .













m Cm ? n?1







C C

n m? n ?1 m m? n ?1

?

m! n ( ? n! m (?

1m ) ! ? ? k ,因此命题得证. 1n ) !

5.马路上有编号为 1,2,3,?,2005 的 2005 只路灯,为节约用电,现要求把其中的 200 只灯 关掉,但不能同时关掉相邻的两只或三只,也不能关掉两端的路灯,求满足条件的关灯方法共有多少 种? 解: 任意一种关灯的方法, 都对应着一种满足题设条件的亮灯与暗灯的排列, 于是总是转化为 1805 只亮灯中插入 200 只暗灯,且任何两只暗灯不相邻,而且不在两端,也就是在 1805 只亮灯所形成的
200 1804 个间隙中选 200 个插入暗灯,其方法有 C1804 种.

综上,非负整数解的个数为:165+9=174 个. 11.一个盒子里有 7 个分别标有号码 1,2,?,7 的球,每次取出一个,记下它的号码后再放回 盒子,共取(放)4 次,求 4 次中最大标号恰是 5 的取法数? 解:最大标号为 5,相当于从 1,2,?,5 中取,共取(放)4 次,共有 5 种取法;从中剔除四
4 次中最大标号均不是 5 的种数,结果为 5 ? 4 =369.
4

4

6.把 2005 个不加区别的小球分别放在 10 个不同的盒子里,使得第 i 个盒子中至少有 i 个球

(i ? 1,2,..., 10) ,问不同放法的总数是多少?
解:先在第 i 个盒子里放入 i 个球,这时共放了 1+2+?+10=55 个球,还余下 2005-55=1950 个球, 故问题转化为把 1950 个球任意放入 10 个盒子(允许有的盒子不放球),相当于一个不定方程的非负 整数解的个数问题,共有 C
1950 10?1950?1

12.已知集合 A ? z | z 2n?1 ? z, z ? C, n ? N , n ? 2 ,在复平面上,以 A 中的复数的对应点为顶 点可构成多少个直角三角形? 解:易求得 A ? 0,1, ? , ? ,??
2

?

?

?

2 n?1

?

,其中 ? ? e n (n?2)设各复数在复平面上对应点依次为 O、

i

?

?C

1950 1959

?C

9 1959 种.

A0、A1、A2、?、A2n-1,则 A0A1A2?A2n-1 为正 2n 边形,易知在 ?OAi A j 中以 Ai , Aj 为顶点的内角均为

锐角,所以,由 O、A0、A1、A2、?、A2n-1 为顶点的直角三角形可分为两类: 第一类:以 O 为直角顶点的直角三角形,不失一般性,可设 ?A0 OAK ? 90? ,则

?
2

?

k? ,所以 n

这说明这类直角三角形存在当且仅当 n 为偶数时, 这时, 这样的直角三角形有 2n 个; n ? 2k (k ? N ) , 第二类:不以 O 为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上,即由 A0、 A1、A2、?、A2n-1 构成,这些点可确定 n 条直径,于是可构成 n(2n ? 2) 个直角三角形 综上所述,由加法原理,所求直角三角形的总个数为 f (n) ? ?

?n(2n ? 2) ? 2n ? 2n 2 , n为偶数 . 2n(n ? 1), n为奇数 ?


相关文章:
高中数学竞赛讲义_排列组合与概率
高中数学竞赛讲义高中数学竞赛讲义隐藏>> 排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在第 1 类办法中有 m1 种不同的方法,在第 2 类办...
高中数学竞赛讲义_排列组合与概率
排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在第 1 类办法中有 m1 种不同的方法,在第 2 类办法中有 m2 种不同的 方法,??,在第 ...
高中数学竞赛讲义(十三)──排列组合与概率
高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在第 1 类办法中有 m1 种不同的方法,在第 2 类办 法中有 ...
高中数学完整讲义——排列与组合1.加法原理
高中数学完整讲义——排列与组合1.加法原理_数学_高中教育_教育专区。高中数学讲义 加法原理 知识内容 1.基本计数原理 ⑴ 加法原理 分类计数原理:做一件事,完成它...
高中数学竞赛讲义_组合
高中数学竞赛讲义_组合_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载 高中数学竞赛讲义_组合_学科竞赛_高中教育_教育专区。高中数学竞赛习题...
数学竞赛讲义组合计数
数学竞赛讲义组合计数_学科竞赛_高中教育_教育专区。数竞必备,组合计数 ...? 2 ?1,读作 n 的阶乘 m 无重排列: 从 n 个不同元素中任取 m 个不...
数学竞赛讲义组合7-21
数学竞赛讲义组合7-21_学科竞赛_高中教育_教育专区。第七讲 组合综合问题本讲概述...,a10 段反序,其它不变,得到新的排列,二者和数之差 S -S′=aj-1x9+xi...
高中数学竞赛讲义(13)排列组合与概率
高中数学竞赛讲义(13)排列组合与概率_学科竞赛_高中教育_教育专区。高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法...
高中数学竞赛_排列组合与概率【讲义】
高中数学竞赛_排列组合与概率【讲义】_学科竞赛_高中教育_教育专区。高中数学竞赛讲义第十三章 排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在...
高中数学完整讲义——排列与组合7.排列组合问题的常用...
高中数学完整讲义——排列与组合7.排列组合问题的常用方法总结1_数学_高中教育_...化学三 科竞赛,共有 90 种不同方案,那么男、女生人数分别是( ) A.男生 2...
更多相关标签: