kl800.com省心范文网

组合数学讲义及课后答案 1章 排列组合


《组合数学》

第一章

组合数学基础

第 1章

组合数学基础

1、 排列组合的基本计数问题(研、本) 2、 计算多项式系数(研、本) 3、 排列组合算法(研)

1.1
(一) 背景

绪 论

起源:数学游戏 幻方问题:给定自然数 1, 2, …, n2,将其排列成 n 阶方阵,要求每 行、每列和每条对角线上 n 个数字之和都相等。这样的 n 阶 方阵称为 n 阶幻方。每一行(或列、或对角线)之和称为幻 方的和。 例:3 阶幻方,幻和=(1+2+3+…+9)/3=15。 (1) 存在性问题:即 n 阶幻方是否存在? (2) 计数问题:如果存在,对某个确定的 n,这样的幻方有 多少种? (3) 构造问题:即枚举问题,亦即如何构造 n 阶幻方。

8 1 6 3 5 7 4 9 2

2 7 6 9 5 1 4 3 8

图1.1.1 3 阶幻方 奇数阶幻方的生成方法: 奇数阶幻方最经典的填法是罗伯法。填写的方法是: 把 1(或最小的数)放在第一行正中; 按以下规律排列剩下的
1/69

《组合数学》

第一章

组合数学基础

(n× n-1)个数 (1)每一个数放在前一个数的右上一格; (2)如果这个数所要放的格已经超出了顶行那么就把它放在底 行,仍然要放在右一列; (3)如果这个数所要放的格已经超出了最右列那么就把它放在 最左列,仍然要放在上一行; (4)如果这个数所要放的格已经超出了顶行且超出了最右列, 那么就把它放在前一个数的下一行同一列的格内; (5)如果这个数所要放的格已经有数填入,那么就把它放在前 一个数的下一行同一列的格内。

一坐上行正中央,依次斜填切莫忘, 上边出格往下填,右边出格往左填, 右上有数往下填,右上出格往下填。 例:将 2,4,6,8,10,12,14,16,18 填入下列幻方:

例1.1.1 (拉丁方)36 名军官问题:有 1,2,3,4,5,6 共六个团队,从每个团队中分别选出具有 A、B、C、D、E、F 六 种军衔的军官各一名, 共 36 名军官。 问能否把这些军官排成 6×6 的方阵,使每行及每列的 6 名军官均来自不同的团队且具有不同 军衔? 本问题的答案是否定的。 反例: A1 B2 C3 D4 E5 F6 B2 C3 D4 E5 F6 A1 C3 D4 E5 F6 A1 B2
2/69

A1 B2 C3 D4 E5 F6 B3 C4 D5 E6 F1 A2 C5 D6 E1 F2 A3 B4

《组合数学》

第一章

组合数学基础

D4 E5 F6 A1 B2 C3 E5 F6 A1 B2 C3 D4 F6 A1 B2 C3 D4 E5

D2 E3 F4 A5 B6 C1 E4 F5 A6 B1 C2 D3 F6

例1.1.2 (计数——图形染色)用 3 种颜色红(r) 、黄(y) 、 蓝(b)涂染平面正方形的四个顶点,若某种染色方案在正方形旋 转某个角度后,与另一个方案重合,则认为这两个方案是相同的。 例如,对图 1.1.2 的涂染方案(a),当正方形逆时针旋转 90 o 时就变 为方案(b),因此,在正方形可旋转的前提下,这两种方案实质上 是一种方案。那么,我们要问:不同的染色方案共有多少种? y r b y b r b b

(a) (b)

图1.1.2 正方形的顶点染色

染色方案的总数为: 3 4 =81 种。 问题:计算不同的染色方案,但在图像可旋转条件下重合的 方案只能统计一次,不同的染色方案总数为(见第 6 章) L=

1 4 3 ? 3 2 ? 2 ? 3 =24 4

?

?

例1.1.3 (存在性) 不同身高的 26 个人随意排成一行, 那么, 总能从中挑出 6 个人,让其出列后,他们的身高必然是由低到高 或由高到低排列的(见第 5 章) 。 (二) 研究内容

算法分类: ? 第一类:数值算法。主要解决数值计算问题,如方程求根、
3/69

《组合数学》

第一章

组合数学基础

解方程组、求积分等,其数学基础是高等数学与线性代数。 ? 第二类:组合算法,解决搜索、排序、组合优化等问题, 其数学基础就是组合数学。 按所研究问题的类型,组合数学所研究的内容可划分为: ? 组合计数理论 ? 组合设计 ? 组合矩阵论 ? 组合优化 本课程重点:以组合计数理论为主,部分涉及其它内容。 (三) 研究方法

分类: 第一类:从组合学基本概念、基本原理出发解题的所谓常规 方法(利用容斥原理、二项式定理、Pólya 定理解计数问题;解 递推关系的特征根方法、母函数方法;解存在性问题的抽屉原理 等) 。 第二类:通常与问题所涉及的组合学概念无关,而对多种问 题均可使用。例如: (1) 数学归纳法:前提是已知问题的结果。 (2) 迭代法 例. 如已知数列 ?hn ?满足关系 ? 表达式。 直接迭代即得:

? hn ? 2hn?1 ? 1 , ,求 hn 的解析 h ? 1 ? 1

hn ? 2hn ? 1 ? 1
= 2?2hn ? 2 ? 1? +1= 22 hn ? 2 ? 2 ? 1 = 22 ?2hn ? 3 ? 1? ? 2 ? 1 = 23 hn? 3 ? 22 ? 2 ? 1
4/69

《组合数学》

第一章

组合数学基础

?
= 2n ? 1 h1 ? 2n ? 2 ? 2n ? 3 ? ? ? 22 ? 2 ? 1 = 2n ? 1 (3) 一一对应技术 原理:建立两类事物之间的一一对应关系,把一个较复杂的 组合计数问题 A 转化成另一个容易计数的问题 B,从而利用对 B 的计数运算达到对 A 的各种不同方案的计数。 思路:将未解决问题的模式转化为一种已经解决的问题模式。 (4) 殊途同归方法 原理:从不同角度讨论计数问题,以建立组合等式。 应用:组合恒等式的证明(也称组合意义法) 。 (5) 数论方法 特别是利用整数的奇偶性、整除性等数论性质进行分析推理 的方法。

组合数学用的较多的是方法(3)与(4) 。 例1.1.4 有 100 名选手参加羽毛球比赛,如果采用单循环淘 汰制,问要产生冠军共需要进行多少场比赛? (解) 常规思路:50+25+12+6+3+2+1=99 场 采用一一对应方法:每场比赛产生一个失败者,且每个失败 者只能失败一次。反之,要淘汰一个选手,必须恰好经过一场比 赛。 结论:失败者与比赛场次之间一一对应,故应该比赛 99 场。 一般情况:单循环淘汰制的比赛,若有 n 个选手参考比赛, 则须经过 n-1 场比赛,方可产生冠军。
5/69

《组合数学》

第一章

组合数学基础

例1.1.5 设某地的街道将城市分割成矩形方格,某人在其住 处 A(0,0)的向东 7 个街道、向北 5 个街道的大厦 B(7,5)处 工作(见图 1.1.3) ,按照最短路径(即只能向东或向北走) ,他每 次上班必须经过某 12 个街段,问共有多少种不同的上班路线? (解) (1)将街道抽象为等长的,其东西方向的长为 x,南 北方向的长为 y。从 A(0,0)点出发,向东走一段为 x,向北走 一段为 y。 B(7,5)

A(0,0) 图1.1.3 最短路径

(2)对应为(元素可重复的)排列问题:一条从 A 到 B 的 路线对应一个由 7 个 x,5 个 y 共 12 个元素构成的排列。 蓝色路径 <——> xyyxxyyxxxxy 反之,给定一个排列,按照 x、y 的含义,必对应一条从 A 到 B 的行走路线。例如,排列

yxxyyyyxxxxx <——> 红色路径
结论:从 A(0,0)到 B(7,5)的最短路径与 7 个 x,5 个 y 的排列一一对应。 (3)求解:再对应为(元素不重复的)排列问题 N= C7 ? 5 = C12 =
6/69

5

5

12! =792 5!?7!

《组合数学》

第一章

组合数学基础

(4)一般情形:从(0,0)点到达(m,n)点的不同的最 短路径数为 N= C m ? n
m

1.2 两 个 基 本 法 则
1.2.1 加 法 法 则 (一) 加法法则

? 常规描述:如果完成一件事情有两个方案,而第一个方案 有 m 种方法,第二个方案有 n 种方法可以实现。只要选择 任何方案中的某一种方法,就可以完成这件事情,并且这 些方法两两互不相同。则完成这件事情共有 m+n 种方法。 ? 集合描述:设有限集合 A 有 m 个元素,B 有 n 个元素,且 A 与 B 不相交,则 A 与 B 的并共有 m+n 个元素。 ? 概率角度描述:设事件 A 有 m 种产生方式,事件 B 有 n 种 产生方式,则事件“A 或 B”有 m+n 种产生方式。当然 A 与 B 各自所含的基本事件是互相不同的。 (二) 应用

例1.2.1 某班又男生 18 人,女生 12 人,从中选出一名代表参 加会议,问共有多少种选法? (解) 用集合 A 表示男生,B 表示女生,则该班中的学生要 么属于 A,要么属于 B。根据加法法则,全班共有 18+12=30 个 学生,故有 30 种选法。 例1.2.2 用一个小写英文字母或一个阿拉伯数字给一批机器 编号,问总共可能编出多少种号码? (解) 26+10=36 个。 其中英文字母共有 26 个,数字 0~9 共 10 个

7/69

《组合数学》

第一章

组合数学基础

1.2.2 乘 法 法 则 (一) 乘法法则

? 常规描述:如果完成一件事情需要两个步骤,而第一步有 m 种方法、第二步有 n 种方法去实现。则完成该件事情共 有 m·n 种方法。 ? 集合描述:设有限集合 A 有 m 个元素,B 有 n 个元素,且 A 与 B 不相交, a ? A, b ? B ,记 ?a , b ? 为一有序对。所有 有序对构成的集合称为 A 和 B 的积集(或笛卡儿乘积) , 记作 A ? B 。那么, A ? B 共有 m ? n 个元素。

?a, b? a ? A, A? B = ?

b ? B?

? 概率角度描述:设离散型随机变量 X 有 m 个取值,Y 有 n 个取值,则离散型随机向量(X,Y)有 m ? n 种取值可能。 (二) 应用

例1.2.3 仍设某班有男生 18 人,女生 12 人,现要求从中分别 选出男女生各一名代表全班参加比赛,问共有多少种选法? (解) 用集合 A 表示男生,B 表示女生,那么,根据乘法法则, 共有 18 ? 12 ? 216 种选法。 例1.2.4 给程序模块命名,需要用 3 个字符,其中首字符要求 用字母 A~G 或 U~Z,后两个要求用数字 1~9,问最多可以给多少 种程序命名? (解) 首先,由加法法则,首字符共有 7 ? 6 ? 13 种选法。其 次,再由乘法法则,最多可以产生 13 ? 9 ? 9 ? 1053个不同的名称。 例1.2.5 从 A 地到 B 地有 n1 条不同的道路,从 A 地到 C 地有

n2 条不同的道路,从 B 地到 D 地有 m1 条不同的道路,从 C 地到 D 地有 m 2 条不同的道路,那么,从 A 地经 B 或 C 到达目的地 D
共有多少种不同的走法? 解 首先,由乘法法则,从 A 地经 B 到达 D 地共有 n1 × m1 种 走法, 由 A 经 C 到达 D 共有 n2 × m 2 种走法,再由加法法则知, 从
8/69

《组合数学》

第一章

组合数学基础

A 地经 B 或 C 到达 D 地共有 n1 m1 + n2 m 2 种不同的走法。 例

2×3+3×4=18

1.3

排列与组合

1.3.1 相 异 元 素 不 允 许 重 复 的 排 列 数 和 组 合 数 (一) 计算公式

从 n 个相异元素中不重复地取 r 个元素的排列数和组合数分 别为: 排列: Pnr ? P?n, r ? ? n?n ? 1?? ?n ? r ? 1? ? 组合:
n! ?n ? r ?!

(1.3.1) (1.3.2)

r ? n ? Pn n! ? ? ? ? Cr ? C n , r ? ? n ? r ? r! ? ?n ? r ?! r! ? ?

例:n=5,r=3,即元素为 1,2,3,4,5 排列:134,431,143,……, 254,425,…… 组合:134,245,…… 特点:排列考虑顺序,组合则不然。
9/69

《组合数学》

第一章

组合数学基础

(二)

数学模型

(1)排列问题:将 r 个有区别的球放入 n 个不同的盒子,每 盒不超过一个,则总的放法数为 P(n,r)。 (2)组合问题:将 r 个无区别的球放入 n 个不同的盒子,每 盒不超过一个,则总的放法数为 C(n,r)。

对应关 系 元素和 位置编 号 排列 1 排列 2 排列 3 排列 4 排列 5 组合 1 组合 2

