《排列组合公式》PPT课件.ppt

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

1、排列组合公式排列组合公式非降路径问题组合恒等式排列与组合从五个候选人中选出两个代表把5本不同的书安排在书架上从五个候选人中选出两个代表时，有10种可能的结果。把5本不同的书安排在书架上有120种方法选出-组合；安排-排列一、排列组合公式排列问题：从某个集合中有序地选取若干个元素的问题组合问题：从某个集合中无序地选取若干个元素的问题注意：可以重复不能重复排列无重排列可重排列从{1,2,…,9}中选取数字构成四位数，使得每位数字都不同，有多少个？从{1,2,…,9}中选取数字构成四位数，使得不同数位上的数字可以相同，有多少个？1、无重排列n个元素的r-无重排列数：排列的长度r计

2、算（一般情形）：乘法原理r=n时,n个元素的全排列r=0时r>n时2、可重排列n个元素的r-可重排列数计算（乘法原理）例题在1和10,000,000,000之间的一百亿个数中，有多少个数含有数码1？又有多少个数不含数码1？不含1:910含1:1010-910+1例题一个二元序列是由一些0和1所组成的序列。n码二元序列指该序列中数码的个数为n。试问，含有偶数个0的n码二元序列的个数是多少？2n-1考虑n码四元序列，即以0,1,2和3为其数码的序列。则含0和1的总个数为偶数的序列有多少个？4n/2例题求n码四元序列中含有偶数个0的个数？放球问题设n≥r，把r个不同的球放入n个不

3、同的盒子，这里每一盒最多只能装一物，允许空盒。放球的方法数为多少？第一个球有n种选法，第二个球有n-1种，等等，乘法原理P(n,r)放球问题把r个不同的球放入n个不同的盒子，一个盒中可以放多个球，也允许空盒。放球的方法数为多少？第一个球有n种选法，第二个球有n种，等等，乘法原理nr这里n和r的大小没有限制例子将3封信向2个信箱投寄，有多少种投寄方法？23=8无序占位模型：不考虑盒子中的排列次序放球问题把r个不同的球放入n个不同的盒子，一个盒中可以放多个球，也允许空盒。考虑每个盒子中球的次序。放球的方法数为多少？有序占位模型有n种方法放第一个球，第一个球放入一个盒后，可以把这

4、个球当成是一个添加的隔板，它把该盒分成两个盒，因此放第二个球有n+1种方法。等等n(n+1)(n+2)…(n+r-1)=[n]rF(n,r)r!例子某车站有6个进站口，今有9人进站，有多少种不同的进站方法？[6]9=6×7×…×14七部汽车通过五间收费亭的方式数？今欲在五根旗杆上悬挂七面不同的旗子，全部旗都得展示出来，但并非所有的旗杆都得使用，问有多少种安排的方法？放球问题另解：把这样一个方法设想为r个不同的球和n-1个相同的盒间板的一个有序安排。组合无重组合可重组合从{a,b,c}中选取2个不同元素，选法数是多少？从{a,b,c}中选取5个元素，元素可以相同，选法数是多少

5、？3、无重组合（Combination）n个元素的r-无重组合数无重组合数与无重排列数的关系计算r=0时r=n时r>n时组合数的推广几个记号下阶乘函数上阶乘函数计算例题如果一个凸十边形无三条对角线在这个十边形的内部交于一点，问这些对角线被它们的交点分成多少条线段？多边形例题对角线的条数为C(10,2)-10=45-10=35任选两条对角线，可能相交在多边形内部，可能交点为多边形的顶点，可能无交点（交点在多边形外）任选四个顶点，对应一个交点，每个对角线分成两段每个对角线是一段35+C(10,4)×2=455例题C(5,2)-5+C(5,4)×2=15C(10,2)-10+C(

6、10,4)×2=455C(4,2)-4+C(4,4)×2=44、可重组合n个元素的r-可重组合例子计算一一对应的思想推论方程x1+x2+…+xn=r的非负整数解的个数。n≤r时，此方程的正整数解的个数n元集合的r-可重组合数，要求每个元素至少出现一次。正整数r的n-长有序分拆的个数求x1+x2+x3+x4=20的整数解的数目，其中x1≥3,x2≥1,x3≥0,x4≥5。例题从为数众多的一分币、二分币、一角币和二角币中，可以有多少种方法选出六枚来？F(4,6)=C(4+6-1,6)=C(9,6)=84例题某糕点厂将8种糕点装盒，若每盒有一打糕点，求市场上能买到多少种该厂出品的

7、盒装糕点？某糕点厂将8种糕点装盒，若每盒有一打糕点，且要求每种糕点至少放一块。求市场上能买到多少种该厂出品的盒装糕点？例题摇三个不同的骰子的时候，可能的结果的个数是多少？63=216。如果这三个骰子是没有区别的，则可能结果的个数是多少？从1,2,3,4,5,6这六个数中允许重复地选出三个数。F(6,3)=C(6+3-1,3)=56将r个骰子掷一次，总共可以掷出多少种不同结果？F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5)有约束条件的排列：引例用两面红旗、三面黄旗依次悬挂在一根旗杆上，问可以组