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

6.3 排列与组合


§6.3 排列与组合
大量的计数问题呈现如下的类型:

(1) 对元素的有序的摆放数或有序的选择数进行计 数 a) 没有重复元素。 b) 允许元素重复。
(2) 对元素的无序的摆放数或有序的选择数进行计 数 a) 没有重复元素。

b) 允许元素重复。

6.3.1 基本的排列与组合
集合

的排列 n元集合S的一个r排列是指先从S中选出r个元素, 然后将其按次序排列。
一般用 P(n, r ) 或 Pnr 表示n元集合的r排列数。 定理 6.9 对于满足 r ? n 的正整数n和r,有

P(n, r ) ? n (n ? 1)?(n ? r ? 1) n! ? ( n ? r )!

要构造n元集合的一个r排列,可以在n个元素 证明: 中任取一个作为第一项,有n种取法;
在取定第一项后,第二项可以从剩下的n-1个元素 中任取一个,有n-1种取法;……; 同理,在前r-1项取定后,第r项有n-r+1种取法。 由乘法原理知 显然,

n! P(n, r ) ? n (n ? 1)?(n ? r ? 1) ? ( n ? r )!
(3)?? P(n, n) ? n ! (4)??0! ? 1

(1)?? P (n, r ) ? 0??( r ? n) (2)?? P(n,1) ? n??(n ? 1)

例 6.9 大家所熟知的“15迷宫”是将标有数字1到 15 的15个可滑动的小正方形装在一个4×4的正方形 框架上,剩下一个小的空方块。游戏是将15个小 方块以任一排列方式移动成如图6.2所示的初始位 置。现在问:这15个小方块在4×4的框架上有多 少种不同的排列方式? 1 2 3 4

5
9

6
10

7
11

8
12

13

14

15
图6.2

解: 原问题就是求将1,2,…,15放在4×4框架中

的16个小方块上而剩下一个空方块的方式数。
将空方块看作16,则原问题就变为1,2,…,16 放入16个各小方块中的方式数。 它等于{1,2, …,16}的全排列数, 即有 P (16,16) ? 16! 种不同的排列方式。

例 6.10 A单位有7位代表,B单位有3位代表, 排成一列合影,要求B单位3人排在一起。 问有多少种不同的排列方案?
解: B单位3个人的某一排列作为一个元素,

参加A单位进行排列,可得方案数为 (7 ? 1)! ? 8!
B单位的3人有 3! 种排列。 由乘法原理知,总排列方案数为 8!? 3!

例 6.11 若例 6.10中 B单位的3人不能相邻,且A 单位的2人排在两端,则有多少种不同的排列方案?
解:A单位7人共有 7! 种排列。 设 A1 A2 A3 A4 A5 A6 A7 是A的一个排列。 B单位3人中的第一人有6种选择 两端固定后,

A1 * A2 * A3 * A4 * A5 * A6 * A7
即上面*的位置。第二位为了不与第一位相邻,故 只有5种选择。第三位有4种选择。 故排列总数为 7!? 6 ? 5 ? 4 ? 604800

前面考虑的排列是在直线上进行的或者确切的 的说,是r线排列。 若在圆周上进行排列,结果又如何呢? 在一个r圆排列的任意两个相邻元素之间都有一个 位置,共有r个位置。 从这r个位置处将该圆排列断 开,并拉直成线排列。 或者换个说法,将r个r线排列

a1a2 ?ar ?1ar a2a3 ?ar a1 ?? ar a1 ?ar ?2ar ?1
的首位相连围成圆排列,得到的是同一个r圆排列.

定理 6.10 n元集合的r圆排列数为

1 n! P ( n, r ) ? r r (n ? r )!
例 6.12
10个男生和5个女生聚餐,围坐在圆桌旁, 任意两个女生不相邻的坐法有多少种? 解:

1 先把10个男生排成圆形,有 ? 10! ? 9! 种方法。 10

固定一个男生的排法,把5位女生插在10个男生 之间, 每两个男生之间只能插一个女生, 而且5个女生之间还存在着排序问题,

故可有 P (10,5) 种排法。 由乘法原则知,共有 9!? P (10,5) 种排法。

集合的组合
n元集合S的r组合是指从S中取出r个元素的一种

? n? r 无序选择, 其组合数记为 ? ? 或 C (n, r ) 或 Cn ?r? 定理 6.11 若 0 ? r ? n, 则

