文档介绍：组合数学
前言
组合数学是一个古老而又年轻的数学分支。
据传说,大禹在4000多年前就观察到神龟背上的幻方……
幻方可以看作是一个3阶方阵,其元素是1到9的正整数,每行、每列以
及两条对角线的和都是15。
贾宪北宋数学家(约11世纪)著有《黄帝九章细草》、《算法斅古集》
斅(音'笑')(“古算法导引”)都已失传。杨辉著《详解九章算法》(1261年)中曾
引贾宪的“开方作法本源”图(即指数为正整数的二项式展开系数表,现称“杨
辉三角形”)和“增乘开方法”(求高次幂的正根法)。前者比帕斯卡三角形
早600年,后者比霍纳(William Geoge Horner,1786—1837)的方
法(1819年)早770年。
1666年莱布尼兹所著《组合学论文》一书问世,这是组合数学的第一部专著。binatorics)一词。
组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广,内容庞杂,并且仍在很快地发展着,因而
还没有一个统一而有效的理论体系。这与数学分析形成了对照。
本学期主要讲组合分析(计数和枚举)以及组合优化的一部分(线性规划的单纯形解法)。
组合分析是组合算法的基础。
组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是,要学好组合数学并
非易事, 既需要一定的数学修养,也要进行相当的训练。
file:///I|/待整理/待整理课件-小/组合数学/[2010-6-17 0:55:07]
Untitled Document
加法法则与乘法法则
[加法法则]设事件A有m种产生方式,事件B有n种产生方式,则事件A或B之一有m+n种产生方式。
集合论语言:若|A|=m,|B|=n,A∩B=φ,则|A∪B|=m+n。
[例]某班选修企业管理的有18人,不选的有10人,则该班共有18+10=28人。
[例]北京每天直达上海的客车有5次,客机有3次,则每天由北京直达上海的旅行方式有5+3=8种。
[乘法法则]设事件A有m种产生式,事件B有n种产生方式,则事件A与B有m·n种产生方式。
集合论语言:若|A|=m ,|B|=n,A×B={(a,b)|a∈A,b∈B},则|A×B|=m·n。
[例]某种字符串由两个字符组成,第一个字符可选自{a,b,c,d,e},第二个字符可选自{1,2,3},则这种
字符串共有5×3=15个。
[例]从A到B有三条道路,从B到C有两条道路,则从A经B到C有3×2=6条道路。
[例]某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄,条纹色可选黑、白,
则共有4×2=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话,则方案数就不是
4×4=16,而只有4×3=12种。
在乘法法则中要注意事件A和事件B的相互独立性。
[例]1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数
1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有9×9×9×9-1=:9999-
6560=3439个
另: 全部4位数有104个,不含1的四位数有94个,含1的4位数为两个的差:104-94=3439个
2)“含0”和“含1”不可直接套用。0019含1但不含0。
在组合的习题中有许多类似的隐含的规定,要特别留神。
不含0的1位数有9个,2位数有92个,3位数有93个,4位数有94个
file:///I|/待整理/待整理课件-小/组合数学/[2010-6-17 0:55:19]
Untitled Document
不含0小于10000的正整数有9+92+93+94=(95-9)/(9-1)=7380个
含0小于10000的正整数有9999-7380=2619个
file:///I|/待整理/待整理课件-小/组合数学/[2010-6-17 0:55:19]
Untitled Document
[定义]从n个不同的元素中,取r个不重复的元素,按次序排列,称为从n个中取r个的无重排列。排列的全体组
成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的
相应记号为P(n,r),P(n,r)。
[定义]从n个不同元素中取r个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从n个中取r个的无重
组合。
组合的全体组成的集合用C(n,r)表示,组合的个数用C(n,r)表示