元素 ? 盒子 1 A C A A B ● ● ● 2 3 B B C 4 C A B C A ● ● 5

位置 ? 球 AB C 134 431 143 254 425 134 245

B C ●

1.3.2 相 异 元 素 允 许 重 复 的 排 列 (一) 问题

从 n 个不同元素中允许重复地选 r 个元素的排列, 简称 r 元重 复排列。其排列的个数记为 RP(∞,r)。 (二) 模型

将 r 个不相同的球放入 n 个有区别的盒子,每个盒子中的球 数不加限制而且同盒的球不分次序。

10/69

《组合数学》

第一章

组合数学基础

对应关 系 元素和 位置编 号 排列 1 排列 2 排列 3 排列 4 排列 5

元素 ? 盒子 1 AB CB AC AB C B 2 3 4 C A B A C 5

位置 ? 球 AB C 114 433 343 222 425

(三)

计算公式 RP(∞,r)= n r 。

(四)

集合描述方式

设无穷集合 S ? ? ? ? e1 , ? ? e2 , ?, ? ? en ?, 即 S 中共含有 n 类 元素,每个元素有无穷多个,从 S 中取 r 个元素的排列数即为 RP(∞,r)。 不 重 复 排 列 : S = ? e1 , e2 , ?, en ?。 1.3.3 不 尽 相 异 元 素 的 全 排 列 (一) 问题

? 1 ? e1 ,

1 ? e2 , ? , 1 ? en

?



有 限 重 复 的 排 列 ( 或 称 部 分 排 列 ): 设 S ? ? n1 ? e1 , n2 ? e2 , ?, nt ? et ?,即元素 e i 有 ni 个(i=1,2,…,t) , 且 n1 ? n2 ? ? ? nt ? n , 从 S 中任取 r 个元素, 求其排列数 RP(n, r)。 (二) 模型

将 r 个有区别的球放入 t 个不同的盒子,而每个盒子的容量是
11/69

《组合数学》

第一章

组合数学基础

有限的,其中第 i 个盒子最多只能放入 ni 个球,求分配方案数。 例: S={2·1,4·2,1·3,3·4,2·5} ={1,1,2,2,2,2,3,4,4,4,5,5} 对应关系 元素和位置编号 排列 1 排列 2 排列 3 排列 4 排列 5 AB C B A C 1 AB CB AC 元素 ? 盒子 2 3 4 C A B 5 位置 ? 球 AB C 114 433 343 222 425

说明:相对于前两种情况而言,此处讲的是有限重复的排列问 题, 即相异元素不重复的排列强调的是不重复, 即盒子的容量为 1; 允许重复的排列实际上针对的是无限重复,即盒子的容量无限。 二者都是极端的情况。而有限重复问题恰好介于两者之间,即盒 子的容量有限。 (三) (1) (2) 特例

r =1:RP(n,1)=t r =n(全排列)
RP?n, n ? ?

n! (1.3.3) n1 ! n2 !? nt ! 即先视为 n 个不同元素的全排列,共有 n!种。但每个排列实际重 复统计了 n1 ! n2 !?nt ! 次。原因是当元素不同时,同类元素互相交 换位置,对应不同的排列。而当同类元素相同时,针对每个确定 的排列,同类元素互相交换位置,该排列不变。

12/69

《组合数学》

第一章

组合数学基础

(3)

t=2, RP?n, n ? ?

? n? n! ? ?? ? n n1 ! n2 ! ? ? 1?

(4) (5)

ni =1,即不重复的排列
ni ? ? ,即重复排列

1.3.4 相 异 元 素 不 允 许 重 复 的 圆 排 列 (一) 圆排列

例1.3.1 把 n 个有标号的珠子排成一个圆圈,共有多少种不同 的排法? (解)典型的圆排列问题。 条件:对于围成圆圈的 n 个元素,同时按同一方向旋转,即 每个元素都向左(或向右)转动一个位置,虽然元素的绝对位置 发生了变化,但相对位置未变,即元素间的相邻关系未变,这样 的圆排列认为是同一种,否则便是不同的圆排列。 解法一:先令 n 个相异元素任意排成一行(称为线排列) ,共 有 n!种排法,再将其首尾相接围成一圆,当圆转动一个角度时, 对应另一个线排列, 当每个元素又转回到原先的位置时, 相当于 n 个不同的线排列,故圆排列数为 CP(n,n)=

P ?n, n ? =(n-1)! n

(1.3.4)

13/69

《组合数学》

第一章

组合数学基础

32541 25413 54132 41325 13254 解法二:先取出某一元素 k,放于圆上某确定位置,再令余下 的 n-1 个元素作成一个线排列, 首尾置于 k 的两侧构成一个圆排 列同样可得到 CP(n,n)=(n-1)!。 3 1 2 3 2 5

4 (a)

5

1 (b)

4

例1.3.2 从 n 个相异元素中不重复地取 r 个围成圆排列,求不 同的排列总数 CP(n,r)。 (解)要完成这个圆排列,需先从 n 个元素中取 r 个,再将其 组成圆排列,故 CP(n,r)= (二) 项链排列

n! P ?n , r ? = r ?n ? r ?! r

(1.3.5)

例1.3.3 将 5 个标有不同序号的珠子穿成一环,共有多少种不 同的穿法? (解)典型的项链排列问题。 首先,由例 1.3.1 知,5 个相异元素的圆排列共有(5-1)!=24
14/69

《组合数学》

第一章

组合数学基础

种。其次,对于圆排列而言,将所穿的环翻过来,是另一种圆排 列,但对于项链排列,这仍然是同一个排列(如图 1.3.1 所示) , 故不同的排法共有 24/2=12 种。 一般情形,从 n 个相异珠子中取 r 个穿成一个项链,共有

n! P ?n , r ? = 2r 2r ?n ? r ?!
种不同的穿法。 3 1 2 2 3 1

(1.3.6)

4 (a)

5

5 (b)

4

图 1.3.1 项链排列

允许重复的圆排列:情况复杂(参见反演公式相关内容) 。

1.3.5 相 异 元 素 允 许 重 复 的 组 合 (一) 问题

设 S ? ? ? ? e1 , ? ? e2 , ?, ? ? en ?,从 S 中允许重复地取 r 个元素构成组合,称为 r 可重组合,其组合数记为 RC(∞,r)。 (二) 抽象

将 S 的 n 个不同元素分别用数字 1,2,…,n 来表示。
15/69

《组合数学》

第一章

组合数学基础

例: (三)

n=5,r=4 计算公式

1111,1122,1345,5555

所取出的 r 个元素从小到大设为 a1,a2,… ar,则 ai 满足: 1≤a1≤a2≤…≤ar≤n 令 则 bi=ai+(i-1),i=1,2,…,r 1≤b1<b 2<…<br≤n+(r-1)

结论: 与从 n+r-1 个相异元素中不允许重复地取 r 个元素的 组合方案一一对应。从而

RC??, r ? ? C?n ? r ? 1, r ? ?
例: n=5,r=4 分类 元素 重复组合 1,2,3,4,5 1111 1122 2245 5555

?n ? r ? 1?! r! ?n ? 1?!
不重复组合

(1.3.7)

1,2,3, ,5,6,7,8 1234 1245 2368 5678

(四)

模型

重复组合的模型是将 r 个无区别的球放入 n 个不同的盒子, 每个盒子的球数不受限制。 (五) 应用

例1.3.4 不同的 5 个字母通过通信线路被传送,每两个相邻字 母之间至少插入 3 个空格,但要求空格的总数必须等于 15,问共 有多少种不同的传送方式?
16/69

《组合数学》

第一章

组合数学基础

(解)将问题分为三步求解: (1)先排列 5 个字母,全排列数为 P(5,5)=5!。 (2) 两个字母间各插入 3 个空格, 将 12 个空格均匀地放入 4 个间隔内,有 1 种方案。 (3)将余下的 3 个空格插入 4 个间隔:即将 3 个相同的球放 入 4 个不同的盒子,盒子的容量不限。即从 4 个相异元素中可重 复地取 3 个元素的组合数 RC ??,3? ? C ?4 ? 3 ? 1,3? ? 20 。

c △△△ b △△△ d △△△ e △△△ a
方案 1 方案 2 (4)总方案数 L=5! ·1·20=2400 1.3.6 不 尽 相 异 元 素 任 取 r 个 的 组 合 问 题 (一) 问题 △△ △ △△△

设 集 合 , S ? ? n1 ? e1 , n2 ? e2 , ?, nt ? et ? n1 ? n2 ? ? ? nt ? n ,从 S 中任取 r 个,求其组合数 RC(n,r)。 (二) 组合数

设多项式

?? x = ? ?1 ? x ? x
t ni j

t

2

? ?? x

ni

i ?1 j ? 0

i ?1

?= ? a x
n r ?0 r

r

则 RC(n,r)就是多项式中 x r 的系数,即 RC(n,r)= a r (三) 应用

例1.3.5 整数 360 有几个正约数?
17/69

《组合数学》

第一章

组合数学基础

(解) (1) 分解 360 为素因子的幂的乘积 360=23×32×5 (2)正约数 1=20×30×50,2=2×30×50,3=20×3×50, 5=20×30×5,22=22×30×50,6=2×3×50=3×2, … 180=22×32×5,360=23×32×5 结论: 正整数 d 是 360 的正约数 ? d= 2a 3b 5c 且 0≤a≤3, 0≤b≤2,0≤c≤1。

? 3,1 ?5?的 6 个元 (3)问题转化:即从集合 S ? ? 3 ? 2,2 素中任取 0 个、1 个、……、6 个的组合数之和。
(4)求解:构造多项式 P6 (x)=(1+x+x2+x3)(1+x+x2)(1+x) =1+3x+5x2+6x3+5x4+3x5+x6 求各项系数之和: L= ? RC ?6, i ? =1+3+5+6+5+3+1=24
i ?0 6

故 7 不是约数,16= 2 4 也不是约数。

简单方法:多项式 P6(x)的系数之和实质上就是求 P6(1)。即 P6(x)=

? RC ?6, i ? =4×3×2=24
i ?0

6

(5)一般结论:设正整数 n 可以因子分解为 n= p1 1 p2 2 ? pk k , 则 n 的正约数个数为 L= ?? 1?1???? 2?1??? k ?1? ( 四 ) 习 题 : 18 , 21
18/69

?

?

?

《组合数学》

第一章

组合数学基础

1.4
(一) 归纳法

组合等式及其组合意义

组合等式的证明方法大致可归纳为以下三种:

(二) 组合意义法: 是指借助于阐明等号两端的不同表达式实 质上是同一个组合问题的方案数(即殊途同归法) ,或者 虽是两个不同组合问题的方案数,但二者的组合方案之 间存在着一一对应关系,因此等式两端必须相等,从而 达到证明等式成立的目的。对于恒等式的实质揭露得更 为深刻。 (三) 母函数法:利用无穷级数(包括有限时的多项式)证明 有关组合等式。是产生和证明组合恒等式的普遍方法。 等式1 对称关系式 C(n,r)=C(n,n-r) (1.4.1) 组合意义 从 n 个元素 ?a1 , a2 ,?, an ? 中取走 r 个,必然余下 n -r 个,故从 n 取 r 的组合与从 n 取 n-r 的组合一一对应。 等式2 加法公式 C(n,r)=C(n-1,r)+C(n-1,r-1) (1.4.2) (一)组合意义:从 n 个元素 ?a1 , a2 ,?, an ? 中取 r 个组合,就 其中某个元素,不妨设为 a1 来看,全体组合可分为两类: (1) 每次取出的 r 个元素中都含有 a1, 这一类组合可视为从 剩下的 n-1 个元素中任取 r-1 个元素,然后再加上 a1 而构成的 组合,其组合数为 C(n-1,r-1)。 (2) 不含元素 a1,这类组合可视为从其余 n-1 个元素中任 取 r 个元素的组合,其数目为 C(n-1,r)。 两类情况互不重复,由加法法则,式(1.4.2)成立。 (二)例:从{1,2,3,4,5}中取 3 个的组合情况为: 第一类(包含元素“1” ) : 123,124,125,134,135,145
19/69

《组合数学》

第一章

组合数学基础

第二类(不包含元素“1” ) : 234,235,245,345 (三)路径问题:加法公式(1.4.2)的等价形式是 C(m+n, m)=C (m+n-1, m) +C (m+n-1, m-1) (1.4.3) 组合意义:从(0,0)点到(m,n)点的路径数等于从(0,0) 点分别到(m,n-1)点和(m-1,n)点的路径数之和。 B(m,n)

A(0,0)

等式3 乘法公式 C(n,k) C(k,r)=C(n,r) C(n-r,k-r) 组合意义 考虑等式 C(n,n-k) C(k,k-r) C(r,r) =C(n,r) C(n-r,n-k) C(k-r,k-r) (1.4.5) (1.4.4)

左端: “将 n 个元素分为 3 堆,要求第一堆有 n-k 个元素,第二 堆有 k-r 个,那么,第三堆就只有 r 个元素”的组合方案数。 右端:另一个类似的组合问题“将 n 个元素分为 3 堆,要求第三 堆有 r 个元素,第二堆有 n-k 个,第一堆有 k-r 个元素”的组 合方案数。 两个组合问题等价,故其方案数亦相等。