? n ? P(n, r ) n! ? ? ?? r! r !(n ? r )! ?r ?

证明: 设S是一n元集合,任取S的一个r组合, 将该r组合中的r个元素进行排列,可得到 P (r , r ) ? r !
个S中的r排列。 而且S中的任一r排列都可恰好通过将S中的某一r 组合排序而得到。

? n? 因此 P (n, r ) ? r !? ? ? ?r ? ? n ? P(n, r ) n! 即 ? ? ?? r! r !(n ? r )! ?r ?

显然,

? n? ? n? (1)??? ? ? 1, ? ? ? 1 ?0? ? n?

? n? (2)??? ? ? 0??? r ? n) ?r ?

例 6.13 系里欲将6名保送研究生推荐给3个单位, 每个单位2名,问有多少种方案? 解: 推荐给某个单位的两名学生的顺序是无关紧要的, 这是一个组合问题。 ? 6?

先从6名学生中选出2名给第一个单位,有 ? ?

? 2?

种选法。

? 4? 然后从余下的4名中选出2名给第二个单位,有 ? ? ? 2? ? 2? 种选法。 余下的2名学生给第三个单位,有 ? ? ? 2?
种选法。 由乘法原则知,共有

? 6? ? 4? ? 2? 6! ? 90 种方案。 ? ??? ??? ? ? ? 4 ? ? 2 ? ? 2 ? 2!2!2!

6.3.2

多重集合的排列与组合

多重集合的排列 前面讲的n元集合的r排列,是指从n个各不相同的 元素里,每次取出r个互不相同的元素进行排列, 而在现实生活中,并不一定是对不同的元素进行 排列。例如,对一组数据排序就是求它的一个排 列,而在这些数据中可能出现相同的数。为此,

引入多重集合的概念。 多重集合同一般集合一样,是一组对象的全体 只不过不像一般集合那样必须要求集合中每个元

素互不相同。

M 例如, ? {a, a, a, b, c, c, d , d , d , d } 是一个10个元 素的多重集合, 其中有3个a,1个b,2个c,4个d。
通常,可将M表示为 M ? {3 ? a,1 ? b, 2 ? c,4 ? d } 一般记多重集合为 M ? {k1 ? a1 , k2 ? a2 ,?, kn ? an }

a 其中, 1 , a2 ,?, an 为M中互不相同的元素, ki 为正整数, ki 为 a i 的重数,表示M中 ki 个 a i 称 (1 ? i ? n) 。ki 也可以取∞,表示M中有无限多个 a i
多重集合S的排列同一般集合的r排列一样,也 是从S中选出r个元素的有序选择。

定理6.12

多重集合M ? {?? a1 , ?? a2 ,?, ?? ak }
r

的r排列数为 k 。 证明: 在构造M的一个r排列时第一项有k种选择, 第二项有k种选择,……,第r项有k种选择。 由于M中的每个元素都是无限重的, 所以r排列中的任一项都有k种选择, r 且不依赖于前面已选择的项,故M的r排列数为 k 由上面的证明易知, 若M中每个元素的重数至少为r, 则定理的结论仍然成立。

定理6.13 多重集合 M ? {k1 ? a1 , k2 ? a2 ,?, kn ? an }

( k1 ? k2 ? ? ? kn )! 全排列数为 k1 ! k2 !? kn !
证明: 集合M中共有 k1 ? k2 ? ? ? kn 个元素。

a1 占集合M的全排列中的 k1 个位置。 ? k1 ? k2 ? ? ? k n ? ? 选取 a1 所占位置的方法数为 ? k1 ? ?
在确定了 k1 个 a1 的位置后,还有 k2 ? ? ? kn

个位置, 2 占集合M的全排列中的 k2 个位置, a
? k2 ? k3 ? ? ? kn ? 从中选取 k2 个a2 的位置的方法数为? ? k2 ? ? 同理,依次选取位置安排 a3 ,?, an ,

由乘法原理知,M的全排列数为 ? k1 ? k2 ? ? ? kn ?? k2 ? ? ? kn ? ? kn ? ? ?? ??? ? k1 k2 ? ?? ? ? kn ? (k1 ? k2 ? ? ? kn )! (k2 ? ? ? kn )! kn ! ? ? ??? k1!(k2 ? ? ? kn )! k2!(k3 ? ? ? kn )! kn ! (k1 ? k2 ? ? ? kn )! ? k1!k2!? kn !

