《组合数学第一章解读》由会员分享，可在线阅读，更多相关《组合数学第一章解读（124页珍藏版）》请在金锄头文库上搜索。
1、东北林业大学东北林业大学 2007.122007.12 第一章 排列与组合 前言 组合数学是一个古老而又年轻的组合数学是一个古老而又年轻的 数学分支。数学分支。 据传说，大禹在据传说，大禹在40004000多年前就观多年前就观 察到神龟背上的幻方察到神龟背上的幻方. 前言 幻方可以看幻方可以看 作是一个作是一个3 3阶方阶方 阵，其元素是阵，其元素是1 1 到到9 9的正整数，的正整数， 每行、每列以每行、每列以 及两条对角线及两条对角线 的和都是的和都是1515。 5 1 9 37 24 86 前言 贾宪贾宪 北宋数学家（约北宋数学家（约1111世纪）世纪） 著有著有黄帝九黄帝九 章细草章细
2、草、算法斅古集算法斅古集斅斅 音音“ “笑（笑（“ “古算法古算法 导引导引” ”）都已失传。杨辉著）都已失传。杨辉著详解九章算法详解九章算法 （12611261年）中曾引贾宪的年）中曾引贾宪的“ “开方作法本源开方作法本源” ”图（图（ 即指数为正整数的二项式展开系数表，现称即指数为正整数的二项式展开系数表，现称“ “ 杨辉三角形杨辉三角形” ”）和）和“ “增乘开方法增乘开方法” ”（求高次幂的正（求高次幂的正 根法）。前者比帕斯卡三角形早根法）。前者比帕斯卡三角形早600600年，后者年，后者 比霍纳（比霍纳（William Geoge HornerWilliam Geoge Horne
3、r，1786183717861837） 的方法（的方法（18191819年）早年）早770770年。年。 前言 1666 1666年莱布尼兹所著年莱布尼兹所著组合学论文组合学论文 一书问世，这是组合数学的第一部专一书问世，这是组合数学的第一部专 著。书中首次使用了组合论（著。书中首次使用了组合论（ CombinatoricsCombinatorics）一词。）一词。 前言 组合数学的蓬勃发展则是在计算机组合数学的蓬勃发展则是在计算机 问世和普遍应用之后。由于组合数学涉问世和普遍应用之后。由于组合数学涉 及面广，内容庞杂，并且仍在很快地发及面广，内容庞杂，并且仍在很快地发 展着，因而还没有一个统
4、一而有效的理展着，因而还没有一个统一而有效的理 论体系。这与数学分析形成了对照。论体系。这与数学分析形成了对照。 前言 n n 本学期主要讲组合分析（计数和枚举）本学期主要讲组合分析（计数和枚举） 以及组合优化的一部分（线性规划的单以及组合优化的一部分（线性规划的单 纯形解法）。纯形解法）。 n n 组合分析是组合算法的基础。组合分析是组合算法的基础。 前言 组合数学经常使用的方法并不高深组合数学经常使用的方法并不高深 复杂。最主要的方法是计数时的合理分复杂。最主要的方法是计数时的合理分 类和组合模型的转换。类和组合模型的转换。 但是，要学好组合数学并非易事，但是，要学好组合数学并非易事， 既
5、需要一定的数学修养，也要进行相当既需要一定的数学修养，也要进行相当 的训练。的训练。 第一章排列组合 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 加法法则 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 1.1 加法法则与乘法法则 例 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 例 北京每天直达上海的客车有 5 次，客 机有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 =
6、 8 种。 1.1 加法法则与乘法法则 乘法法则 设事件A有m种产生式， 事件B有n种产生方式，则事件A与B有 m n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。 1.1 加法法则与乘法法则 例 某种字符串由两个字符组成，第一个 字符可选自a，b，c，d，e，第二个字符 可选自1，2，3，则这种字符串共有5 3 = 15 个。 例 从A到B有三条道路，从B到C有两条 道路，则从A经B到C有32=6 条道路。 1.1 加法法则与乘法法则 n n 例例 某种样式的运动服的着色由底色和装某种样式的运
7、动服的着色由底色和装 饰条纹的颜色配成。底色可选红、蓝、饰条纹的颜色配成。底色可选红、蓝、 橙、黄，条纹色可选黑、白，则共有橙、黄，条纹色可选黑、白，则共有4 4 2 2 = 8= 8种着色方案。种着色方案。 n n 若此例改成底色和条纹都用红、蓝、橙若此例改成底色和条纹都用红、蓝、橙 、黄四种颜色的话，则，方案数就不是、黄四种颜色的话，则，方案数就不是4 4 4 = 16 4 = 16， 而只有而只有 4 4 3 = 12 3 = 12 种。种。 n n 在乘法法则中要注意事件在乘法法则中要注意事件 A A 和和 事件事件 B B 的的 相互独立性。相互独立性。 1.1 加法法则与乘法法则
8、例例 1)1)求小于求小于1000010000的含的含1 1的正整数的个数的正整数的个数 2)2)求小于求小于1000010000的含的含0 0的正整数的个数的正整数的个数 1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有999916560个. 含1的有：99996560=3439个 另: 全部4位数有10 个,不含1的四位数有9 个, 含1的4位数为两个的差: 10 9 = 3439个 4 4 4 4 2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。 不含0的1位数有9个，2位数有9 个， 3位数有9
9、个，4位数有9 个 不含0小于10000的正整数有 9+9 +9 +9 =(9 9)/(91)=7380个 含0小于10000的正整数有 99997380=2619个 2 34 2345 1.2排列与组合 定义定义 从从n n个不同的元素中，取个不同的元素中，取r r个不重个不重 复的元素，按次序排列，称为从复的元素，按次序排列，称为从n n个中取个中取 r r个的个的无重排列无重排列。排列的全体组成的集合。排列的全体组成的集合 用用 P(n,r)P(n,r)表示。排列的个数用表示。排列的个数用P(n,r)P(n,r)表表 示。当示。当r=nr=n时称为时称为全排列全排列。一般不说可重。一般不
10、说可重 即无重。可重排列的相应记号为即无重。可重排列的相应记号为 - - P(n,r) P(n,r), ,P(n,r)P(n,r)。 l 1.2排列与组合 定义从定义从n n个不同元素中取个不同元素中取r r个不重复的元素个不重复的元素 组成一个子集，而不考虑其元素的顺序，组成一个子集，而不考虑其元素的顺序， 称为从称为从n n个中取个中取r r个的个的无重组合无重组合。 组合的全体组成的集合用组合的全体组成的集合用C(n,r)C(n,r)表示，组表示，组 合的个数用合的个数用C(n,r)C(n,r)表示，对应于可重组合表示，对应于可重组合 - - 有记号有记号C C(n,r)(n,r), ,
11、C(n,r)C(n,r)。 1.2排列与组合 从从n n个中取个中取r r个的排列的典型例子是从个的排列的典型例子是从n n 个不同的球中个不同的球中, ,取出取出r r个个, ,放入放入r r个不同的个不同的 盒子里盒子里, ,每盒每盒1 1个。第个。第1 1个盒子有个盒子有n n种选择种选择 ，第，第2 2个有个有n-1n-1种选择，种选择，第，第r r个有个有n n -r+1-r+1种选择。种选择。 故有故有 P(n,r)=n(n-1)P(n,r)=n(n-1)(n-r+1)(n-r+1) 有时也用有时也用nn r r 记记n(n-1)n(n-1)(n-r+1)(n-r+1) 1.2排列
12、与组合 若球不同，盒子相同，则是从若球不同，盒子相同，则是从n n个中取个中取r r个个 的的组合组合的模型。若放入盒子后再将盒子标的模型。若放入盒子后再将盒子标 号区别，则又回到排列模型。每一个组合号区别，则又回到排列模型。每一个组合 可有可有r!r!个标号方案。个标号方案。 故有故有 C(n,r)C(n,r) r!=P(n,r),r!=P(n,r), C(n,r)C(n,r)=P(n,r)/r!=n=P(n,r)/r!=n r r /r!=/r!= ( ( ) )= = 易见易见 P(n,r)=nP(n,r)=n n r r n! r!(n-r)! 1.2排列与组合 例例 有有5 5本不同
13、的日文书，本不同的日文书，7 7本不同本不同 的英文书，的英文书，1010本不同的中文书。本不同的中文书。 1)1)取取2 2本不同文字的书；本不同文字的书； 2)2)取取2 2本相同文字的书；本相同文字的书； 3)3)任取两本书任取两本书 1.2排列与组合 解解 1) 57+510+710=155;1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; =10+21+45=76; 3) 155+76=231=( ) 3) 155+76=231=( ) 5+7+10 2 1.2排列与组
14、合 例例 从从1,3001,300中取中取3 3个不同的数，使这个不同的数，使这 3 3个数的和能被个数的和能被3 3整除，有多少种方案？整除，有多少种方案？ 解 将1,300分成3类： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法： 1)3个数同属于A;2)3个数同属于B 3)3个数同属于C;4)A,B,C各取一数. 故共有3C(100,3)+100 =485100+1000000=1485100 3 1.2排列与组合 例例 某车站有某车站有6 6个入口处，每个入口
15、处每个入口处，每个入口处每 次只能进一人，一组次只能进一人，一组9 9个人进站的方案有多个人进站的方案有多 少？少？ 解一进站方案表示成：00011001010100 其中“0”表示人，“1”表示门框，其中“0”是 不同元，“1”是相同元。给“1”n个门只用n-1 个门框。任意进站方案可表示成上面14个 元素的一个排列。 1.2排列与组合 解法解法11标号可产生标号可产生5!5!个个1414个元的全排列个元的全排列 。 故若设故若设x x为所求方案，则为所求方案，则 x x 5!=14!5!=14! x=14!/5!=726485760 x=14!/5!=726485760 1.2排列与组合 解法解法22在在1414个元的排列中先确定个元的排列中先确定 “1”1”的位置，有的位置，有C(14,5)C(14,5)种选择，在种选择，在 确定人的位置，有确定人的位置，有9 9！种选择。！种选择。 故 故 C(14,5)C(14,5) 9!9! 即所求 即所求 1.2排列与组合 解法解法33把全部选择分解成若干步，使每步把全部选择分解成若干步，使每步 宜于计算。不妨设宜于计算。不妨设9 9个人编成个人编成1 1至至9 9号。号。1 1号号 有有6 6种选择；种