20/69

《组合数学》

第一章

组合数学基础

等式4

C(n+r+1,r)=

? C ?n ? i , i ?
i ?0

r

= C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2) +C(n+r-3,r-3)+…+C(n,0) (1.4.6) 或 C(n+r+1,r)=

? C ?n ? i , n ?
i ?0

r

= C(n+r,n)+C(n+r-1,n)+C(n+r-2,n) +…+C(n,n) (1.4.7) (一)组合意义:从 n+r+1 个元素 ?a1 , a 2 , ?, a n? r ?1 ?中取 r 个的组合情况,分类统计: (1) 将所有组合针对 a1 分为两类: 即所取 r 个元素中含元素 a1 或不含元素 a1。对不含元素 a1 的情形,相当于从 n+r 个元素 ?a 2 , a 3 ,?, a n? r ?1 ?中取 r 个的组合,其组合数为 C ?n ? r , r ? ; (2) 仿照(1) ,再将含有元素 a1 的所有组合针对 a2 分为两 类:即所取 r 个元素中含 a2 或不含 a2,同样考虑不含 a2 的情形, 这又相当于从除去 a1、 a2 后的 n+r-1 个元素 ?a 3 , a 4 , ? , a n? r ?1 ?中 取 r-1 个, 再加上 a1 而构成组合, 其组合数为 C(n+r-1, r-1); (3) 同法,r-1 组合中含元素 a1、a2,但不含 a3 的组合数 为 C(n+r-2,r-2); 组合中含元素 a1、a2、…、ar-1,但不含 ar 的组合数为 C(n +1,1);

?r ?

?

?r ? 1?
=C(n,0) .

组合中含元素 a1、a2、…、ar 的组合数为 C(n+1,0)

(二)说明:实际上,组合等式 3 是等式 2 的推广,等式 2 只 是将 r 组合分为两类,而等式 3 则是分为 r+1 类来考虑问题。
r r ?1 Cr n ? r ?1 = C n ? r ? C n ? r

= C n? r ? C n? r ?1 ? C n? r ?1
21/69

r

?

r ?1

r ?2

?

《组合数学》

第一章

组合数学基础

= C n? r ? C n? r ?1 ? C n? r ? 2 ? C n? r ? 2 =……

r

r ?1

?

r ?2

r ?3

?
0

= C n? r ? C n? r ?1 ? C n? r ? 2 ? ? ? C n?1 ? C n?1 = C n? r ? C n? r ?1 ? C n? r ? 2 ? ? ? C n?1 ? C n (三)相应的路径问题: (r,n+1) … … … … … (0,0)
r r ?1 r ?2 1 0

r

r ?1

r ?2

?

1

?

等式5 Vandermonde(范德蒙)恒等式
r ? m ? n? ? n ?? m ? ? ? ? = ? ? r ? ?i? ?? ?r ? i? ? ? ? i ? 0 ? ?? ? ? n ?? m ? ? n ?? m ? ? n ?? m ? ? ? ? ? ? ? ? ? ? ? ? ? =? ? 0 ?? r ? ? 1 ?? r ? 1 ? ?r? ?? ?0? ? , r≤min(m,n) ? ?? ? ? ?? ? ? ?? ?

(1.4.8) 组合意义 现有 n 个相异的红球,m 个相异的蓝球,从 n+m 个球中取 r 个的组合,其结果必是下列情形之一:有 i 个红球,r -i 个蓝球 (i=0,1, …,r) 。 对固定的 i, 应有 C 选法。 特例 当 m=r 时,有
22/69

?n, i ?C ?m, r ? i ? 种

《组合数学》

第一章

组合数学基础

? n ?? r ? ? n ? r ? ? n ?? r ? ? n ?? r ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ?r? ?? ? 0? ? ? r ? ? 0 ?? r ? ? 1 ?? r ? 1 ? ? ? ?? ? ? ? ? ?? ? ? ?? ? n ? ? r ? ? n ?? r ? ? n ?? r ? ? ? ? ? ? ? ? ? =? ? ? ? ? ? 0 ? ? 0 ? ? 1 ?? 1 ? ?r? ?? ?r? ?, ? ? ? ? ? ?? ? ? ?? ? r ? n ?? r ? =?? ?i? ?? ?i? ? i ? 0 ? ?? ?
等式6 和式公式

r≤n (1.4.9)

? C ?n, i ? ? 2 n
i ?0

n

(1.4.10)

组合意义 对 n 个元素而言,每一个元素都有“取”与“不取” 两种可能,并由此构成所有状态。根据乘法法则,其总数为 2 n 。 它等于从 n 个元素中分别取 0 个,1 个,……,n 个元素的总组合 数。 例 组合 φ
e1 e 3 e 6 e1 e 2 e 3 e 4 e 5 e 6 e1

e2

e3

e4

e5

e6

不取 不取 不取 不取 不取 不取 取 取 不取 取 取 取 不取 不取 取 取 取 取

等式7

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

(1.4.11)

组合意义 n 个元素中取 r 个组合,r 为奇数的组合数目等于 r 为偶数的组合数(包括 r=0) 。 利用一一对应:从 n 个元素中任意取定某一个元素 a,所有 r 组合可以分为含有 a 和不含 a 两类。 设 r 为奇数(r≥1) ,若某个组合中含有元素 a,则去掉 a 后就 得一个 r-1 为偶数的组合,反之,设 r 为偶数(r≥0) ,同样可将 相应的组合通过去掉 a 或加上 a 而对应唯一的一个奇数组合。
23/69

《组合数学》

第一章

组合数学基础

例如,n=4 r 为奇数的 组合 r 为偶数的 组合 a φ abc bc abd bd acd cd b ab c ac d ad bcd abcd

1 2 n n?1 等式8 (1.4.12) Cn ? 2 Cn ? ? ? n Cn ? nC 2 n?1 组合意义 从 n 名先生、n 名太太中选出 n 人,这 n 人中有 一人担任主席,并且必须为太太,考虑有多少种选法。

? ?

2

? ?

2

? ?

2

1 选法 1:先选一名太太任主席有 C n ? n 种方法,再从其余的 n ?1 n ?1 2n-1 人中选 n-1 人有种 C 2 n ?1 方法。所以共有 nC 2 n ?1 种选法。

选法 2:对于 k=1,2,…,n,先从 n 名太太中选出 k 人,并从 k
k 人中选一人任主席,有 kC n 种方法,然后再从 n 名先生中选 n-k n? k k ? Cn 人,有 C n 种方法(即在 n 名先生中选 k 人不去充当“代

表” ) 。选法总数=

? k C nk
k ?1

n

? ?

2



等式9 设 r,M 都是自然数,M≥r 则有
r M ?r r M ? r M ? r ?1 r ? ? ? ? ? M M M ?1 M M ?1 M ? 2 M ? r M ? r ?1 1 r ? ?? ? ? ? ?1 M M ?1 r ?1 r

(1.4.13)

组合意义 设袋中有 M 个大小相同的球, 其中有 r 个是白色, 其余的是黑色。每次摸出一个球,不放回去,直至摸到白球为止。 这是一个必然事件(迟早会摸到白球) ,所以概率为 1。 另一方面, 第一次摸到白球的概率为 第二次摸到白球的概率为

M ?r r ? ,??,第 k 次才摸到白球的 M M ?1
24/69

r 。 第一次未摸到白球, M

《组合数学》

第一章

组合数学基础

概率为

M ? r M ? r ? 1 M ? r ? ?k ? 2? r , ?k ? 2,3,?, M ? r ? 1? ? ? ? M M ?1 M ? ?k ? 2? M ? ?k ? 1?
因此,摸到白球的概率为式(1.4.13)左端,从而式(1.4.13)成 立。

等式10 当 n≥m 时,
n? m k ?0 m n? m m ? Cn ? C nm? k C m ?k ? 2

(1.4.14)

组合意义 考虑从 n 人中选出 m 名正式代表及若干名列席代 表的选法(列席代表人数不限,可以为 0) 。
m 一方面,先选定正式代表,有 C n 种方法,然后从 n ? m 人中

选列席代表,有 2 n? m 种方法。因此共有
m 2 n? m C n

(1.4.15)

种选法。 另一方面,可以先选出 m+k 人(k=0,1,…,n-m),然后再从 中选出 m 名正式代表,其余的 k 人为列席代表,对每个 k,这样
m?k m C m ? k 种,从而,总选法的种数为 的选法有 C n
n? m k ?0 m ? C nm ? k C m ?k

(1.4.16)

综合式(1.4.15) 、 (1.4.16)即得式(1.4.14) 。

1.5
(一) (1) Newton 二 项 式 二项展开式

多项式系数

当 n 是正整数时,Newton 二项式定理
25/69

《组合数学》

第一章

组合数学基础

? ?a ? b ?n ? ? ? ?
n

n ? r n? r ? ?a b r r ?0 ? ?

(1.5.1)

的右端称为二项式(a+b)n 的展开式,而组合数 ? ? ? ? =C(n,r)叫做 二项式系数。 (2) 组合意义

? n? ?r?

将 n 个相异的球放入两个盒子, 其中要求 a 盒放入 n1=r 个, b 盒放入 n2=n-r 个,且同盒的球不分次序,则方案数为

n! n! = n1 !?n2 ! r!??n ? r ?!
即 a r b n? r 项的系数为组合数 ? ? ? ?。 例
? n? ?r?

?a ? b?2 =(a+b)(a+b)=aa+ab+ba+bb= a 2 ? 2ab ? b 2
?a ? b?3 =(a+b)(a+b)(a+b)=(aa+ab+ba+bb)(a+b)
=aaa+aab+aba+abb+baa+bab+bba+bbb = a 3 ? 3a 2 b ? 3ab2 ? b 3

产生系数的根源:同一单项式中有顺序,即排列问题(球不同的 分配问题) 。 (二) 一般分配问题

问题:将 n 个相异的球放入 t 个盒子,要求第 1 个盒子放入 n1 个,第 2 个盒子放入 n2 个,……,第 t 个盒子放入 nt 个,且盒 中的球无次序,求不同的分配方案数。 问题转化:由于第 i 个盒中的 ni 个球是无序的,可视为 ni 个 相同的元素。因此,问题归结为求重集 S ? ?n1 ? e1 , n2 ? e2 ,?, nt ? et ?(n1 + n2+…+ nt = n)的全排列数 RP(n,n)。由式(1.3.3)知
26/69

《组合数学》

第一章

组合数学基础

RP?n, n ? ?

n! n1 ! n2 !? nt !

仿照二项式系数 ? ? ? ? ,将其记为 ? ? (三) 多项式系数

? n? ?r?

?

n ? ? ?。 n n ? n ? 1 2 t ?

一般多项式系数与 ? ?

?

n ? ? ? 的关系: n n ? n ? 1 2 t ?

(x+y+z)3=x3+y3+z3+3x2y+3xy2+3x2z+3y2z+3xz2+3yz2 +6xyz =

3! 3! 3! 3! x3+ y3+ z3+ x2y 0!?3!?0! 0!?0!?3! 2!?1!?0! 3!?0!?0! 3! 3! 2 3! 3! xy2+ x2z+ y z+ xz2 1!?2!?0! 2!?0!?1! 0!?2!?1! 1!?0!?2!

+ +

3! 3! yz2+ xyz 0!?1!?2! 1!?1!?1! 3 ? 3 3 ? 3 ? 3 ? 3 ? ? ? ? ? ? =? x + y + ? 0 0 3? ? z ? 3 0 0? ? 0 3 0? ? ? ? ? ? ? 3 ? 2 ? 3 ? 2 ? 3 ? 2 ? ? ? ? ? +? x y + xy + ? 2 1 0? ?1 2 0? ? 2 0 1? ?x z ? ? ? ? ? ?
3 ? 2 ? 3 ? 2 ? 3 ? 2 ? ? ? ? ? +? y z + xz + ? 0 2 1? ?1 0 2? ? 0 1 2? ? yz ? ? ? ? ? ? ? 3 ? +? ? 1 1 1? ? xyz ? ?

定理1.5.1 设 n 与 t 均为正整数,则有

? x 1 ? x 2 ? ? ? x t ?n
27/69

《组合数学》

第一章

组合数学基础



?ni ? 0 ?
t

? ni ? n
i ?1

t

?

n ? ? n1 n2 nt ? ? x x ? x 1 2 t ? n n ?n ? ? 1 2 t?

(1.5.2)

其中求和是在使 nt)上进行。