例6.14 求不多于四位的二进制数的个数。 解: 此问题相当于多重集合 {? ? 0, ? ? 1} 的4排列问题 由定理6.12知,所求的二进制数个数为 2 ? 16
4

例6.15 设 S ? {3 ? a, 2 ? b,4 ? c} 求S的8排列的个数。 解:S的8排列可分为以下三类:

(1)??{2 ? a, 2 ? b,4 ? c} 的8排列, 8! ? 420 个数为 2!2!4! (2)??{3 ? a,1 ? b,4 ? c} 的8排列,

8! ? 280 个数为 3!1!4!
(3)??{3 ? a, 2 ? b, 3 ? c} 的8排列,

8! 个数为 ? 560 3!2!3!
因此,S的全部8排列的个数为

420 ? 280 ? 560 ? 1260

多重集合的组合
多重集合M的r组合是指从M中无序地选出r个元素 定理6.14 多重集合 M ? {?? a1 , ?? a2 ,?, ?? ak }

? k ? r ? 1? 的r组合数为 ? ? ? r ?
证明: 设多重集合M的某个r组合为

{ x1 ? a1 , x2 ? a2 ,?, xk ? ak }
则有 x1 ? x2 ? ? ? xk ? r

x 其中, 1 , x2 ,?, xk 为非负整数。
反之,若给出方程 x1 ? x2 ? ? ? xk ? r的一组非负 整数解 x1 , x2 ,?, xk ,则对应与M的一个r组合。 M的r组合与方程 x1 ? x2 ? ? ? xk ? r 所以, 的非负整数解构成一一对应,从而将求M的r组合 的问题转化为求方程 x1 ? x2 ? ? ? xk ? r 的非负 整数解。 方程 x1 ? x2 ? ? ? xk ? r 的非负整数解可表示成

长为 k ? 1 ? r 的0,1序列。

1 1 ? 1??0??1 1 ? 1?????1 1 ? 1??0 ????? ????? ?????
x1个 x2个 xk 个

其中,0的个数为k-1个。 该0,1序列是集合 {( k ? 1) ? 0, r ? 1} 的全排列。

方程 x1 ? x2 ? ? ? xk ? r 的解与 {( k ? 1) ? 0, r ? 1} 的全排列之间一一对应的, k ? r ? 1

? 从而多重集合M的r组合数为 ? ?

r

? ? ?

例6.16 求方程 x1 ? x2 ? x3 ? x4 ? 20 整数解的个数?其中 x1 ? 3, x2 ? 1, x3 ? 0, x4 ? 5 解: 设 y1 ? x1 ? 3, y2 ? x2 ? 1, y3 ? x3 , y4 ? x4 ? 5 代入方程 x1 ? x2 ? x3 ? x4 ? 20 可得

y1 ? y2 ? y3 ? y4 ? 11 x1 , x2 , x3 , x4 下界能够满足当且仅当 y1 , y2 , y3 , y4
是非负的。
方程 y1 ? y2 ? y3 ? y4 ? 11 的非负整数解的个数为

? 11 ? 4 ? 1 ? ? 14 ? ? ? ? ? ? ? 364 ? 11 ? ? 11 ?
同理,含有k种元素,且重数为 n1 , n2 ,?, nk 的多重集 S ? {n1 ? a1 , n2 ? a2 ,?, nk ? ak } 的r组合数
和方程 x1 ? x2 ? ? ? xk ? r 的整数解的个数相同, 其中 0 ? x1 ? n1 ,0 ? x2 ? n2 ,?,0 ? xk ? nk

6.3.3 二项式系数
? n? 表达式 ? ? 表示n元集合的r组合数。 ?r?
它有许多很奇妙的性质,关于它有许多恒等式。 由于它出现在下面所介绍的二项式定理中,所以 称其为二项式系数。在进行计算机算法分析时, 经常要用到二项式系数,有必要对其熟练掌握。

定理6.15

(二项式定理)

设n为一正整数,则对任意的x和y ,有
? n ? n ?1 ? n ? 2 n ? 2 ? n ? n?1 ( x ? y) ? y ? ? ? xy ? ? ? x y ? ? ? ? x y ? xn ? ?1 ? ?2? ? n ? 1? n ? n ? r n? r ? ? ? ?x y r ?0 ? r ? 证明:
n n

( x ? y )n ? ( x ? y )( x ? y )? ( x ? y ) 展开,直到没 将 ???? ????? ? ?
n个

