《组合数学讲》PPT课件.ppt

《《组合数学讲》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前言组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方…...幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学研

2、究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。第一章排列与组合1.1加法法则与乘法法则.[加法法则]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若

3、A

4、=m,

5、B

6、=n,AB=,则

7、AB

8、=m+n。第一章

9、排列与组合[例]某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。[例]北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。第一章排列与组合[乘法法则]设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若

10、A

11、=m,

12、B

13、=n,AB={(a,b)

14、aA,bB},则

15、AB

16、=m·n。第一章排列与组合[例]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种

17、字符串共有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的不含

18、1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含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个不含0小于10000的正整数有9+92+93+94=(95－1)/(9－1)=7380个含0小于10000的

19、正整数有9999－7380=2619个第一章排列与组合1.2排列与组合定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。nr若取出r个元素而不考虑次序，则称从n个不同元中取r个元的组合。其组合的个数记为C(n,r)或（）第一章排列与组合规定：从n个不同元中取n个的排列称为n的全排列第一章排列与组合我们有下列排列与组合的计数公式：特别地，对于全排列有P(n,n)=n!。第一章排列与组合从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,

20、放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有P(n,r)=n(n-1)···(n-r+1)有时也用[n]r记P(n,r)第一章排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),nrn!———r!(n-r)!C(n,r)=P(n,r)/r!=[n]r/r!=()=第一章排列与组合例有5本不同的日文书，7本不同的

21、英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书请问有多少种不同的取法？解：1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()5+7+102第一章排列与组合例从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解：将[1,300]分成3类：A={