? ni ?n 的所有非负整数数列(n ,n ,…,
i ?1
1 2

证 (x1+x2+…+ xt)n
x ? x 2 ? ? ? xt ?? x1 ? x 2 ? ? ? x t ?? ? x1 ? x 2 ? ? ? x t ? =? ?1 ?????????? ? ???????????? ?
共n个 因 子 连 乘

其展开式的项都是由每个因子中各取某个 x, 然后相乘而得, 即所 有的项都具有形式
n1 n2 x1 x2 ? xtnt

而且 ? ni ? n 。 一般项的系数等于在这 n 个因子中先选出
i ?1

n

n1 个因子且这 n1 个因子中都取 x1,然后再在其余的 n-n1 个因子 中选出 n2 个因子且这 n2 个因子中都取 x2,…,最后在剩下的 n-

x1 n1-n2-…-nt-1= nt 个因子中都取 xt, 那么, 的系数为
n! ? n1 !??n ? n1 ? !

n1

n2 x2 ? xtnt

C ?n, n1 ? ? C ?n ? n1 , n2 ??C ?nt , nt ?

?n ? n1 ?!
n2 !??n ? n1 ? n2 ? !

?



nt ! nt !?0!

n! n ? ? ? = =? ? n1 ! n2 !? nt ! ? ? n1 n2 ? nt ?
28/69

《组合数学》

第一章

组合数学基础

称? ?

?

n ? ? ? 为多项式系数。 n n ? n ? 1 2 t?
多项式展开的项数

(四)

定理1.5.2

? x1 ? x2 ? ? ? xt ?n

展 开 式 的 项 数 等 于

C ?n ? t ? 1, n? ,而这些项的系数之和为 t n .
n1 n2 证 展开式的项 x1 x2 ? xtnt 与从 t 个元素 x1,x2,…,xt

中取 n 个的 n 可重组合是一一对应的,由式(1.3.7),后者正是 RC(∞,n)=C(n+t-1,n)。 令 x1=x2=…=xt=1,代入式(1.5.1)即得

?

?

t

?

i i ?1 ni ? 0

n ? ? ? ? n n ?n ? ? =(1+1+…+1)n= t n t ? ? 1 2 n ?n
?

(五)



例1.5.1 求(a+b+c+d)3 的展开式。 解 n=3,t=4,共有 RC(∞,3)=C(3+4-1,3) =20(项) 所以 (a+b+c+d)3 = ? ?
? ? 3 ? ?a ? 3 0 0 0? 3

+ ? ?

?

? 3 ? ?b ? 0 3 0 0? 3

+ ? ?

?

? 3 ? ?c ? 0 0 3 0? 3



3 ? ? 2 ? ? 2 0 1 0? ?a c + ? ? 3 3 3 ? ? 2 ? ? 2 ? ? 2 ? ? ? ? ? a d ab + + ? 2 0 0 1? ?1 2 0 0? ?1 0 2 0? ?ac + ? ? ? ? ? ?
3 ? ? 3 ? ? 0 0 3 0? ?d ? ?



3 ? ? 2 ? ? 2 1 0 0? ?a b ? ?



29/69

《组合数学》

第一章

组合数学基础

3 3 3 ? ? 2 ? ? 2 ? ? 2 ? ? ? ? ? ad b c + + ?1 0 0 2? ? 0 2 1 0? ? 0 2 0 1? ?b d ? ? ? ? ? ?
+? ?

?

3 3 ? 2 ? ? 2 ? ? 2 ? ? ? ? + + bc bd ? ? 0 1 0 2? ? 0 0 2 1? ?c d 0 1 2 0 ? ? ? ? ? ? 3 ? 3 3 ? 2 ? ? ? ? ? ? ? ? cd abc + + ? ?1 1 1 0? ? 1 1 0 1? ?abd 0 0 1 2 ? ? ? ? ? ? 3 3

+? ?

+? ?

?

3 ? ? ? ? ? acd + ? ? 0 1 1 1? ?bcd 1 0 1 1 ? ? ? ?
= a 3 + b 3 + c 3 + d 3 + 3 a 2 b + 3 a 2 c + 3 a 2 d + 3 ab2 + 3 ac 2 +

3 ad + 3 b c + 3 b d + 3 bc + 3 bd + 3 c d + 3 cd + 6abc + 6abd+6acd+6bcd
2 3 例1.5.2 (a1+a2+a3+a4+a5)7 的展开式中, 项 a1 a 3 a4 a5 的系数

2

2

2

2

2

2

2



7 ? ? 7! ? ? 2 0 1 3 1? ? ? 2!?0!?1!?3!?1! =420 ? ?
3 2 例1.5.3 在(2x1-3x2+5x3)6 的展开式中,项 x1 的系数是 x2 x3

什么? 解 令 a1=2x1,a2=-3x2,a3=5x3,则(a1+a2+a3)6 的展开式
3 2 a2a3 中 a1 的系数为 ? ?

?

6 ? ? , 即 (2x1 - 3x2 + 5x3)6 中 ? ? 3 1 2?

3 2 ?2 x1 ?3 ?? 3 x2 ??5 x3 ?2 的系数。因此 x1 x2 x3 的系数是

30/69

《组合数学》

第一章

组合数学基础

? ? ?3 ?

6 1

? 3 6! 2 ? ? ? 2 ? 3 5 = ? 8 ? ?? 3? ? 25 =-36000 2? 3 ! ? 1 ! ? 2 ! ?

例1.5.4 求证

k ?0

? ?? 1?k C ?n, k ?x k ?1 ? x ?n ? k ? 1 , n≥1
证 在二项式定理中取 a=-x,b=1+x,则 1= 1n = ??? x ? ? ?1 ? x ??
n
n

n

(1.5.3)



k ?0

? C ?n, k ??? x ?k ?1 ? x ?n ? k

整理即得式(1.5.3) 。 例1.5.5 今天是星期日,再过 10 解
100

天是星期几?
50

10100 = 10050 = ?14 ? 7 ? 2?
=2
50 50

? 50 ? r 50 ? r ? ?? ? r ? ??14 ? 7 ? 2 ? r ?1 ?

等价问题: 10100 除以 7 的余数= 2 50 除以 7 的余数

2

50

=2

2? 3?16

16 ? ? 16 ? r ? = 4 ? 8 = 4?7 ? 1? = 4 ?1 ? ? ? ? r ? ?7 ? ? ? ? r ?1 ?
16
16

≡4 mod 7 答案:再过 10 另法: 10
100

天是星期四。
100

100

= ?7 ? 3? =3
100

? 100 ? r 100? r ? ?? ? r ? ?7 ? 3 r ?1 ? ?
100
31/69

《组合数学》

第一章

组合数学基础

3100 = 3 ? 27 33 = 3?28 ? ?? 1??

33

33 ? ? 33 ? r 33 33? r ? ? ? ? 28 ? ? 1 = 3 ??? 1? ? ? ? ? ? ? r ?1 ? r ? ? ?

3?? 1? =-3≡4 mod 7
33

例1.5.6 求证
k ? ?? 1? C ?n, k ?? k ?0 n

? 1 ? kx ? =0, n 为自然数 k ? ? ?1 ? nx ? ?
n n

(1.5.4) 证

1 ? 1 ? ? ? 0= ? 1 ? ? -?1 ? ? 1 ? nx ? 1 ? nx ? ? ?
n

1 ? nx ? 1 ? ? =?1 ? ? - ?1 ? ? 1 ? nx ? 1 ? nx ? 1 ? nx ? ? 1 ? ? = ? C ?n, k ?? ? ? ? 1 ? nx ? k ?0
n k

n?1

nx - 1 ? nx
n

1 ? ? ? ? C n ? 1 , k ? ? ? ? ? 1 ? nx ? k ?0
k k

n?1

k

? 1 ? = ? C ?n, k ??? 1? ? ? 1 ? nx ? ? k ?0

x n ?1 1 ? - ?? 1?k ?k ? 1?C ?n, k ? 1?? ? ? ? 1 ? nx k ? 0 ? 1 ? nx ?

k

? 1 ? = ? ?? 1? C ?n, k ?? ? ? 1 ? nx ? k ?0 n ?kx ? ? ?? 1?k C ?n, k ? +? ?1 ? nx ?k k ?0
n k

k

32/69

《组合数学》

第一章

组合数学基础

= ? ?? 1?k C ?n, k ??
k ?0

n

? 1 ? kx ? . k ? ? ?1 ? nx ? ?

(六)

问题
8

c ? ? 请 给 出 多 项 式 ? a ? 2b ? ? 3d ? 的 展 开 式 中 a 2 b 2 c 2 d 2 和 2 ? ?

bc 5 d 2 两项的系数。
答:22680,-189/2

1.6
1.6.1 序 数 法 (一)

排列的生成算法

数的位权表示
r

(1)十进制数:考虑小于 10 的正整数 n,可以表示为下述的 位权形式: n=

k ?0

? ak 10k ,

r ?1

0≤ a k ≤9<10

例 315= 3 ? 102 ? 1 ? 101 ? 5 ? 100 , (r=3) (2)推广(p 进制数) n=

k ?0

? ak p k ,

r ?1

0≤ a k <p

(3)特点:① 固定进制;② 逢 p 进一;③十进制 r 位数最 小为 0,最大为 999…9= 10r -1< 10r ;④将十进制换算为 p 进 制数方法:除 p 取余法。

33/69

《组合数学》

第一章

组合数学基础

(二)

变进制表示

(1)依据:利用递推关系 n! =(n-1)(n-1)!+ (n-1)! 可以得到 n!=(n-1)(n-1)!+ (n-2)(n-2)!+ (n-2)! =(n-1)(n-1)!+ (n-2)(n-2)!+ (n-3)(n-3)!+ (n-3)!
?

=(n-1)(n-1)!+ (n-2)(n-2)!+ …+2·2!+1·1!+1! n!=

? k ? k! +1
k ?1

n ?1

所以 n!-1=(n-1)(n-1)!+ (n-2)(n-2)!+ …+2· 2! +1· 1! 这和

10n -1=9·10n ?1 +9·10n ? 2 +…+9·10 1+9·10 0 类似。

可以证明,从 0 到 n!-1 的任何整数 m 都可唯一地表示为 m=an-1(n-1)!+an-2(n-2)!+…+a22!+a11! = 其中 0≤ai≤ i , i =1,2,…,n-1. 所以,从 0 到 n!-1 的 n!个数与满足式(1.6.2)要求的序列 (an-1,an-2,an-3,…,a2,a1) 是一一对应的。 将十进制转换为变进制:
34/69

? a k ?k !
k ?1

n?1

(1.6.1)

(1.6.2)

(1.6.3)

《组合数学》

第一章

组合数学基础

20=3*3!+1*2!+0*1!=(310) 30=1*4!+1*3!+0*2!+0*1!=(1100) 100=4*4!+0*3!+2*2!+0*1!=(4020) 200=(13110) ,8005=(143201)

(2)ai 的计算 m=an-1(n-1)!+an-2(n-2)!+…+a22!+a11! 记 n1=m

n1 ? n2 = ? ? ? =an-1 ?2?

?n ? 1?!
2

+an-2

?n ? 2 ? !
2

+…+a3

3! +a2 2
(1.6.4)



m÷2!= n1 ? 2 ? n2 ????a1

同理,

?n ? 2 ? ! ?n ? 1?! 4! ?n ? +an-2 +…+a4 n3 = ? 2 ? =an-1 3! 3! 3! ?3?
+a3



(m- a1 )÷3!= n2 ? 3 ? n3 ????a2

算法:

? n1 ? m ? ? ni ? ? ? ni ?1 ? ? ? , i ? 1,2, ? , n ? 1 i ? 1 ? ? ? ? ?a i ? ni ? ?i ? 1?ni ?1 , i ? 1,2,? , n ? 1
其中 ? x ? 表示不大于 x 的最大整数。

(1.6.5)

(3)特点:① 变进制;② 从右向左,第 i 位逢 i +1 进一;
35/69

《组合数学》

第一章

组合数学基础

③n 位数最小为 0,最大为:(n-1)(n-1)!+ (n-2)(n-2)!+ … +2·2!+1·1!=n!-1<n!;④ 将十进制换算为变进制数方法 (见上) 。 (三) 序数法

(1)规则 设 n 个元素为 1,2,…,n。 对应规则:设序列(an-1,an-2,an-3,…,a2,a1)对应某个 排列(p)=p1p2…pn,其中 ai 可以看作排列(p)中数 i+1 所在 位置后面比 i+1 小的数的个数,即排列(p)中从数 i+1 开始向 右统计不大于 i 的数的个数。 (2)实例 1)n=4,排列(p)=(3124) ,4 后面比它小的数的个数 a3 =0,3 后面比它小的数的个数 a2=2,2 后面比它小的数的个数 a1 =0,故得 (p)=(3124) ? (a3 a2 a1)=(020) 2)反之,已知某个具体的(a3 a2 a1) ,即可得到对应的排列 p1p2p3 p4 . 比如(a3 a2 a1)=(111) ,由最左边的 a3=1 可知,比 4 小的数只有一个,故 4 排在 p3 的位置(即 p3=4) ,再由中间的 a2=1 知比 3 小的数也只有一个,因此 3 不能在最后,也不能在最 前边,故 p2=3,最后,由 a1=1 知 2 应排在 1 之前,故 p1=2, 最后必有 p4=1。所以 (a3 a2 a1)=(111) ? (p)=(2341) 当 n=4 时,各序列的对应排列见表 1.6.1。 3)数 7 3 5 2 3 3 2 2 0 数 987654321