括号为止。在展开时,每个因子中均可取x或y,

因此共有 2 项,这些项都可以写成 x y (0 ? r ? n) 可以在n个x+y因子中选出r个, 的形式。
n

r

n? r

从这r个因子中取x,而在另外的n-r个因子中取y, 如此得到 x r y n? r 项, ? n? r n? r 因此 x y 的系数等于n个因子的组合数,即 ? ? ?r? n ? n ? r n? r n 因此 ( x ? y ) ? ? ? ?x y r ?0 ? r ? 推论 n为一正整数,则对任意的x, n ? n? r n (1 ? x ) ? ? ? ?x r ?0 ? r ?

证明:在二项式定理中令y=1即可。

二项式系数的基本性质
本的性质:

? n? 当n,r均为非负整数,且 n ? r 时, ? 有一些最基 ? ?r? ? n? ? n ? (1) 对称关系 ? ? ? ? ? ?r ? ?n?r? ? n ? ? n ? 1? ? n ? 1? (2) 递推关系 ? ? ? ? ??? ? ? r ? ? r ? ? r ?1?
( n ? r ? 1)

注意: 在证明二项式系数的性质或恒等式时,一般可利 用下面三种方法。 1)用二项式系数的表达式。 2)利用二项式系数的组合意义。 3)利用二项式定理。 证明性质(1)对称关系。 证法一:利用二项式系数的表达式

? n? n! ?? ? ? ? r ? r !(n ? r )!

? n ? ? n? n! n! ?? ? ?? ? ?? ? n ? r ? (n ? r )![n ? (n ? r )]! r !(n ? r )! ? r ?
证法二:利用二项式系数的组合意义

? n? 因为 ? ? 表示n元集合S的r元组合数, ?r ?
或表示n元集合的r元子集的个数。

? n ? 同理, ? ? 表示集合S的n-r元子集的个数。 ?n?r?

设 S1 是集合S的r元子集,则 S ? S1 是S的n-r元子集,

且这种关系显然是1-1的对应的。 所以S的r元子集的个数等于S的n-r元子集的个数。

? n? ? n ? 因此,? ? ? ? ? ?r ? ?n?r?
证法三:利用二项式定理

? n ? r n? r ? ( x ? y ) ? ? ? ?x y r ?0 ? r ? n ? n ? r n? r n ( y ? x) ? ? ? ? y x r ?0 ? r ?
n n

( y ? x) ? ( x ? y)
n

n

? n ? r n? r n ? n ? r n? r ? ? ? ?x y ? ? ? ? y x r ?0 ? r ? r ?0 ? r ?
n

? n? ? n ? ?? ? ? ? ? ?r ? ?n?r?

证明性质(2)递推关系。 证法:利用二项式系数的组合意义 集合 S ? {a1 , a2 ,?, an } 的r元子集可以分成两类: 第一类r元子集含 a1 , 第二类r元子集不含 a1 第一类r元子集中的任一个去掉a1 后,就是 S ? {a1 } 的r-1元子集; 反过来,任给一个 S ? {a1 }的r-1元子 集,添上 a1 后,就是 S的r元子集, 故二者之间一一对应。

? n ? 1? 第一类r元子集共有 ? ? 个。 ? r ?1?

第二类r元子集就是 S ? {a1 } 的r元子集,

? n ? 1 ? 个。 共有 ? ? ? r ? ? n ? ? n ? 1? ? n ? 1? 因此,? ? ? ? ??? ? ? r ? ? r ? ? r ?1?

( n ? r ? 1)

由性质(2)可得如图6.3所示的杨辉三角形

? n? 许多关于 ? ? 的性质可通过考察杨辉三角形得到 ?r ?
(3)单峰性 当n为偶数时,有

?n ? ? n? ? n? ? n ? ? n? ? ? ? ??? ? n? ??? ? ? ? ??? ? ? ? 0 ? ?1 ? ? ? ? ? n ? 1? ? n ? ? 2?
当n为奇数时,有

? n ? ? n ? ? n? ? n? ? ??? ? ? ? ? ? n ? ? ? n? ? ? ? ? ? ??? ? n?1? ? n?1? ? ? ? ? ? ? ? ? ? 0 ? ?1 ? ? n ? 1? ? n ? ? 2 ? ? 2 ?

