组合数学4_排列组合

《组合数学4_排列组合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学Combinatorics陈卫东chenwd@scnu.edu.cn华南师范大学计算机学院2007-10-120存在性问题、计数问题、鸽笼原理、容斥原理、构造性问题、组合优化排列组合、母函数、Pólya计数法数学归纳法、搜索技术…组合问题组合原理、方法组合数学2007-10-121¾计数问题常用解法V排列组合V递归方程V搜索技术2007-10-122排列与组合ß基本原理、方法V排列组合V排列组合的生成算法V递归方程的编程求解（递推计算）ß应用举例V方程解的个数V购票问题2007-10-1231.排列组合[例]　下图所示的棋盘中，若要从左下角走到右

2、上角，并且规定只能向右或者想上走，问有多少种方案？2007-10-1241.排列组合加法原理设事件A有m种产生方式，另一事件B有n种不同的产生方式，则产生事件A或B之一有m+n种方式。集合论语言：若

3、A

4、=m,

5、B

6、=n,A∩B=∅,则

7、A∪B

8、=m+n。2007-10-1251.排列组合乘法原理设事件A有m种产生式，另一事件B有n种不同的产生方式，则同时产生事件A与B有m·n种方式。集合论语言：若

9、A

10、=m,

11、B

12、=n,A×B={(a,b)

13、a∈A,b∈B},则

14、A×B

15、=m·n。2007-10-1261.排列组合[例]北京每天直达上海的客车有5次，客

16、机有3次，则每天由北京直达上海的旅行方式有5+3=8种。[例]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有5×3=15个。2007-10-1271.排列组合[例](1)求小于10000的含1的正整数的个数；(2)求小于10000的含0的正整数的个数。解答：(1)小于10000的不含1的正整数可看做4位数,但0000除外。故有9×9×9×9－1＝6560个。含1的有9999－6560=3439个。另:全部4位数有104个,不含1的四位数有94个,含1的4位数为两个的差:104－94=34

17、39个。2007-10-1281.排列组合[例](1)求小于10000的含1的正整数的个数；(2)求小于10000的含0的正整数的个数。解答：(2)不含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个。2007-10-1291.排列组合排列定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的一个无重排列。这样的排列的个数用P(n,r)表示。当r=n时称为全排列。200

18、7-10-12101.排列组合排列公式从n个中取r个排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有P(n,r)=n(n-1)······(n-r+1)特别，P(n,n)=n！2007-10-12111.排列组合组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个n中取r个的一个无重组合。这种组合的个数用()r或C(n,r)表示。2007-10-12121.排列组合组合公式若球不同，盒子相同，则是从n个中

19、取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),C(n,r)=P(n,r)/r!n!=———r!(n-r)!2007-10-12131.排列组合组合公式的性质C(n,r)=C(n,n-r)C(n,r)=C(n-1,r)+C(n-1,r-1)nn即()=()，rn-rnn-1n-1()=()+()rrr-12007-10-12141.排列组合[例]有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书.2

20、007-10-12151.排列组合解答：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或，()=2315+7+1022007-10-12161.排列组合重复排列求r个1,r个2,…,r个t的全排列个数P(n;r,r,…,r),12t12tn也记作()r1,r2,…,rt设r+r+…+r=n,对1，2，…，t分别加下标，得到12tP(n；r,r,…,r)·r!r!…r!=n!12t12tn!∴P(n；r,r,…,r)=————12tr!r!…r!12t2007-10-

21、12171.排列组合圆排列从n个中取r个的圆排列的排列数为P(n,r)/r,1≤