?

排列 3 5 A 8 6 4 9 7 1 2

?

排列 A 9 8 7 6 5 4 3 2 1

4)排列 3,5,7,9,10,8,6,4,2,1

? 数 554433221
36/69

《组合数学》

第一章

组合数学基础

(3)4 元排列的生成 表 1.6.1 m 0 1 2 3 4 5 6 7 8 9 10 11 a3 a2 a1 000 001 010 011 020 021 100 101 110 111 120 121 p1 p2 p3 p4 1234 2134 1324 2314 3124 3214 1243 2143 1342 2341 3142 3241 m 12 13 14 15 16 17 18 19 20 21 22 23 a3 a2 a1 200 201 210 211 220 221 300 301 310 311 320 321 p1 p2 p3 p4 1423 2413 1432 2431 3412 3421 4123 4213 4132 4231 4312 4321

1.6.2 字 典 序 法 (一) 算法

将所有 n 元排列按“字典顺序”排成队,以 12…n 为第一个排 列,排序的规则,也就是由一个排列(p)=(p1p2…pn)直接生 成下一个排列的算法可归结为 (1) 求满足关系式 pk ?1 ? pk 的 k 的最大值,设为 i,即

i ? max ?k pk ?1 ? pk ?
(2) 求满足关系式 pi ?1 ? pk 的 k 的最大值,设为 j,即

j ? max ?k pi ?1 ? pk ?
(3) pi ?1 与 p j 互换位置得
37/69

《组合数学》

第一章

组合数学基础

(q)=(q1 q2 … qn); (4) (q)=(q1 q2 … qi-1 qi qi+1 … qn)中 qi qi+1 … qn 部 分的顺序逆转,得新排列 q1 q2 … qi-1 qn…qi+1 qi (二) 例

(1)设 p1p2p3p4=3421,那么,i=2,j=2,p1 与 p2 交换得 q1 q2 q3 q4 =4321,再将 321 逆转即得下一个排列 4123 。 当 n=4 时由字典序法所得的全部排列的先后顺序如下: 1234 → 1243 → 1324 → 1342 → 1423 → 1432 → 2134 → 2143 → 2314 → 2341 → 2413 → 2431 → 3124 → 3142 → 3214 → 3241 → 3412 → 3421 → 4123 → 4132 → 4213 → 4231 → 4312 → 4321 (2)85376421 ? i=4,j=6 ? q1 q2 q3…q8 =85476321 ? 85412367 85412367 ? i=8,j=8 ? q1 q2 q3…q8 =85412376 85412376 ? i= 7, j= 8 ? q1 q2 q3… q8 = 85412673
? 85412637

85413726 ? i=8,j=8 ? q1 q2 q3…q8 =85413762 85413762 ? i= 6, j= 7 ? q1 q2 q3… q8 = 85416732
? 85416723

38/69

《组合数学》

第一章

组合数学基础

1.6.3 邻 位 互 换 生 成 算 法 本算法的思想也是希望以(12…n)作为 n 个元素 1,2,…, n 的第一个排列,然后按照某种方法,由一个排列(p)=(p1p2… pn)直接生成下一个排列,直到全部排列生成完毕为止。 以 n=4 为例, 开始在排列 1234 的各数上方加一个左箭头 “←” , 当一个数上方箭头所指的一侧,相邻的数比该数小时,便称该数处 ???? 于活动状态。例如 1234 中的 2,3,4 都处于活动状态。 从排列(p)=(p1p2…pn)生成下一个排列的算法如下: (1)若排列(p)=(p1p2…pn)中无一数处于活动状态,则 停止,否则转(2) ; (2)求所有处于活动状态的数中的最大者,设为 k,k 和它的 箭头所指的一侧的相邻数互换位置,转(3) ; (3)令比 k 大的所有数的箭头改变方向,转(1) 。 n=4 时各个数移动位置而生成所有 4 排列的情形见图 1.6.1。 各数的活动规律:以 1234 中的 4 为例,从一端移到另一端, 共进行了 3 次换位,然后暂停一次,这时 3 开始活动。这是 4 活动 的一个过程。 3 在 123 中的活动规律也很相似,而且这种活动规律可以推广 到 n 个数的排列。

39/69

《组合数学》

第一章

组合数学基础

1

2

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

2

3

?1 ? ?1 ? ?1 ?4 ? ?4 ? ?1 ? ?1 ?1 ? ?3 ? ?3 ? ?3 ?4 ? ?4 ? ?3 ? ?3 ?3 ? ?2 ? ?2 ? ?2 ?4 ? ?4 ? ?2 ? ?2 ?2 ?

2 2 4 1 1 4 3 3 1 1 4 3 3 4 2 2 3 3 4 2 2 4 1 1

3 4 2 2 3 3 4 2 2 4 1 1 2 2 4 1 1 4 3 3 1 1 4 3

4 3 3 3 2 2 2 4 4 2 2 2 1 1 1 4 4 1 1 1 3 3 3 4

3

2

1

2

2

1

2

1

3

1

1

3

40/69

《组合数学》

第一章

组合数学基础

图 1.6.1 排列的邻位互换过程

1.7

组合的生成算法

例 从 6 个元素 1,2,3,4,5,6 中取 3 个的组合: 123 → 124 → 125 → 126 → 134 → 135 → 136 → 145 → 146 → 156 →234 → 235 → 236 → 245 → 246 → 256 → 345 → 346 → 356 → 456 规律: (1)最后一位数最大可达 n(本例 n=6) ,倒数第二位数最大 可达 n-1,…,依此类推,倒数第 k 位最大可达 n-k+1(k≤r) , 若 r 个元素的组合用 c1c2…cr 来表示,并不妨假定 c1< c2<…< cr 则 cr≤n,cr-1≤n-1,…,c1≤n-r+1 即 ci≤n-r+i,i=1,2, …,r 。

(2)当存在 cj <n-r+j 时,令 i=max j c j ? n ? r ? j ,并 令

?

?

?d k ? c k , 1 ? k ? i ? ?d i ? c i ? 1 , ?d ? d ? 1 , i ? k ? r ? k k ?1
就可得到新的组合 d1d2…dr 。若每个 cj =n-r+j,则已经达到最 后一个组合,生成完毕。 例如由 123 开始,显然 1,2,3 都满足 c j ? n ? r ? j ,选其 中最大下标 i ? 3 对应的 c3 ,令 d1= c1=1,d2= c2=2,d3= c3 +1=4,便得下一组合 124。又如组合 c1c2c3=346,那么 3 和 4 满 足 c j ? n ? r ? j ,自然选 i ? 2 ,并令 d1= c1=3,d2= c2+1=4 +1=5,d3= d2+1=5+1=6,即后续组合为 356 。
41/69

《组合数学》

第一章

组合数学基础

归纳从一个组合 c1c2…cr 得到下一个组合的步骤如下初值为组 合 ?12?r ? : (1)若 i=max j c j ? n ? r ? j 存在,转(2) ,否则,停止; (2)ci←ci+1; (3)cj←cj-1+1,j=i+1,i+2,…,r . 输出 ? c1c2 ?cr ? , 转(1) 。 例:n=10,r=5 14678 → 14679 → 1467A → 14689 → 1468A → 1469A → 14789

?

?

1.8

应用举例

例1.8.1 试确定由 1,2,3,4,5 这五个数字能组成多少个大 于 43500 的五位数? (解)有限制条件的 RP(∞,5)的问题。下列情况之一发生便 可导致“大于 43500” : (1) 万位上数字是 5,其余四位上的数字从 1,2,3,4,5 中允许重复选取,共有 1×5 4 个符合要求的数; (2) 万位上数字为 4,千位上数字从 4,5 中选一个,其余 三位上数字可从五个数字中重复选取,共有 1×2×53 个; (3) 万位、千位、百位上数字分别为 4、3、5,其余二位上 的数字可在 1~5间重复选取,共有 1×1×1×52 个。 由加法法则,这样的数总计为 54+2×53+52=900 (个)

例1.8.2 从-2,-1,0,1,2,3 共 6 个数中不重复地选 3 个
42/69

《组合数学》

第一章

组合数学基础

数 作 为 二 次 函 数 y ? ax 2 ? bx ? c 的 系 数 , 使 得 抛 物 线

y ? ax 2 ? bx ? c 的开口方向向下,共可作出多少个二次函数?
(解) 抛物线的开口方向向下,必有 a<0。
1 第一步:a 从-2、-1 中选一个,有 P2 种方法;

第二步:在余下的五个数中选出两个进行排列,作为 b 和 c, 有 P52 种方法。 根据乘法法则,共可作出二次函数
1 2 P2 P5 =40(个)

例1.8.3 满足 x1 ? x2 ? x3 ? x4 ? 100 的正整数解有多少组? 解 方法Ⅰ:设想长度为 100 的线段被分为 4 段,每段的长度 均为正整数,叫做 x1 , x 2 , x 3 , x 4 。把 4 条线段再接成一条线 段,需要 3 个加号“+” 。如 x1 =10, x 2 =35, x 3 =40, x 4 =15, 从而有 10+35+40+15=100。 — — … — + — — … — +— …— — —+ — … — 问题转化:长度为 1 的 100 条线段中间有 99 个空“○”将这 些线段分开,在这 99 个空的位置上放置 3 个“+”号,未放“+” 号的线段合成一条线段,求放法总数。
3 C 99 =

99 ? 98 ? 97 =156849(组) 3? 2?1

方法Ⅱ:将 100 个相同的“1”放入 4 个不同的盒子,每个盒 子至少放一个。求不同的放法数。 第一步:每个盒子先放一个,共有一种放法。
96 3 第二步:将余下的 96 放入,有 C96 4? 96?1 ? C99 ? C99

变异一:求非负整数解(即 x i ? 0 ) 。
43/69

《组合数学》

第一章

组合数学基础

用方法Ⅰ求解: — — … — — … — + — — … — — + — — … —+ — — … — — … — ++ — — … — — + — — … —
3 3 答: C101 ? 3?1 ? C103 =176851

用方法Ⅱ求解:将 100 个相同的球放入 4 个不同的盒子,每个 盒子的容量无限。求不同的放法数。
100 100 3 答: C 4 ?100?1 ? C103 ? C103 =176851

变异二:求解。 x1 ? ?3 , x 2 ? 5 , x 3 ? 0 , x4 ? 0 。 思想:将问题转化为变异一。 原方程 故令 得 答:解数为

? x1 ? 3? ? ? x2 ? 5? ? x3 ? x4 ? 98
y1 ? x1 ? 3 , y2 ? x2 ? 5 , y3 ? x 3 , y4 ? x4 y1 ? y2 ? y3 ? y4 ? 98
( yi ? 0 )

98 98 3 C4 ? 98?1 ? C101 ? C101 =166650

问题:将原题用变异二的思路求解。

y1 ? y2 ? y3 ? y4 ? 96
例1.8.4 把 r 个相异物体放入 n 不同的盒子里,每个盒子允许放 任意个物体,而且要考虑放入同一盒中的物体的次序 ,求这种分配 方案有多少? (解) 特点: 本问题既不是相异元素的不重复排列,也不是简单的重复 排列。 考虑第一个物体的放法有 n 种,把它放入某盒子后,可看作是
44/69

《组合数学》

第一章

组合数学基础

该盒子的隔板,将盒子分成了两部分。这样,第二个物体的放法 有 n+1 种,同理,第三个物体的放法有 n+2 种,……,第 r 个 物体的放法有 n+r-1 种。由乘法原理,符合条件的方案数为 n(n+1)(n+2)…(n+r-1)=

?n ? r ? 1? ! =P(n+r-1,r) ?n ? 1? !

若在上例中把将条件“考虑放入同一盒中的物体的次序”改为 “不考虑放入同一盒中相异物体的次序” ,则分配方案数应为

n ?? n? ?? ? n = n r ,即 n 个相异元素的 r 可重排列数。原因是每个 ? ? ?
r个

物体都恰有 n 种放法。

实际应用:A、B、C、D、E 共 5 位同学由两个门排队进入教 室,每个门每次只能同时进一人,问有多少种进法? 答:2×3×4×5×6=720 种

前门人 数 0 1 2 3 4 5

后门人 数 5 4 3 2 1 0

方法 1×5!=120
1 C5 ×1×4!=120

备注
0 ×0!×5! C5
1 C5 ×1!×4!

2 C5 ×2!×3!=120

3 C5 ×3!×2!=120 4 C5 ×4!×1!=120 5 ×5!×0!=120 C5

问题 1:设前门宽大,可以同时进 2 人,那么又有多少种不同 的进法? 答:有 3×4×5×6×7=2520 种。
45/69

《组合数学》

第一章

组合数学基础

问题 2: 火车站外有 100 名乘客, 欲从 4 个门排队进入候车室, 问有多少种进门的排队方式? 问题 3:大楼共有 19 层,今有 12 人从一楼进入电梯上楼,每 层都可能有人出电梯,且电梯的门同时只能容许一个人出入,问 有多少种方式出电梯? 如果只关心从每个门进入教室的学生人数和具体的人,但不考 虑从同一个门进入教室的学生的次序,则 5 个学生通过 2 个门进 入教室的所有不同方式也就是

