组合数学概念简介.pptxVIP

1Combinatorics马昱春第一章排列组合

2说说数数这件事无重复，无遗漏

3第一章 排列组合1.1加法法则与乘法法则 分类计数和分步计数从甲地到乙地，可以乘火车，也可以乘汽车，一天中，火车有3班，汽车有2班．那么一天中，乘坐这些交通工具从甲地到乙地共有多少种不同的走法？解答：3＋2＝5种不同的走法从甲地到乙地，要从甲地选乘火车到丙地，再于次日从丙地乘汽车到乙地．一天中，火车有3班，汽车有2班．那么两天中，从甲地到乙地共有多少种不同的走法？解答：共有3×2＝6种不同的走法

41.1加法法则与乘法法则集合论语言：若|A|=m,|B|=n,A?B=?,则|A?B|=m+n。[例]某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。[加法法则TheSumRule]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。

51.1加法法则与乘法法则若|A|=m,|B|=n,A?B={(a,b)|a?A,b?B},01则|A?B|=m·n。02[乘法法则TheProductRule] 设事件A有m种产生方式，事件B有n种产生方式，则事件A与B有m·n种产生方式。03[例]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有5?3=15个。04集合论语言：

61.1加法法则与乘法法则若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4?4=16，而只有4?3=12种。在乘法法则中要注意事件A和事件B的相互独立性。例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4?2=8种着色方案。

71.1加法法则与乘法法则1)小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个另:全部4位数有104个,不含1的四位数有94个,含1的4位数为两个的差:104－94=3439个例1)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数

82)求小于10000的含0的正整数的个数“含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的正整数有9999－7380=2619个

91.2排列与组合定义[排列Permutation]从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)表示，或者。当r=n时称为全排列。一般不说可重即无重。定义[组合Combination]从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的个数用C(n,r)表示或者

101.2排列与组合从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有P(n,r)=n(n-1)······(n-r+1)=有时也用[n]r记n(n-1)······(n-r+1)全排列：P(n,n)=n!

111.2排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r)=C(n,r)=P(n,r)/r!=[n]r/r!==

12排列组合问题的来源排列组合问题，最早见于我国的《易经》一书．所谓“四象”就是每次取两个爻(yáo)的排列，“八卦”是每次取三个爻的排列．在汉代数学家徐岳的《数术记遗》（公元2世纪）中，也曾记载有与占卜有关的“八卦算”，即把卦按不同的方法在八个方位中排列起来．它与“八个人围一张圆桌而坐，问有多少种不同坐法”这一典型的排列问题类似．11世纪时，邵雍还进一步研究了六十四卦的排列问题唐朝僧人一行曾经研究过围棋布局的总数问题．古代的棋盘共有17路，2