组合数学及其应用

《组合数学及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、组合数学前言组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方…...前言幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言组合数学是一个迷人的数学分支,它起源于古代的游戏和美学鉴赏.在现代科学技术的发展中,人们会面临各种各样的组合数学问题.组合数学在计算机科学中发挥着出极为重

2、要的作用.前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言组合数学的基本内容组合数学关心的事情是要按照一定方式“配置”一组事物，主要考虑以下几方面的问题.存在性：(2)计数与分类：主要内容(3)构造算法：部分内容(4)算法优化：前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练

3、。前言内容:高等数学(微积分,高等代数)计算机数学(离散数学,组合数学)意义:方法(用于编程),素质(全面,细致)难点:方法的应用,例题的题型和思路教材:4版为主讲课:听课为主,课件较完整,板书和说明多种思路的分析，实例的直观理解第一章排列组合1.1加法法则与乘法法则1.1加法法则与乘法法则假设：A和B是性质无关的两类事件。[加法法则]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若

4、A

5、=m,

6、B

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

8、AB

9、=m+n。1.1加法法则与乘

10、法法则[例]某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。[例]北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。[例]某班选音乐的有5人，选美术的有7人，则至少选其中之一的有7到12人。1.1加法法则与乘法法则[乘法法则]设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若

11、A

12、=m,

13、B

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

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

16、AB

17、=m·n。1.1加法法则与乘法法则[例]某种字符串由两

18、个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有53=15个。[例]从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。[例]某班选音乐的有5人，选美术的有7人，则同时选二者的有0到5人。1.1加法法则与乘法法则例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12

19、种。在乘法法则中要注意事件A和事件B的相互独立性。1.1加法法则与乘法法则例1-21)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数1)小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个另:全部4位数有个,不含1的四位数有个,含1的4位数为两个的差:=3439个[要点：含1的＝总数－不含1的]1.1加法法则与乘法法则1)小于100的不含1的正整数可看做2位数,但00除外.故有9×9－1＝80

20、个.(00,02,…,09,20,22,…,29,30,…,99)含1的有：99－80=19个(01,11,21,…,91,10,12,13,…,19)2)“含0”和“含1”不可直接套用。0019含1但不含0。直接套用,含0的(??)有：99－80=19个(00,10,20,…,90,01,02,03,…,09)其中:黄色的10个不是含0的.因此,修改计算方法为:不含0的1位数有9个，(1,2,…,9)2位数有个，(11,12,…,19,21,…,99)不含0小于100的正整数有81+9=90含0小于10

21、0的正整数有99－90=9个(10,20,…,90)2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含规定，要特别留神。不含0的1位数有9个，2位数有个，3位数有个，4位数有个不含0小于10000的正整数有含0小于10000的正整数有9999－7380=2619个1.1加法法则与乘法法则例1-3长度为n的0，1符号串的数目为设由乘法规则例如：n＝3，有8个000,001,010,011,1