2 5 =32
种。

例1.8.5 把 n 元集 S 划分成 n ? 3 个无序非空子集(n≥4) ,共有 多少种分法? 解 模型:分配问题:将个不同的球放入 n-3 个相同的盒子,每 个盒子最少一个球。 求解:设共有 L 种分法,可将这些划分方法分成如下三类: (1) 使得有一个子集是 4 元集,其余子集是一元集的划分方案
4 数等于 n 元集的不重复的 4 组合数 C n ;

(2) 使得有一个子集是 3 元集,有一个子集是 2 元集,其余子
5 集是 1 元集的划分方法:因为 n 元集 S 的 5 组合数为 C n ,

3 把 5 元集划分成一个 3 元子集和一个 2 元子集的方法有 C 5 5 =10 种,故由乘法法则,属于此类的划分方法有 10 C n 种;

(3) 使得有 3 个子集是 2 元集, 其余子集是一元集的划分方法:
6 因为 n 元集的 6 组合数为 C n , 把 6 元子集划分成 3 个 2 元 子集的方法有

46/69

《组合数学》

第一章

组合数学基础

6 ? 1 6! 1? ? ? ? ? 3! 2!2!2! ? 15 3! ? 2 2 2 ? ? ? n? 种,所以属于此类的划分方法有 15 ? ? ? 6? ? 种。 ? ?
三类情况,互不重复,故由加法法则得

? n? ? 6? 例1.8.6 设 f r ?n, k ? 是能够从集合 ?1,2,?, n?中选出两两之差 均大于 r 的 k 元子集的方案数,试求 f r ?n, k ? 。
L= ? ? ? ? ? 10? ? ? ? ? 15? ? ? ? 解 在集合 A= ?1,2,?, n?中任取 k 个两两之差超过 r 的数构 成组合 a1 , a 2 ,?, a k ,不妨设 a1 ? a2 ? ? ? ak ,则 a j ? a i ≥r+1 (1≤i<j≤k) , 令

? n? ? 4?

? n? ? 5?

bi ? ai ? ?i ? 1?r ,

i ? 1,2,?k