组合恒等式
有关二项式系数的恒等式至今已发现的就有上 千个,而且还在不断的发展。这些组合恒等式在 许多算法分析中起着重要的作用,这里给大家介 绍常用的几个。

等式 1
证明:

? n? ? n? ? n? n ? ? ? ? ? ??? ? ? ? 2 ? 0 ? ?1 ? ? n?

在二项式定理中令x=y=1即可。

? n? ? n? ? n? ? n? ? n? ? n? 等式 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0? ?2? ?4? ?1 ? ? 3 ? ? 5 ? n 证明: k ? n? 在二项式定理中令x= -1,y=1,得 ? (?1) ? ? ? 0 k ?0 ?k?
将上式整理一下即得等式 2。

由等式 1 可得

? n? ? n? ? n? ? n? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ?0? ?2? ?1 ? ? 3 ?

? n? ? n? n ?1 ? ? ? ? ? ?? ? 2 ?0? ?2?

? n? ? n? n ?1 ? ? ? ? ? ?? ? 2 ?1 ? ? 3 ?

? n? ? n? ? n? n ?1 等式 3 1 ? ? ? ? 2 ? ? ? ? ? ? n ? ? ? ? n ? 2 ?1 ? ?2? ? n? 证明: n ? n? i n ?(1 ? x ) ? ? ? ?x i ?0 ? i ?

?((1 ? x) )? |x?1 ? n(1 ? x)
n

n?1

|x?1 ? n2

n?1

? ? n ? n? i ? ? ? ? ? ?x ? ? i ?0 ? i ? ?

x ?1

n ? n ? i ?1 ? n? ? ? i ? ?x ? ?i? ? i ?1 ? i ? i ?1 ? i ? x ?1 n

? n? ? n? ? n? n?1 ?1 ? ? ? ? 2 ? ? ? ? ? ? n ? ? ? ? n ? 2 ?1 ? ?2? ? n?


相关文章:
排列组合的基本理论和公式
排列组合的基本理论和公式 排列与元素的顺序有关,组合与顺序无关.如 231 与 ...∴共 C(6.3)=20 种方法。 5 . 间接计数法 .(1)排除法 例 14. 三行三...
加乘原理和排列组合
加乘原理和排列组合排列与元素的顺序有关,组合与顺序无关.如 231 与 213 是...∴共 C(6.3)=20 种方法。 4.间接计数法.(1)排除法 例 14. 三 行三列...
6.3 数学1-100
6.3 数学1-100。GMAT 2011年六月 数学机经讨论稿更新 schedule: 6/3 6/3 6...PS:一道排列组合的 问一共 16 个人 6 个女人 10 个男人 抽出两个人是一 ...
第6章 资产组合计算
6.3 资产组合收益率与方差 .格式: [PortRisk,PortReturn]=portstats(ExpReturn...PortWts 每排是不同的资产组合 构造。 Portrand(Asset,Return,Point)点出了...
转一个判定组三 组六的计算方法
9-3=6,9-6=3,9-9=0,9+3=2,9+6=5[下期尾 6.3.0.2.5] 096 期...推荐几种另类的定位杀号法以及杀二码组合方法 2006-12-12 10:34:00 [排列 ...
数字逻辑第6章习题解答
6.3 简述 PAL 和 PLA 在结构上的主要区别。 PAL ...(1) 组合型输出结构 组合输出型结构适用于组合电路...因为这些模块的排列形 式和门阵列(GA)中单元的排列...
实验6 绘制图形与图文混排
3.插入自选图形文本框,并将它们组合成一个整体。 三、实验指导 首先将文档...图 6.3 “设置艺术字格式”之“颜色和线条”选项卡 图 6.4 “设置艺术字格式...
东北大学16春学期《行政组织学》在线作业123(标准答案)
衍射型 D. 重叠型 2.1.行政组织各要素的排列组合方式构成了行政组织的 ( )...必须 6.3.下列哪一项不是行政组织的内部目标? A. 机关管理 B. 绩效管理 C....
小学六年级数奥题及答案
当是102时,102/16=6.375 当是103时,103/16=6.4375 4.一个三位数的各位...排列组合问题 1.有五对夫妇围成一圈,使每一对夫妇的夫妻二人动相邻的排法有(...
更多相关标签:
火影忍者羁绊6.3组合 | 排列与组合 | 排列与组合的区别 | 排列与组合公式 | 高中数学排列与组合 | 排列与组合的计算公式 | 排列组合与概率 | 排列与组合ppt |