组合-chapt2-16排列与组合.ppt
组合数学组合数学第第2章章 排列与组合排列与组合主要内容：主要内容：1.基本的计数原理及其应用基本的计数原理及其应用2.集合的排列与组合集合的排列与组合3.多重集的排列与组合多重集的排列与组合基本计数原理基本计数原理(P16-17)加法原理加法原理:设设 S=S1 Sm,且且 Si Sj=(i j)则则|S|=|S1|+|Sm|.乘法原理乘法原理:设设S是由是由(a,b)组成的集合组成的集合,其中其中a有有p种选择种选择,且对且对a的每种选择的每种选择,b有有q种选择种选择,则则|S|=p q.乘法原理应用乘法原理应用(P17)例例:确定确定34 52 117 138的正整数因子的个数的正整数因子的个数.解解:其正整数因子的形式为其正整数因子的形式为 3i 5j 11m 13n,其中其中 0 i 4,0 j 2,0 m 7,0 n 8.i有有5种选择种选择;对对i的每种选择的每种选择,j有有3种选择种选择;对对j的每种选择的每种选择,m有有8种选择种选择;所以根据乘法原理所以根据乘法原理,正整数因子的个数是正整数因子的个数是 5 3 8 9=1080.例例(P19)例例.求求10009999之间具有不同数字的奇数的个数之间具有不同数字的奇数的个数解解:1.个位个位有有|1,3,5,7,9|=5 种选择种选择 2.千位千位有有|1,9|-1 =8 种选择种选择 3.百位百位有有|0,1,9|-2 =8 种选择种选择 4.十位十位有有|0,1,9|-3 =7 种选择种选择 总个数总个数=5 8 8 7=2240.换次序换次序:1.百位有百位有|0,1,9|=10 种选择种选择 2.个位有个位有|1,3,5,7,9|-?种选择种选择 当百位是偶数时当百位是偶数时,个位有个位有5种选择种选择;当百位是奇数时当百位是奇数时,个位有个位有4种选择种选择.不能直接用不能直接用乘法原理乘法原理集合与多重集的记法集合与多重集的记法(P19)集合集合:不能重复不能重复,没有次序没有次序 a,b,b =a,b 多重集多重集:可以重复可以重复,没有次序没有次序 a,b,b =b,a,b a,b 多重集的记法多重集的记法:M=a,a,a,b,c,c,d,d,d,d:=3 a,b,2 c,4 d N=a,2 b,c,4 d集合的排列与组合集合的排列与组合(P21,24)令令S是集合是集合,|S|=n,r 0,S的一个的一个r-排列排列是是 S中中r个元素的有序摆放个元素的有序摆放.S的一个的一个r-组合组合是是 S中中r个元素的无序选择个元素的无序选择,或者说是或者说是 S的的r个元素的子集个元素的子集.例例:S=a,b,cS的的1-排列排列:a,b,c,1-组合组合:a,b,cS的的2-排列排列:ab,ca,2-组合组合:a,b,b,c,a,cS的的3-排列排列:cab,3-组合组合:a,b,cS的的4-排列排列:?4-组合组合:?S的的0-排列排列:?0-组合组合:,1个个排列数与组合数排列数与组合数(P21-27)用用P(n,r)表示表示n元素集合的元素集合的r-排列的个数排列的个数用用C(n,r)表示表示n元素集合的元素集合的r-组合的个数组合的个数定理定理1:0 r n,P(n,r)=n!/(n-r)!(乘法原理乘法原理)定理定理2:0 r n,C(n,r)=n!/(n-r)!/r!(双计数双计数)通常记通常记C(n,r)为为定理定理3:C(n,r)=C(n,n-r).定理定理4:C(n,0)+C(n,1)+C(n,n)=2n.例例(P22-25)例例1:平面上平面上25个点个点,无无3点共线点共线,求他们所确定的直线数和三角形数求他们所确定的直线数和三角形数.例例2:排列排列26个字母个字母,a,e,i,o,u两两不相邻两两不相邻,求方案数求方案数.定义定义:循环排列循环排列,即沿圆圈排列即沿圆圈排列.定理定理:n元素集合的循环元素集合的循环r-排列的个数是排列的个数是 P(n,r)/r.例例3.8个不同颜色念珠穿成一条项链个不同颜色念珠穿成一条项链,求方案数求方案数.例例4.10人围坐一圆桌人围坐一圆桌,其中两个不相邻其中两个不相邻,求方案数求方案数.与例与例2比较比较.多重集的排列和组合多重集的排列和组合(P28)特点特点:每个元素可以出现每个元素可以出现0到多次到多次.例例:S=2 a,b,3 cS的的4-排列有排列有 abac,cacc 等等S的的4-组合有组合有 2 a,b,c,a,3 c 等等S的的6-排列有排列有 abccac 等等S的的6-组合有组合有 2 a,b,3 cS的的7-排列排列 无无,S的的7-组合组合 无无.两个简单情况两个简单情况(P28,32)定理定理1:设设S=n1 a1,n2 a2,nk ak,且且|S|=n1+nk=n,则则 S 的全排列数是的全排列数是 =C(n,n1)C(n-n1,n2)定理定理2:设设 S=a1,a2,ak,r 0,则则S的的r-排列个数是排列个数是kr,S的的r-组合个数是组合个数是C(r+k-1,r).r-排列排列:等价于等价于r个位置个位置,每个位置每个位置k种选择种选择 r-组合数组合数 依次等价于依次等价于 1.不定方程不定方程 x1+x2+xk=r 的非负整数解个数的非负整数解个数 2.将将r个相同球放入个相同球放入k个不同盒子的方案数个不同盒子的方案数 3.将将r个相同球个相同球(0)与与k-1个相同间隔个相同间隔(1)全排列的方案数全排列的方案数 例例(P29,31,34)例例1.求求MISSISSIPPI中字母的排列数中字母的排列数.例例2.S=3 a,2 b,4 c,求求S的的8排列的个数排列的个数.例例3.一面包房生产一面包房生产8种炸面包圈种炸面包圈,若一打面包一盒若一打面包一盒,求不同盒数求不同盒数.例例4.不定方程不定方程 x1+x2+x3+x4=20,其中其中 x1 3,x2 1,x3 0,x4 5,求其整数解的数目求其整数解的数目.本章小结与作业本章小结与作业 集合集合:排列组合排列组合 容易容易多重集多重集:无个数限制的排列组合无个数限制的排列组合 容易容易 有限多重集的全排列有限多重集的全排列 容易容易 有限多重集的部分排列组合有限多重集的部分排列组合 困难困难 作业作业:第第2章章 P37:ex5,11,27,32,37,51.编程题编程题:crazy tea party作业作业P37:ex5.确定作为下列各数的因子的确定作为下列各数的因子的10的最大幂的最大幂(等价于用通常等价于用通常的的10进制表示时尾部进制表示时尾部0的个数的个数)：(a)50!,(b)1000!ex11.从数集从数集1,2,20中形成中形成3个数的集合，如果没有个数的集合，如果没有2个相连个相连的数字在同一个集合中，那么能形成多少个的数字在同一个集合中，那么能形成多少个3个数的集合。个数的集合。ex27.5个没有区别的车放在个没有区别的车放在8 8棋盘上，棋盘上，使得使得没有车能够攻击没有车能够攻击 别的车并且第一行和第一列都不空的放置方式有多少？别的车并且第一行和第一列都不空的放置方式有多少？ex32.确定下面的多重集合的确定下面的多重集合的11排列的数目：排列的数目：S=3 a,4 b,5 c。ex37.一家面包店销售一家面包店销售6种不同类型的酥皮糕点。如果该店每种种不同类型的酥皮糕点。如果该店每种 糕点至少有一打，那么可能配置成多少打不同类型的酥皮糕点？糕点至少有一打，那么可能配置成多少打不同类型的酥皮糕点？如果在一盒中每种糕点至少有一块，又能有多少打？如果在一盒中每种糕点至少有一块，又能有多少打？ex51.考虑大小为考虑大小为3n+1的多重集合的多重集合n a,n b,1,2,3,n+1，确定它的确定它的n组合数。组合数。