那么, b j ? bi ≥1 (1≤i<j≤k,且有 1≤ b1 ? b2 ? ? ? bk ≤n-(k-1)r 即按条件从 A 中选取 k 个元素的一种方案对应于从集合 B= ?1,2,?, n ? ?k ? 1?r?中不重复地选取 k 个元素的方案,反之亦然。 因此,两个集合各自满足不同条件的 k 组合方案是一一对应的, 后者的组合方案数为 ? ?

? n ? r ?k ? 1?? ? ? ,从而知 k ? ?
? n ? rk ? r ? ? f r ?n, k ? ? ? ? ? k ? ?

例1.8.7 有 7 位科学家从事一项机密工作,他们的工作室装有 电子锁,每位科学家都有打开电子锁的“钥匙” 。为了安全起见, 必须同时有 4 人在场时才能打开大门。试问该电子锁至少应具备 多少个特征?每位科学家的“钥匙”至少应有多少种特征? (解) 任意 3 个人在一起,至少缺少一种特征,故不能打开 电子锁。由 7 个人中的 3 个人组合数为 C(7,3),故电子锁至少应
47/69

《组合数学》

第一章

组合数学基础

有 C(7,3)= 7 ? 6 ? 5 =35
3? 2

种特征。这样才能保证有任意 3 人在场时至少缺少一个特征而打 不开门。这就是说,每一种组合所形成的 3 人小组缺少的特征是 不一样的, 才能达到目的。 如若不然, 假设电子锁只有 34 种特征, 那么,7 人中取 3 位的 35 种组合方案中,至少有两组缺少同一种 特征, 而这两种组合方案至少对应 4 位不同的科学家 (当然至多 6 人) ,这就说明,这 4 位科学家由于缺少同一特征而当 4 人同时在 场时打不开大门。

1 2 3 4 5 6 7

ABC ABD ABE ABF ABG ACD ACE

8 9 10 11 12 13 14

ACF ACG ADE ADF ADG AEF AEG

15 16 17 18 19 20 21

AFG BCD BCE BCF BCG BDE BDF

22 23 24 25 26 27 28

BDG BEF BEG BFG CDE CDF CDG

29 30 31 32 33 34 35

CEF CEG CFG DEF DEG DFG EFG

对某一位科学家 A 的“钥匙”而言,其“钥匙”的特征个数至 少为 C(6,3)=

6? 5? 4 =20 3? 2

例:A={16~35}; B={6~15,26~35}; C={2~5,10~15,20~25,32~35}; 例1.8.8 从(0,0)点到达(m,n)点(m<n) ,要求中间所 经过的每一个格子点(a,b)恒满足 b>a,问有多少条最短路径? 解 从(0,0)到(m,n)点的路径中若排除经过点(a,b) , b≤a,的可能性。则第一步必须从(0,0)到(0,1) 。因此问题
48/69

《组合数学》

第一章

组合数学基础

等价于求满足条件的从(0,1)点到(m,n)点的路径数。 (m,n)

(0,0)
图1.8.1

带有限制条件的最短路径问题

由于 m<n,显然从(1,0)点到(m,n)点的每一条路径, 必然穿过 y=x 上的格子点。下面建立起从(1,0)到(m,n)点 每一条路径,与从(0,1)到(m,n)点但经过 y=x 线上的格子 点的路径间的一一对应关系。 从图 1.8.1 可见,若从(1,0)到(m,n)点的某一路径与 y =x 的交点从左而右依次为 P1,P2,…,Pk,设 Pk 是最后一个在 y=x 上的格子点。作(0,1)点到 Pk 的一条道路(实线)使之与 上述的从(1,0)点到 Pk 点的路径(虚线)关于直线 y=x 对称, 于是对从(1,0)点到(m,n)点的一条路径,有一条从(0,1) 点到 (m, n) 点, 但过 y=x 上的点的路径与之对应。 反之对从 (0, 1)点到(m,n)点的一条路径(经过 y=x 上的格子点) ,必存在 从(1,0)点到(m,n)点的一条路径与之对应。 故所求的路径数为 (0,1)点到(m,n)点的所有路径数减去 (1,0)点到(m,n)点的所有路径数,即 N= ? ?

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

49/69

《组合数学》

第一章

组合数学基础

=(m+n-1)! ? =(m+n-1)! ? =

?

? 1 1 ? ? ? m!( n ? 1)! ( m ? 1)! n!?

m ? ? n ? ? m! n! m! n!? ?

n ? m ?n ? m? ( m ? n ? 1)! ? ? (n—m)= ? n? m? m! n! m ? ?
k?r r Cn ? Cn ?k

例1.8.9 n,h,r 都是非负整数,并且 n ? k ? r 。证明 (1.8.1)

等号何时成立?
k?r 解 在 a1 , a 2 ,?, a n 中取 k+r 个元,有 C n 种取法。其中特

殊的一种取法是:先取前 k 个元素 a1 , a 2 ,?, a k ;再从其余的 n ? k
r 个元素 a k ?1 , a k ? 2 ,?, a n 中取 r 个,这样的取法有 C n ? k 种。显然后

者不大于前者,这就是式(1.8.1) 。 等号成立时 n=k+r,否则总有不全含 a1 , a 2 ,?, a k 的 k+r 元 子集。反过来,当 n=k+r 时,确实有
k ?r r Cn ? 1 ? Cn ?k

例1.8.10 (一) 二进制串的汉明距离 设 a、b 两个用 n 位二进制表示的码 a=a1a2…an, b=b1b2…bn

如若 ai≠bi 的个数为 k,则用 d(a,b)=d(b,a)=k 表之,称 为 a、b 码的 Hamming 距离。

50/69

《组合数学》

第一章

组合数学基础

(二) 性质 三角不等式 d(a,b)+d(b,c)≥d(a,c) 设 c=c1c2…cn,d(a,c)=k。如若 ai≠ci,由于每位只有两种可 能(0 或 1) ,因此有以下两种情况: (1) ai≠bi,但 bi=ci;

(2)ai=bi,bi≠ci。由于假定 d(a,c)=k,其中 k1 位满足 条件(1) ,k2 位满足条件(2) ,且 k=k1+k2 。 根据 Hamming 距离的定义有 d(a,b)≥k1 , d(b,c)≥k2 故三角不等式成立。 (三) 检错码与纠错码 检错码:奇偶校验码、汉明码、BCH 码等。 纠错码:汉明码、BCH 码、郭帕码等。 (四) 汉明码 (1) 思想:如若 a′与码 a 的距离≤r,则认为 a′是 a 的错 误而予以纠正,即将 a′当作是码 a 而加以处理。 (2) 码字的距离: 任意两个码 a、 b 之间的 Hamming 距离不 得小于 2r+1,否则可以构造 c,使之满足 d(a,c)=r,d(c,b)=r 即 c 与码 a 和 b 的距离相等, 都等于 r,无法纠正。 因若 a 与 b 的距
51/69

《组合数学》

第一章

组合数学基础

离为 2r,即其中有 2r 位满足 ai≠bi。从这 2r 位中选取 r 位,使之 保持与 a 相同,另 r 位与 b 相同。这样所得的 c 便是所求。 反之,若有一组码,其中两两的 Hamming 距离不小于 2r+1。 如若 a′与 a 的距离≤r,则由 d(a,a′)+d(a′,b)≥d(a, b) ,可知 a′与其它任一码字 b 的距离大于 r,这是因为 d(a′,b)≥d(a,b)- d(a,a′)≥(2r+1)-r=r+1>r (3) 例:r=1,n=8 字母 码字 a 00000000 b 11100000 c 00011100 相近码 10000000,01000000,…,00000001 01100000,10100000,…,11100001 10011100,01011100,…,00011101

(五) 编码量 设有一组 Hamming 距离不小于 2r ? 1的 n 位二进制码: a1,a2,…,aM 已知 n 位二进数共有 2n 个, 其中与 ai 的距离等于 k 的数的个数显 然为 ? 即从 ai 中取出 k 位加以改变而得。 故与 ai 的距离小于等 ? ? ?, 于 r 的数的个数为
? n? ? n? ? n? r ? n? ? ? ? ? ? ? ? ? ? ? 0? ? 1? ?r? ? ? ?? ? ? ? ? ? ? ? ? ? k ?0 ? k ?

? n? ?k?

凡是与 ai 的距离小于等于 r 的二进制数都认为是由于 ai 的错误引 起的。令 Ui={a|d(a,ai)≤r}。
52/69

《组合数学》

第一章

组合数学基础

根据编码时对距离的规定, 可知 2n 个数中每个数最多只能属于 U1,U2,…UM 中的一个。 所以
?? n ? ? n ? ? n ?? n M ? ?? ? 0? ??? ? 1? ? ? ?? ? ?r? ? ? ≤2 ? ?? ?? ? ? ?

即 M≤
2n ? n? ? n? ? n? ? ? ? ? ? ? ? ... ? ? 0? ? 1? ?r? ? ? ? ? ? ? ?

53/69

《组合数学》

第一章

组合数学基础

重点与要求
1.排列组合的基本计数问题(研、本) 2.计算多项式系数(研、本) 3.排列组合算法(研)

54/69

《组合数学》

第一章

组合数学基础

习题 1
1、 基本题:1~9,14,16,19,22~23,29,31 2、 加强题:11~12,17,18,21,28 3、 关联题:10,27, 4、 提高题:13,15,20,24~26,30,32

在 1 到 9999 之间, 有多少个每位上数字全不相同而且由 奇数构成的整数?
1-1

(解) 问题相当于求在相异元素 ?1,3,5,7,9?中不重复地取 1 个、

2 个、…、4 个元素的所有排列数,答案为

P51 ? P52 ? P53 ? P54 =5+20+60+120=205

比 5400 小并具有下列性质的正整数有多少个? (1) 每位的数字全不同; (2) 每位数字不同且不出现数字 2 与 7。 (解) (1)分类统计:①一位正整数有 P91 ? 9 个;②两位正整 数有 P91 ? P91 =81 个;③三位正整数有 P91 ? P92 =9×9×8=648 个; ④千位数小于 5 的四位数有 P41 ? P93 =4×9×8×7=2016 个;⑤千 位数等于 5,百位数小于 4 的数有1? P41 ? P82 =4×8×7=224 个。 由乘法法则,满足条件的数的总个数为
1-2

9+81+648+2016+224=2978 (2)仿(1) ,总个数为

P71 + P71 ? P71 + P71 ? P72 + P31 ? P73 + 1 ? P31 ? P62
=7+49+294+630+150=1130 一教室有两排,每排 8 个坐位,今有 14 名学生,问按下 列不同的方式入座,各有多少种坐法? (1) 规定某 5 人总坐在前排,某 4 人总在后排,但每人具体坐位不 指定; (2) 要求前排至少坐 5 人,后排至少坐 4 人。
1-3
55/69

《组合数学》

第一章

组合数学基础

(解) (1)5 人在前排就座,其坐法数为 P ?8,5? ,4 人在后排就座, 其坐法数为 P ?8,4? , 还空 7 个坐位, 让剩下的14 ? 5 ? 4 ? 5 个人入坐, 就座方式为 P ?7,5? 种,由乘法法则,就座方式总数为 P ?8,5? P ?8,4? P ?7,5? =28 449 792 000 (2)因前排至少需坐 6 人,最多坐 8 人,后排也如此。可分 成三种情况分别讨论:①.前排恰好坐 6 人,入坐方式有
? 14 ? ? 14 ? ? ②. 前排恰好坐 7 人, 入坐方式有 ? ?6? ? P ?8,6?P ?8,8? 种; ?7? ? P ?8,7 ?P ?8,7 ? ? ? ? ?

种;③前排恰好坐 8 人,入坐方式有 ? ? ? ? P ?8,8?P ?8,6? 种。各类入坐 方式互相不同,由加法法则,总的入坐方式总数为
? 14 ? ? 14 ? ? 14 ? ? ? ? ? ? ? ? ? ? ? ? ? ? + + P 8 , 6 P 8 , 8 P 8 , 7 P 8 , 7 ?6? ?7? ?8? ? P ?8,8?P ?8,6? ? ? ? ? ? ?

? 14 ? ?8?

误:先选 6 人坐前排,再选 4 人坐后排,剩下的 4 人坐入余下 的 6 个座位。故总的入坐方式共有
? 14 ? ? 8? ? ?6? ? P ?8,6?? ? 4? ? P ?8,4?P ?6,4? ? ? ? ?

种。但这样计算无疑是有重复的,例如恰好选 6 人坐前排,其余 8 人全坐后排,那么上式中的 ? ? ? ? P ?8,4? 就有重复。
? 8? ? 4?

一位学者要在一周内安排 50 个小时的工作时间, 而且每 天至少工作 5 小时,问共有多少种安排方案?
1-4

(解)是重复组合问题。 (1)每周按 7 天计算,先要拿出 5×7 =35 小时平均分配到每一天, 再将其余的 15 小时安排到 7 天之中,
56/69

《组合数学》

第一章

组合数学基础

每天的小时数不受限制,则安排方案数为

? 7 ? 15 ? 1 ? ? 21? ? ? 15 ? ??? ? 15 ? ? ? 54264 ? ? ? ?
(2)若每周的工作日按 6 天计,则问题变成在平均分配完 5 ×6=30 小时后,再将余下的 20 小时分配到这 6 天中,但此时每 天最多只能分配 19 小时。或者更一般,每天在 5 小时外再最多工 作 ni 小时 ?0 ? ni ? 19? ,那么,答案是多项式

? ?1 ? x ? x
6 i ?1
20

2

? ?? x

ni

?= ? a x
n r ?0 r

r

中 x 的系数 a 20 ,其中 n ? n1 ? n2 ? ? ? n6 。 (3) 另外, 设每周工作 t 天 ?3 ? t ? 7 ?, 每天最少工作 5 小时, 最多工作 ni 小时 ?5 ? ni ? 24? ,可以不按照上边的两步分配方法 求解,而是直接计算多项式

? ?x
t i ?1

5

? x ? x ? ?? x

6

7

ni

?= ? a x
n r ?0 r

r

t ? ? ? , ? n ? ? ni ? ? i ?1 ? ?

中 x 50 的系数 a 50 ,即得答案。 方式?
1-5

若某两人拒绝相邻而坐, 问 12 个人围圆桌就坐有多少种

答 11!-2×10!=9×10! 有 15 名选手,其中 5 名只能打后卫,8 名只能打前锋, 2 名能打前锋或后卫,今欲选出 11 人组成一支球队,而且需要 7 人打前锋,4 人打后卫,试问有多少种选法?
1-6


? 8 ?? 5 ? ? 2 ? ?? 8 ?? 5 ? ? 8 ?? 5 ? ? ?? 8 ?? 5 ? ? 8 ?? 5 ? ? 8 ?? 5 ? ? ? ? 7? ?? ? 4? ??? ? 1? ? ?? ? 6? ?? ? 4? ??? ? 7? ?? ? 3? ? ? ? ?? ? 5? ?? ? 4? ??? ? 7? ?? ? 2? ? ? 2? ? 6? ?? ? 3? ?? ? ?? ? ? ? ?? ?? ? ? ?? ? ? ?? ?? ? ? ?? ? ? ?? ? ?

=40+2×(140+80)+(280+80+2×280)=1 400
1-7

求 ? x ? y ? 2 z ? w ? 展开式中 x 2 y 2 z 2 w 2 项前的系数。
8

57/69

《组合数学》

第一章

组合数学基础

答 10 080
1-8

8 ? ? 2 8! 2 2 ? ? ? ? ? ? = ? 1 ? ? 1 ? 2 ? 1 ?4= ? 2 2 2 2? 2 ! ? 2 ! ? 2 ! ? 2 ! ? ?
求 ? x ? y ? z ?4 的展开式。

(解)由多项式的展开式公式

? ?n ?x ? y ? z? = 3 ? ? 1 n ? 4 ? i
4

?

n n2

? n1 n2 n3 ?x y z n3 ? ?

? ni ? 0 ?

i ?1

=? ?

?

4 ? 4 4 ? 4 ? 4 ? ? ? 4 ? 3 ? ? ? z +? x +? y +? ? ? ? 3 1 0? ?x y + ? ? ? ? 0 0 4? ? ? ? 4 0 0? ? 0 4 0? 4

? 4 ? 3 ? 4 ? 3 ? 4 ? 3 ? 4 ? 3 ? ? ? ? ? ? ? + + + xy x z y z ?1 3 0 ? ?1 0 3? ? xz + ? 3 0 1? ? 0 3 1? ? ? ? ? ? ? ? ? 4 ? 2 2 ? 4 ? 2 2 ? 4 ? 2 2 ? 4 ? 3 ? ? ? 0 1 3? ? yz + ? ? 2 2 0? ?x y +? ? 2 0 2? ?x z +? ? 0 2 2? ?y z ? ? ? ? ? ? ? ?

+? ? =

?

4 ? 2 ? 4 ? 2 ? 4 ? ? ? ? x yz + ? xyz 2 xy z + ? ? ? ? ? ? ? 2 1 1? ?1 1 2 ? ? 1 2 1?

4! 4! 4! 4! 4! x4 + y4 + z4 + x3 y + x3z + 4!?0!?0! 0!?4!?0! 0!?0!?4! 3!?1!?0! 3!?0!?1! 4! 4! 4! 4! 4! xy 3 + y3z + xz 3 + yz 3 + x2 y2 1!?3!?0! 0!?3!?1! 1!?0!?3! 0!?1!?3! 2!?2!?0!



4! 4! 4! 4! x2z2 + y2z2 + x 2 yz + xy 2 z + 2!?0!?2! 0!?2!?2! 2!?1!?1! 1!?2!?1!

4! xyz 2 1!?1!?2!

= x 4 + y 4 + z 4 + 4 x 3 y + 4 x 3 z + 4 xy 3 + 4 y 3 z + 4 xz 3 + 4 yz 3 +
6 x 2 y 2 + 6 x 2 z 2 + 6 y 2 z 2 +12 x 2 yz +12 xy 2 z + 12 xyz 2

58/69

《组合数学》

第一章

组合数学基础

可以验证,系数之和 1×3+4×6+6×3+12×3=81= 3 4
1-9
3 6 求 ? x1 ? x 2 ? x 3 ? x 4 ? x5 ?10 展开式中 x 2 的系数。 x3 x 4

答.
1-10

10 ? ? 10! ? ? 0 3 1 6 0? ? = 0!?3!?1!?6!?0! =840 ? ?

试证任一正整数 n 可唯一地表成如下形式: n= ? a i i! ,0≤ai≤i, i ? 1,2,?
i ?1

1-11

证明 nC(n-1,r)=(r+1)C(n,r+1)。并给出组合

意义。 意义: 将 n 个人分为 3 组: 一组 1 人, 一组 r 人, 另一组 n ? ?r ? 1? 人。一种分法是先从 n 个人中选出 r+1 人,剩下 n ? ?r ? 1? 人为一 组,再将所选的 r+1 人分为两组,一组 1 人,一组 r 人。另一种 分法是先选一人为一组,再从其余的 n ? 1 人中选 r 人为一组,剩下 的 n ? ?r ? 1? 人为一组。
1-12

证明

? kC ?n, k ? =n2 -1。
n

n

k ?1

(证)用殊途同归法。将 n 个不同的球放入标号为 A、B、C 的 3 个盒子,其中要求 A 盒只放 1 个球,其余两盒的球数不限。 那么,有两种思路: (1) 先从此 n 个不同的球中选出 1 个,放入 A 盒,再将其
1 ? 2 n?1 ? n2 n?1 种放法; 余 n ? 1 个球放入另外两盒,有 C n

(2) 先由 n 个球中选出 k 个 ?1 ? k ? n? ,再从所选的 k 个球 中选出 1 个放入 A 盒,将其余的 k-1 个球放入 B 盒,所剩的 n
k 1 n? k k ? Ck ? Cn - k 个 球 放 入 C 盒 , 有 Cn ? k ? kCn 种 放 法 。 当 k ? 1,2,?, n ,各种情况互不重复,且包含了所有放法,故对 k 求 和,即得等式左端。

1-13

有 n 个不同的整数,从中取出两组来,要求第一组数里
59/69

《组合数学》

第一章

组合数学基础

的最小数大于第二组的最大数,问有多少种方案? 解 设取的第一组数有 a 个,第二组有 b 个,而要求第一组数 中最小数大于第二组中最大的,即只要从 n 个数中取出 m=a+b 个数,从大到小排序后取前 a 个作为第一组,剩余的为第二组, 就满足题目的要求。 此时从 n 个数中取 m 个的方案数为 C(n, m)。 从 m 个数中取第一组数共有 m-1 种取法。故总的方案数为

? ?m ? 1?C nm = (n ? 2)2 n?1 ? 1
i ?2

n

六个引擎分列两排, 要求引擎的点火次序两排交错开来, 试求从某一特定引擎开始点火有多少种方案?
1-14

(解)设两排引擎分别为 a,b,c 和 x,y,z。 (1)设特定的引擎是 a,则点火的方案数为 3×2×2×1×1= 12。 (2)如果只指定从 a,b,c 这一排先开始点火,不指定某一个, 则方案数为 3×3×2×2×1×1=36 (3)如果第一个引擎任意选,只要求点火过程是交错的,则 方案数为 6×3×2×2×1×1=72 试求从 1 到 1000000 的整数中,0 出现了多少次? (解) 先不考虑 1 000 000 本身, 那么任一个 000 000~999 999 之间的数都可以表示成如下形式
1-15

d 1d 2 d 3 d 4 d 5 d 6
其中每个 d i 是 0 到 9 的数字。因为每位数字可以有 10 种选择,根 据乘法法则,共有 106 个“6 位数” ,又每个“6 位数”由 6 个数字 组成(包括无效 0) ,那么共有 6 ? 106 个数字,又每个数字出现的
60/69

《组合数学》

第一章

组合数学基础

概率相等, 所以 0 出现的次数应是

6 ? 106 ÷10= 6 ? 105
但习惯上在计算 0 的个数时,不包括无效 0(即高位的 0) ,因而 要从中去掉无效 0,其中 1 位数有 9 个(不包括 0) ,其无效 0 共有 5 ? 9 个; 2 位数有 90 个,其无效 0 共 4 ? 90 个。 余类推,这样,无效 0 的总数为

5 ? 9 ? 4 ? 90 ? 3 ? 900 ? 2 ? 9000 ? 1 ? 90000
注意到 d1d 2 d 3 d 4 d 5 d 6 全 0 时的 6 个 0 和 1 000 000 本身的 6 个 0 相互抵消,所以 1 到 1 000 000 之间的自然数中 0 出现的次数为

6 ? 105 ? ?5 ? 9 ? 4 ? 90 ? 3 ? 900 ? 2 ? 9000 ? 90000?=488
895 注 1 出现的次数为 6 ? 105 ? 1(要考虑 1 000 000 这个数的首 位 1) ,2,3,…,9 各自出现的次数为 6 ? 105 。 n 个男 n 个女排成一男女相间的队伍,试问有多少种不 同的方案?若围成一圆桌坐下,又有多少种不同的方案?
1-16

答 (1)2 ?n!? ; (2)n!(n-1)!
2

1-17

n 个完全一样的球,放到 r 个有标志的盒子,n≥ r,要

求无一空盒,试证其方案数为 ? ?

? n ? 1? ? ? 。 r ? 1 ? ?

(证) 因为盒子不能空,所以每个盒子可先放一个球。然后 把剩下的 n ? r 个球任意地放到 r 个盒子中, 因为此时每盒的球数不 限,这相当于求

61/69

《组合数学》

第一章

组合数学基础

S ? ?? ? e1 , ? ? e2 ,?, ? ? er ?
的 n ? r 组合,其组合数为
? r ? ?n ? r ? ? 1? ? n ? 1 ? ? n ? 1? ? ? ? ??? ?n? r? ??? ? r ? 1? ? n ? r ? ? ? ? ? ?
α α 设 n= p1α p2 , p1 、 p 2 、…、 p k 是 k 个不同的素数, ? pk 试求能整除尽数 n 的正整数数目。 答 ?? i ? 1??? 2 ? 1???? k ? 1?

1-18

1

2

k

1-19

试求 n 个完全一样的骰子能掷出多少种不同的方案?

(解)问题等价于计算从 6 类相异元素集 S ? ?? ? 1, ? ? 2,?, ? ? 6? 中可重复地选取 n 个元素的 n-重组合数,故方案数为
? 6 ? n ? 1? ? n ? 5 ? ?n ? 1??n ? 2???n ? 5? ? ??? ? ? ? ?? n ? 5! ? ? ? n ?

凸十边形的任意三个对角线不共点,试求这凸十边形的 对角线交于多少个点?又把所有的对角线分割成多少段? (解) (1)先求交点数:因为一个交点需要两条对角线相交, 而两条对角线又需要多边形的四个点构成一四边形。反之,从 n 个顶点中任取四个顶点,连诚意四边形,而四边形的两条对角线 必须确定唯一的一个交点,故凸十边形的对角线共交于 C(n,4)个 点(前提:任三对角线不共点,否则,一个交点不能对应 n 边形 的唯一四个顶点)
1-20

(2)2 交点总数+对角线条数= 2? ? ? ??? ? ? ??? ? ? ?

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

62/69

《组合数学》

第一章

组合数学基础

试证一整数 n 是另一个整数的平方的充要条件是除尽 n 的正整数的数目为奇数。
1-21
? ? (证)设 n 的标准分解式为 n= p1? p2 ,其中诸 p i 是互相 ? pk
1 2 k

不同的素数, ? i 为正整数。那么 n 是一个完全平方数 ? ? i 都是偶数 ? ? i +1 都是奇数 ?

?αi ? 1??α2 ? 1???αk ? 1? =奇数,即 n 的正因子数,亦即除尽 n 的正
整数有奇数个。 统计力学需要计算 r 个质点放到 n 个盒子里去,并分别 服从下列假定之一,问有多少种不同的图象。假设盒子始终是不 同的,
1-22

(1)Maxwell-Boltzmann 假定:r 个质点是不同的,任何盒子可 以放任意个。 (2)Bose-Einstein 假定:r 个质点完全相同,每一个盒子可以放 任意个。

(3)Fermi—Dirac 假定:r 个质点都完全相同,每盒不得超过一
个。 (解) (1)是重复排列问题,共有 n r 种不同图象; (2)是重复组合问题,共有 C ?n ? r ? 1,r ? 种不同图象; (3)是不重复组合问题,共有 C ?n,r ? 种不同图象。
1-23

从 26 个英文字母中取出 6 个字母组成一字,若其中有 2
63/69

《组合数学》

第一章

组合数学基础

或 3 个母音,问分别可构成多少个字(不允许重复)?

给出 ? n ?? r ? ? n ? 1 ?? r ? 1 ? ? n ? 2 ?? r ? 2 ? ? n ? m ?? r ? m ? ? n ? r ? 1 ? ? ? ? ?m? ?? ? 0? ??? ? m ? 1? ?? ? 1 ? ??? ? m ? 2? ?? ? 2 ? ? ? ?? ? ? 0 ? ?? ? ??? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? m ? ? m ?
1-24

的组合意义。
1-25

给出

? r ? ? r ? 1? ? r ? 2 ? ? n ? ? n ? 1? ? ? ? ? ? ? ? ? ? ? ? ? ?r? ? r ? ? r ? ?r? ??? ? r ? 1? ? ? ? ? ? ? ? ? ? ? ?
的组合意义。
1-26

证明:
? m ?? m ? ? m ?? m ? 1? ? m ?? m ? n ? n?m? ? ?? ? ? ? ?? ? ? ? ? ? ?? ??2 ? ? ? 0 ?? n ? ? 1 ?? n ? 1 ? ? n ?? 0 ? ? n?

中,当

1-27

对于给定的正整数 n, 证明在所有 C(n, r) (r=1,2, …,n)
?n ?1 , ? k= ? 2 ?n, ?2 n ?1 , n为奇数 2 n为偶数

时,C(n,k)是最大值。
1-28

(a)用组合方法证明 (b)证明

( 2n)! ( 3n)! 和 n n 都是整数。 2 ?3 2n

( n 2 )! ( n! ) n?1

是整数。

64/69

《组合数学》

第一章

组合数学基础

(证) (a)方法一:把 2n 个不同的球放入 n 个相异的盒子中, 每个盒子中恰有 2 个球,其分配方案数即为 方法二:因为 2n ? 2 ? 2? ?? ? 2 ,所以 ? ? ? ? ? ?
n个

( 2n)! ( 2n)! = n 。 2!2!? 2! 2

2n ? ? ( 2n)! ( 2n)! ? ? ? ? ? 2!2!?2! ? 2 2 ? 2 2n ? ?
2 2 2 是多项式 ? x1 ? x 2 ? ? ? x n ? 中 x1 项的系数。 x2 ? xn

2n

方法三: 集合 S ? ?2 ? e1 , 2 ? e2 , ?, 2 ? en ? 中 2n 个元素的 全排列的总数即为

( 2n)! ( 2n)! ? n 2!2!?2! 2
其次,对

( 3n)! ( 3n)! ( 3n)! ,方法类似,关键是看出 = 。 2n ? 3n 2 n ? 3 n 3!3!? 3!
( kn)! ( kn)! = ,但若 k! k!?k! ( k ! ) n

(b)仿(a) ,把 kn 个不同的球放入 n 个相异的盒子中,每个 盒子中恰有 k 个球,其分配方案数即为 盒子相同,则分配方案数即为
1-29

( kn)! ,再令 k=n,即得结果。 ( k ! ) n n!

(a)在 2n 个球中,有 n 个相同。求从这 2n 个球中选取 n 个的方 案数。 (b)在 3n+1 个球中,有 n 个相同。求从这 3n+1 个球中选取 n 个的方案数。 (解) (a)视为从集合 S ? ?n ? e0 , e1 , e 2 ,?, e n ?中选取 n 个元素,
65/69

《组合数学》

第一章

组合数学基础

分类统计,共有 n+1 类取法:设第 k 类取法是指所取的 n 个元素 中含有 k 个 e 0 , n ? k 个其它的 e i ?1 ? i ? n? (每个 e i 最多取一次) ,
?k 则此类取法共有1 ? C n 种 ?k ? 0,1,?, n ? 。所以,总的方案数为 n

? C nn? k ? ? C nk ? 2 n
k ?0 k ?0

n

n

(b)与(a)类似,方案数= ? C 2nn??k1 = ? C 2kn?1
k ?0 k ?0

n

n

1-30

证明在由字母表{0,1,2}生成的长度为 n 的字符串中。
n

(a) 0 出现偶数次的字符串有 3

?1 个; 2

? n ? n ? n ? n?2 ? n ? n?q 3n ? 1 ?n? (b) ? ? 0? ?2 ? ? ? 2? ?2 ? ? ? ? ?q? ?2 ? 2 , 其中 q=2 ? 2 ? . ? ? ? ? ? ? ? ?

(证) (a)为了叙述方便,称满足条件的串为偶串,否则为奇 串。并设满足条件的串为 ?a1a 2 ?a n ? 。考虑诸 a i 中至少有一个为 0 或 1 的串,那么,从串的左边开始向右扫描,总是会碰到 0 或 1, 对扫描到的第一个 0(或 1) ,将其改为 1(或 0) ,从而将偶串变 成了唯一的一个奇串,或将奇串变成了唯一的一个偶串。因此, 在三进制串中,除了每一位都是 2 的偶串(22…2)之外,所有偶 串与奇串一一对应,故各有 数应为
3n ? 1 3n ? 1 ? 1= 2 2 3n ? 1 个,再加上全 2 的串,偶串的总 2

(b)设偶串中有 2k 个 0,则 0 ? k ? ? ? 。可由两步来构造这 ?2?
66/69

?n?

《组合数学》

第一章

组合数学基础

样的 n 位串:
2k (1) 先在 n 个不同的位置放入 2k 个相同的 0, 有Cn 种放法;

(2) 再在其余的 n ? 2k 个位置放入 1 或 2, 其放法对应 n ? 2k 位 二进制串的个数,有 2 n? k 个。
2k 所以,由乘法法则知有 2k 个 0 的偶串共有 C n 2 n? k 个。又知对

于不同的 k,相应的串之间没有重复。故由加法法则,全部偶串共 有
? n ? n ? n ? n? 2 ? n ? n? q ? ?n?? ? ? ? ? ? 2 ? 2 ? ? ? ? q ? 2? 2 ? ? ? ? 0? ? 2? ?q? ?2 , ? ? ?? ? ? ? ? ? ? ?

个。再结合(a) ,即得欲证的结论。 5 台教学仪器供 m 个学生使用,要求使用第 1 台和第 2 台的人数相等,有多少种分配方案?
1-31

(解)由题目要求知 5 台仪器被视为是不同的。将分配过程分 为三步:
2k (1)从 m 个学生中选出 2k 人,有 C m 种选法;

(2)将选出的 2k 个学生分给 1、2 号仪器,且每台仪器 k 个 人,有
( 2k )! k ? C2 k 种分法; k! k!

(3)将其余的 m ? 2k 名学生分给 3、4、5 号仪器,每台仪器所 分人数不限,有 3m ? 2k 种分法。 由加法法则,总的分配方案数为
? m ?? 0 ? m ? m ?? 2 ? m ? 2 ? m ?? 4 ? m ? 4 ? m ?? 2t ? m ? 2 t ? ?? ? ?? ? ?0? ?? ? 0? ?3 ? ? ? 2? ?? ? 1? ?3 ? 4? ?? ? 2? ?3 ? 2t ? ?? ? ? ?3 ? ?? ? ? ?? ? ? ?? ? ? ?? t ?

67/69

《组合数学》

第一章

组合数学基础

m? 其中 t= ? ? ?。 ?2?
1-32 由 n 个 0 及 n 个 1 组成的字符串, 其任意前 k 个字符中, 0 的个数不少于 1 的个数的字符串有多少?

答 见教材第 3 章(P.73) 解 由 n 个 1 和 n 个 0 组成的 2n 位二进制数共有 (2n)!
(n!) 2

个(2n

个不尽相异元素的全排列),设所求的二进制数共有 bn 个,不符合 要求的数有 rn 个。而不合要求的数的特征是从左向右扫描时,必 然在某一位首次出现 0 的个数大于 1 的个数,即从左向右累计到 第 2k+1 位时出现 k+1 个 0 和 k 个 1。此时,后 2(n-k)-1 位上 有 n-k 个 1,n-k-1 个 0。将后部分的 0 改写为 1,1 改写为 0。 结果整个数变成由 n-1 个 1 和 n+1 个 0 组成的 2n 位数 z。即一 个不合要求的数唯一对应于这样的一个数 z。 10000111 ? 11111000, 00011110 ? 00011111 01010110 ? 01010111, 00111001 ? 00111110 反之,给定一个由 n-1 个 1 和 n+1 个 0 组成的 2n 位数 z.由 于 0 比 1 多 2 个,故一定在某一位首次出现 0 的累计数超过 1 的 累计数。依同法将此位后的 0 与 1 互换,使 z 变成由 n 个 1 和 n 个 0 组成的 2n 位数。所以,这两种二进制数一一对应。即
rn ?

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



68/69

《组合数学》

第一章

组合数学基础

bn ?

?2n?! 1 ?2n?! 1 ?2n ?! ? r = ?2n?! ? ? ? C ?2n, n? n 2 2 2 ?n!? ?n ? 1?! ?n ? 1?! n ? 1 ?n!? n ? 1 ?n!?

69/69


赞助商链接

组合数学-排列组合

这 与数学分析形成了对照。 1 第一章 排列组合 在这一章我们要用加法法则和...在组合习题中有许多类似的隐含的规定,要特别留神。 不含 0 的 1 位数有 ...

网络路径问题、母函数与排列组合、容斥原理论文

网络路径问题、母函数与排列组合、容斥原理论文_互联网_IT/计算机_专业资料。本科毕业论文 1 引言 第 1 页共 23 页 说起来,组合数学门很古老的科学,人们...

组合数学(2)排列组合

组合数学(2)排列组合_数学_高中教育_教育专区。ACM 暑期集训 组合数学(2) 排列组合 1 加法原理 3 配对原理(一一对应原理、相等原理) 如果可建立两个有限集 A...

2018年04月的高中排列组合数学组卷

2018 年 04 月的高中排列组合数学组卷一.选择题(共 21 小题) 1.高三年级的三个班去甲、乙、丙、丁四个工厂参加社会实践,但去何工厂可 自由选择,甲工厂必须...