《离散第讲容斥原理与排列组合.ppt》由会员分享，可在线阅读，更多相关《离散第讲容斥原理与排列组合.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、vv离散第讲容斥原理与排列组合离散第讲容斥原理与排列组合现在学习的是第1页，共43页vvPowerPoint Template_Sub PowerPoint Template_Sub 鸽笼原理鸽笼原理N+1只鸽子飞进只鸽子飞进N只笼子，至少有只笼子，至少有2只鸽子飞进同一笼子只鸽子飞进同一笼子m个对象放入个对象放入n个盒子，有一个盒子至少放入个盒子，有一个盒子至少放入 个对象个对象计数问题计数问题排列、组合排列、组合重新排列单词重新排列单词SUCCESS中的字母能得到多少不同的字符串？中的字母能得到多少不同的字符串？组合数学组合数学研究给定模式下研究给定模式下配置的存在性、配置的数目、可能的配
2、置、配置的性质配置的存在性、配置的数目、可能的配置、配置的性质等等鸽笼原理讨论可能鸽笼原理讨论可能配置的存在性配置的存在性，计数则解决，计数则解决配置数目的计算配置数目的计算问题，问题，广泛应用于广泛应用于事件概率的计算事件概率的计算以及计算机以及计算机算法的复杂性算法的复杂性研究研究现在学习的是第2页，共43页vvPowerPoint Template_Sub PowerPoint Template_Sub 1计数基本原理计数基本原理2排列与组合排列与组合3重集的排列与组合重集的排列与组合第第3 3章章 组合合论基基础-计数数4递归关系递归关系现在学习的是第3页，共43页vv计数基本原理与排
3、列组合计数基本原理与排列组合计数基本原理与排列组合计数基本原理与排列组合Textbook Page 30 to 36Textbook Page 30 to 36离散数学离散数学离散数学离散数学第第第第5 5 5 5讲讲讲讲现在学习的是第4页，共43页v内容提要内容提要6.1 计数基本原理计数基本原理加法原理、乘法原理加法原理、乘法原理包含排斥原理（容斥原理）包含排斥原理（容斥原理）6.2 排列与组合排列与组合线排列、圆排列、组合线排列、圆排列、组合在回顾中学知识的基础上适度提高在回顾中学知识的基础上适度提高现在学习的是第5页，共43页v加法原理与乘法原理加法原理与乘法原理加法原理加法原理分类计
4、数分类计数：完成一件事有完成一件事有n类办法，在第类办法，在第1类办法中有类办法中有a1 种种 不同的方式，不同的方式，在第，在第n类办法中有类办法中有an 种不同的方式，那么种不同的方式，那么完成这件事共有完成这件事共有a1+an 种不同的方式种不同的方式若有限集合若有限集合S=S1S2 Sn，且，且S1,S2,Sn两两不相交，两两不相交，那么那么|S|=|S1|+|S2|+|Sn|乘法原理乘法原理分步计数分步计数：完成一个任务需要分成个步骤，做第：完成一个任务需要分成个步骤，做第1步有步有 a1 种不同的方式，种不同的方式，做第步有，做第步有an 种不同的方式，那么种不同的方式，那么 完完
5、成整个任务共有成整个任务共有a1a2 an种方式种方式对有限集合对有限集合S1,S2,Sn，|S1S2 Sn|=|S1|S2|Sn|现在学习的是第6页，共43页v应用应用例例1(例例3.2)一家服装厂用一家服装厂用4种式样，种式样，5种颜色，种颜色，8种尺寸生产种尺寸生产男式男式服装；服装；用用6种式样，种式样，5种颜色，种颜色，6种尺寸生产种尺寸生产女式女式服装，问这家服服装，问这家服装厂共计生产男女服装多少种？装厂共计生产男女服装多少种？解：男式服装种类：解：男式服装种类：458=160（种）（种）女式服装种类：女式服装种类：656=180（种）（种）共计：共计：160+180=340（种
6、）（种）加法原理加法原理乘法原理乘法原理乘法原理乘法原理现在学习的是第7页，共43页v应用应用例例2(例例3.1)从从上海直达天津上海直达天津可以乘坐汽车、火车和飞机旅行，已知汽可以乘坐汽车、火车和飞机旅行，已知汽车有车有3个班次，火车有个班次，火车有4个班次，飞机有个班次，飞机有2个班次。从个班次。从天津天津直达大连直达大连可以乘坐轮船和飞机旅行，已知轮船有可以乘坐轮船和飞机旅行，已知轮船有2个班次，个班次，飞机有飞机有3个班次。问从个班次。问从上海经天津到大连上海经天津到大连有多少种旅行安有多少种旅行安排？排？解：从上海到天津有解：从上海到天津有 3+4+2=9 种旅行安排种旅行安排 从天
7、津到大连有从天津到大连有 2+3=5 种旅行安排种旅行安排 从上海经天津到大连共有从上海经天津到大连共有 95=45 种旅行安排种旅行安排乘法原理乘法原理加法原理加法原理加法原理加法原理现在学习的是第8页，共43页v加法原理与乘法原理注意点加法原理与乘法原理注意点都是把一个事件分解成若干个分事件来完成都是把一个事件分解成若干个分事件来完成加法原理（分类计数原理）加法原理（分类计数原理）如果分事件如果分事件相互独立相互独立，分类完备分类完备，就用分类计数原理，就用分类计数原理注意：分类时要做到注意：分类时要做到不重不漏不重不漏乘法原理（分步计数原理）乘法原理（分步计数原理）如果分事件如果分事件相
8、互关联相互关联，缺一缺一 不可不可，就用分步计数原理，就用分步计数原理注意：分步时做到不缺注意：分步时做到不缺经常结合使用经常结合使用现在学习的是第9页，共43页v相交集合的计数相交集合的计数加法原理中，加法原理中，S1,S2,Sn两两不相交两两不相交，|S|=|S1|+|S2|+|Sn|若取消两两不相交的限制，该如何计算？若取消两两不相交的限制，该如何计算？考虑两个集合的情况考虑两个集合的情况AB现在学习的是第10页，共43页ABv相交集合的计数相交集合的计数加法原理中，加法原理中，S1,S2,Sn两两不相交两两不相交，|S|=|S1|+|S2|+|Sn|若取消两两不相交的限制，该如何计算？
9、若取消两两不相交的限制，该如何计算？考虑两个集合的情况考虑两个集合的情况|A|+|B|112|AB|现在学习的是第11页，共43页ABv相交集合的计数相交集合的计数加法原理中，加法原理中，S1,S2,Sn两两不相交两两不相交，|S|=|S1|+|S2|+|Sn|若取消两两不相交的限制，该如何计算？若取消两两不相交的限制，该如何计算？考虑两个集合的情况考虑两个集合的情况|A|+|B|AB|111|A B|=|A|+|B|AB|现在学习的是第12页，共43页v三个相交集合的计数三个相交集合的计数三个集合的情况三个集合的情况ABC|A|+|B|+|C|现在学习的是第13页，共43页v三个相交集合的计
10、数三个相交集合的计数三个集合的情况三个集合的情况ABC|A|+|B|+|C|1112223|AB|AC|BC|现在学习的是第14页，共43页v三个相交集合的计数三个相交集合的计数三个集合的情况三个集合的情况|A|+|B|+|C|AB|AC|BC|+|ABC|ABC11111130现在学习的是第15页，共43页v三个相交集合的计数三个相交集合的计数三个集合的情况三个集合的情况|A U B U C|=|A|+|B|+|C|AB|AC|BC|+|AB C|A|+|B|+|C|AB|AC|BC|+|ABC|ABC1111111现在学习的是第16页，共43页vn n个相交集合的计数个相交集合的计数定理定
11、理3.2考虑集合考虑集合S1,S2,Sn,S=S1S2Sn，那么，那么|S|=|S1S2Sn|验证：验证：n=1n=2n=3现在学习的是第17页，共43页v定理定理3.23.2的证明的证明用数学归纳法证明用数学归纳法证明|S1S2Sn|对对n进行归纳进行归纳基础步基础步：n=1,2时，根据上面的验证，等式成立；时，根据上面的验证，等式成立；归纳步归纳步：假设：假设n=k(k1)时等式成立，则时等式成立，则n=k+1时时等式依然成立等式依然成立综上，对任意自然数综上，对任意自然数n 1，均有等式成立，均有等式成立 课后自己看书现在学习的是第18页，共43页v另一种证明思路另一种证明思路从集合从集
12、合|S1S2Sn|中每个元素被计数的次数来考虑中每个元素被计数的次数来考虑设元素设元素a S1S2Sn，它恰在，它恰在Sa1,Sa2,Sar中出现中出现(1a1a2arn)则元素则元素a被被 因为因为 所以所以元素元素a恰被计数恰被计数1次次计数了计数了 次次计数了计数了 次次计数了计数了 次次计数了计数了 次次现在学习的是第19页，共43页v应用应用(例例3.3)试计算在集合试计算在集合1，2，3，1000中有多少元素至少能被中有多少元素至少能被5，6，8这三个数中的一个整除。这三个数中的一个整除。解解.用用A、B、C分别表示分别表示1000以内能被以内能被5、6、8整除的正整数整除的正整数
13、集合，题意为求集合，题意为求|ABC|一个数能被若干个数同时整除当且仅当这个数能被它们的一个数能被若干个数同时整除当且仅当这个数能被它们的最小公倍数整除最小公倍数整除|AB|=33|AC|=25|BC|=41|ABC|=8|ABC|=|A|+|B|+|C|AB|AC|BC|+|ABC|=400（个）（个）|A|=200|B|=166|C|=125现在学习的是第20页，共43页v应用应用学校学校1807个新生中有个新生中有453人选了计算机科学课，人选了计算机科学课，567人选了数学人选了数学 课，课，299人同时选了计算机科学课和数学课。问有多少学生人同时选了计算机科学课和数学课。问有多少学生
14、既没既没 选计算选计算机科学课又没选数学课机科学课又没选数学课？用用S表示全体新生，用表示全体新生，用A、B分别表示选了计算机科学课和数分别表示选了计算机科学课和数学课的新生集合。学课的新生集合。A S，B S。可把。可把S看作全集。看作全集。A 为没选计算机科学课的新生集合，为没选计算机科学课的新生集合，B 为没选数学课的新为没选数学课的新 生集合，目标是求生集合，目标是求|A B|A B=S(AB)|A B|=|S(AB)|=|S|AB|=|S|(|A|+|B|AB|)=1807 (453+567 299)=1086因此，共有因此，共有1086人人既没选计算机科学课又没选数学课既没选计算机
15、科学课又没选数学课现在学习的是第21页，共43页v容斥原理容斥原理容斥原理容斥原理(定理定理3.4)用用S1,S2,Sn分别表示集合分别表示集合S中具有中具有性质性质P1,P2,Pn元素元素集合，则集合，则S中中同时不具有这些性质同时不具有这些性质的元素个数为的元素个数为|S1 S2 Sn|现在学习的是第22页，共43页v应用应用例例3.3（2）试计算在集合试计算在集合1，2，3，1000中有多少元素不能被中有多少元素不能被5，6，8这三个数中的一个整除。这三个数中的一个整除。解解.用用A、B、C分别表示分别表示1000以内不能被以内不能被5、6、8整除的正整数集合，整除的正整数集合，题意为求
16、题意为求|A B C|一个数能被若干个数同时整除当且仅当这个数能被它们的一个数能被若干个数同时整除当且仅当这个数能被它们的最小公倍数整除最小公倍数整除|AB|=33|AC|=25|BC|=41|ABC|=8|A B C|=1000-|A|-|B|-|C|+|AB|+|AC|+|BC|-|ABC|=1000 400=600（个）（个）|A|=200|B|=166|C|=125现在学习的是第23页，共43页v应用应用已知：已知：密钥是密钥是长度为长度为L的的0，1序列序列，为安全起见，须对密钥进，为安全起见，须对密钥进 行变换。行变换。变换方式是：对于变换方式是：对于被被p整除和被整除和被q整除整
17、除的各位改变其的各位改变其奇奇 偶性偶性。问：问：作作此改变后，此改变后，最终未改变最终未改变奇偶性的有多少位？为了使未奇偶性的有多少位？为了使未 改变奇偶性的位改变奇偶性的位尽可能地少，尽可能地少，p,q 应满足什么性质？应满足什么性质？L=50，p=4，q=6用用S表示密钥各位的集合（全集），用表示密钥各位的集合（全集），用A、B分别表示分别表示被被4整整除除和和被被6整除整除 的各位组成的集合的各位组成的集合一次未改的密钥位集合为一次未改的密钥位集合为A B；改变两次，最终与原奇；改变两次，最终与原奇偶性相同的密钥位集合为偶性相同的密钥位集合为AB 根据容斥原理，根据容斥原理，|A B|
18、+|AB|=|S|A|B|+|AB|+|AB|最终有最终有38个密钥位未改变个密钥位未改变奇偶性奇偶性=38=38现在学习的是第24页，共43页v应用应用已知：已知：密钥是密钥是长度为长度为L的的0，1序列序列，为安全起见，须对密钥进行变换。，为安全起见，须对密钥进行变换。变换方式是：对于变换方式是：对于被被p整除和被整除和被q整除整除的各位改变其的各位改变其奇偶性奇偶性。问：问：作作此改变后，此改变后，最终未改变最终未改变奇偶性的有多少位？为了使未改变奇偶性的位尽奇偶性的有多少位？为了使未改变奇偶性的位尽可能地少，可能地少，p,q 应满足什么性质？应满足什么性质？12345678910 11
19、 1213 14 15 16 17 18 19 20 21 22 23 2425 26 27 28 29 30 31 32 33 34 35 3637 38 39 40 41 42 43 44 45 46 47 4849 50为使未改变奇偶性的位尽可能地少，为使未改变奇偶性的位尽可能地少，p,q p,q 应应互质互质 现在学习的是第25页，共43页v应用应用一次会议有一次会议有2005位数学家位数学家参加，每人至少有参加，每人至少有1337位合作者位合作者，求证：可，求证：可以找到以找到4位位数学家，他们中每两人都合作过。数学家，他们中每两人都合作过。记数学家们为记数学家们为a，b，与其合作过
20、的数学家集合分别记作，与其合作过的数学家集合分别记作A，B,。任取一数学家任取一数学家a，并取，并取b A（a与与b合作过）合作过）|A|1337，|B|1337，|AB|2005|AB|=|A|+|B|AB|1337220050 取取c AB（c与与a、b均合作过）均合作过）因为因为|ABC|=|AB|+|C|(AB)C|(133722005)+13372005=1因而存在数学家因而存在数学家d ABC，d与与a、b、c均合作过均合作过找到四位数学家找到四位数学家a、b、c、d，他们两两合作过，他们两两合作过 现在学习的是第26页，共43页v线排列的计数线排列的计数定义定义3.1：用用Pnr
21、或或P(n,r)表示表示“从从n个不同元素的集合中每次取出个不同元素的集合中每次取出r个元素进行个元素进行有序排列有序排列时可得到的排列的总数时可得到的排列的总数”。Pnr或或P(n,r)简称简称为为r-排列数排列数，P(n,n)简称为简称为n-全排列数全排列数定理定理3.5：对任意正整数对任意正整数n,r,rn,r-排列数是排列数是特别地，特别地，Pn1=n，Pnn=n！现在学习的是第27页，共43页v排列组合求解方法例排列组合求解方法例1 1：班里照相，班里照相，12人站一排。人站一排。8个男学员，个男学员，4个女学员，个女学员，要求女学员要排在一起，共有多少种不同的排法？要求女学员要排在
22、一起，共有多少种不同的排法？将将4个女学员看成是一个人个女学员看成是一个人,与与8个男学员作全排列，共个男学员作全排列，共P(9,9)种，种，4个女学员内部排列方式有个女学员内部排列方式有P(4,4)种，所以共种，所以共P(9,9)P(4,4)种种捆绑法捆绑法：要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题,可以用捆可以用捆绑法来解决。即将绑法来解决。即将需要相邻的元素合并为一个元素需要相邻的元素合并为一个元素,再与再与其它元素一起作排列，同时要其它元素一起作排列，同时要注意注意合并元素内部也可以作合并元素内部也可以作排列。排列。现在学习的是第28页，共43页v排列组合求解方
23、法例排列组合求解方法例2 2：班里照相，班里照相，12人站一排。人站一排。8个男学员，个男学员，4个女学员，要个女学员，要求女学员在男学员中间，且女学员互不相邻，共有多求女学员在男学员中间，且女学员互不相邻，共有多少种不同的排法？少种不同的排法？先排男学员共有先排男学员共有P(8,8)种排法。然后把女学员插入男学员之种排法。然后把女学员插入男学员之间的空档，共有间的空档，共有7个空档可插，选其中的个空档可插，选其中的4个空档个空档,共有共有P(7,4)种选法。根据乘法原理，共有不同排法种选法。根据乘法原理，共有不同排法P(8,8)P(7,4)种。种。插空法插空法：对于某两个元素或者几个元素要求
24、不相邻的问题：对于某两个元素或者几个元素要求不相邻的问题,可以用插空法。即可以用插空法。即先排好没有限制条件的元素先排好没有限制条件的元素,然后然后将有限制将有限制条件的元素按要求插到条件的元素按要求插到排好元素的空档之中即可。排好元素的空档之中即可。现在学习的是第29页，共43页v排列组合求解方法例排列组合求解方法例3 3：期末安排考试科目期末安排考试科目7门，英语要在离散数学之前考门，英语要在离散数学之前考,有多少种不同的安排顺序有多少种不同的安排顺序?不加任何限制条件，整个排法有不加任何限制条件，整个排法有P(7,7)种。种。“英语安排在英语安排在离散数学之前考离散数学之前考”与与“离散
25、数学安排在英语之前考离散数学安排在英语之前考”的的排法是相等的，所以英语安排在离散数学之前考的排法排法是相等的，所以英语安排在离散数学之前考的排法共有共有 P(7,7)/2 种。种。对等法对等法：在有些题目中，限制条件的肯定与否定是对等在有些题目中，限制条件的肯定与否定是对等的，各占全体的的，各占全体的二分之一二分之一。在求解中只要求出全体。在求解中只要求出全体,就可就可以得到所求。以得到所求。现在学习的是第30页，共43页v例例3.43.4有多少个大于有多少个大于5400，又同时满足下列两个性质的整数：（，又同时满足下列两个性质的整数：（1）各）各位数字均不相同；（位数字均不相同；（2）不出
26、现数字）不出现数字2和和7解：解：不能出现数字不能出现数字2和和7，且各位数字均不相同，所以只能是四、五、六、，且各位数字均不相同，所以只能是四、五、六、七、八位数七、八位数1)对五、六、七、八位数来说，第一位只能从对五、六、七、八位数来说，第一位只能从1、3、4、5、6、8、9中选取，中选取，即共有即共有7种可能，其他各位可从剩余的种可能，其他各位可从剩余的7个数字中选择进行排列，共有个数字中选择进行排列，共有P(7,i)种（种（i=4,5,6,7）所以：五、六、七、八位数共有所以：五、六、七、八位数共有7 P(7,4)+7 P(7,5)+7 P(7,6)+7 P(7,4)+7 P(7,5)
27、+7 P(7,6)+7 P(7,7)=P(7,7)=9408094080 个满足条件。个满足条件。2)对于四位数来说，对于四位数来说，2.1)若第一位大于若第一位大于5（共有（共有3种可能），则其余种可能），则其余3位可从剩余的位可从剩余的7个数字选取个数字选取3个个排列，即共有排列，即共有3*P(7,3)=630 个。个。2.2)若第一位为若第一位为5，则第二位只能从，则第二位只能从4、6、8、9种选择，其余种选择，其余2位可从剩余的位可从剩余的6个数字选取个数字选取2个排列，即共有个排列，即共有1*4*P(6,2)=120 个。个。综上，根据加法原理，共有综上，根据加法原理，共有94080
28、+630+120=94830 个个现在学习的是第31页，共43页v圆排列的计数圆排列的计数定义定义(圆排列圆排列)：从从n个不同元素的集合中每次取出个不同元素的集合中每次取出r个元素，围绕个元素，围绕一个圆周进行有序排列的排列总数（可旋转，但不可翻转）一个圆周进行有序排列的排列总数（可旋转，但不可翻转）对于圆排列对于圆排列(1,2,3,4,5)12345(1,2,3,4,5)(2,3,4,5,1)(3,4,5,1,2)(4,5,1,2,3)(5,1,2,3,4)一个圆排列对应一个圆排列对应r r个线排列个线排列线排列数是圆排列数的线排列数是圆排列数的r r倍倍现在学习的是第32页，共43页v圆
29、排列圆排列的计数的计数定理定理3.6：对任意正整数对任意正整数n,r,rn,从从n个不同元个不同元素的集合中每次取出素的集合中每次取出r个元素，围绕一个圆周进个元素，围绕一个圆周进行有序排列时可得到的排列的总数是行有序排列时可得到的排列的总数是：现在学习的是第33页，共43页v例例3.53.5六位女士和六位先生围着一张圆桌聚餐，要求安排六位女士和六位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问有多少可能的安排方案？女士和先生交替就座。问有多少可能的安排方案？解：解：可分为两个步骤来分配座位：先安排女士就座，两人之间留可分为两个步骤来分配座位：先安排女士就座，两人之间留一个空位，然后再安
30、排先生就座。一个空位，然后再安排先生就座。安排女士就座的方案共有安排女士就座的方案共有 种（种（圆排列圆排列）安排好女士后，再安排先生就座时，是安排好女士后，再安排先生就座时，是线排列线排列而非圆排列问题，因为而非圆排列问题，因为此时已经有了女士作参照，相同的圆排列与女士圆排列对齐方式此时已经有了女士作参照，相同的圆排列与女士圆排列对齐方式不同将导致不同的就座方案。因此，对每一种女士就座方式，可不同将导致不同的就座方案。因此，对每一种女士就座方式，可有有 P(6,6)=720 种男士就座方式。种男士就座方式。根据根据乘法原理乘法原理，共有，共有120 720=86400 种就座方案。种就座方案
31、。现在学习的是第34页，共43页v例例五对夫妇围着一张圆桌聚餐，试问每对夫妻相邻而五对夫妇围着一张圆桌聚餐，试问每对夫妻相邻而坐的方式有多少种？坐的方式有多少种？解：解：分为两步：第一步先安排五对夫妇的位置，第二步再具分为两步：第一步先安排五对夫妇的位置，第二步再具体安排每对夫妻两人的相对位置。体安排每对夫妻两人的相对位置。第一步共有第一步共有圆排列圆排列 种；种；第二步每对夫妻都有两种相对坐法，因此共有第二步每对夫妻都有两种相对坐法，因此共有25=32种坐法种坐法（乘法原理乘法原理）。）。根据根据乘法原理乘法原理，共有，共有24 32=768种就座方式。种就座方式。现在学习的是第35页，共4
32、3页v例例A、B、C、D、E、F六人围圆桌而坐，若六人围圆桌而坐，若A、B、C三人相邻，共有多少种坐法？三人相邻，共有多少种坐法？解：解：第一步将第一步将A、B、C看成一个整体，将其与看成一个整体，将其与D、E、F一起分一起分配座位，共有配座位，共有 就座方式；就座方式；第二步规定第二步规定A、B、C的座位，此时为的座位，此时为线排列问题线排列问题，共有，共有P(3,3)=6种安排方式。种安排方式。根据根据乘法原理乘法原理，一共有，一共有6 6=36种坐法种坐法。现在学习的是第36页，共43页v组合的计数组合的计数定义定义3.2：用用Cnr或或C(n,r)表示表示“从从n个元素的集个元素的集合
33、中每次取出合中每次取出r个元素（不进行有序排列）组成个元素（不进行有序排列）组成子集合的总数子集合的总数”。Cnr或或C(n,r)简称为简称为r-组合数组合数定理定理3.7：对任意正整数对任意正整数n,r,rn,r-组合数是组合数是：现在学习的是第37页，共43页v例例若数学系有若数学系有9名教师，计算机科学系有名教师，计算机科学系有11名，现要名，现要求由求由3名数学系教师和名数学系教师和4名计算机科学系教师组成名计算机科学系教师组成离散数学课程组，共有多少种可能的方案？离散数学课程组，共有多少种可能的方案？解：解：根据根据乘法原理乘法原理，共有，共有 种方案种方案。现在学习的是第38页，共
34、43页v排列组合求解方法例排列组合求解方法例4 4：班里有班里有43位同学，从中任抽位同学，从中任抽5人，正、副班长、人，正、副班长、团支部书记至少有一人在内的抽法有多少种团支部书记至少有一人在内的抽法有多少种?43人中任抽人中任抽5人的方法有人的方法有C(43,5)种，正副班长、团支种，正副班长、团支部书记都不在内的抽法有部书记都不在内的抽法有C(40,5)种，所以正副班长、种，所以正副班长、团支部书记至少有团支部书记至少有1人在内的抽法有人在内的抽法有C(43,5)-C(40,5)种种排异法排异法:有些问题有些问题,正面直接考虑比较复杂正面直接考虑比较复杂,而它的反面而它的反面往往比较简捷
35、，可以先求出它的反面，再从整体中排往往比较简捷，可以先求出它的反面，再从整体中排除。除。现在学习的是第39页，共43页v排列组合求解方法例排列组合求解方法例5 5：学院有学院有8个教研室个教研室,要抽要抽12人听报告人听报告,每个教研室要每个教研室要求至少求至少1人人,名额分配方案有多少种名额分配方案有多少种?此题可以转化为此题可以转化为:将将12个相同的白球分成个相同的白球分成8份，有多少种份，有多少种不同的分法问题。不同的分法问题。把这把这12个白球排成一排，在个白球排成一排，在11个空档中放上个空档中放上7个相同的个相同的黑球，每个空档最多放一个，即可将白球分成黑球，每个空档最多放一个，
36、即可将白球分成8份份,显然显然有有C(11,7)种不同的放法种不同的放法转化法转化法:对于某些较复杂的、或较抽象的排列组合问题，对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想，将其化归为简单的、具体的问题来可以利用转化思想，将其化归为简单的、具体的问题来求解求解现在学习的是第40页，共43页v排列组合求解方法例排列组合求解方法例6 6：袋中有袋中有5分硬币分硬币23个，个，1角硬币角硬币10个，如果从袋中取个，如果从袋中取出出2元钱，有多少种取法元钱，有多少种取法?(相同币值的不同硬币视为相同币值的不同硬币视为不同取法不同取法)把所有的硬币全部取出来，将得到把所有的硬币全部取出来，
37、将得到 0.0523+0.1010=2.15元，比元，比2元多元多0.15元。所以剩下元。所以剩下0.15元即剩下元即剩下3个个5分或分或1个个5分与分与1个个1角，共有角，共有C(23,3)+C(23,1)C(10,1)种取法种取法剩余法剩余法：在组合问题中，有多少取法，就有多少种剩法，在组合问题中，有多少取法，就有多少种剩法，它们是一一对应的。因此，当求取法困难时，可转化为求它们是一一对应的。因此，当求取法困难时，可转化为求剩法。剩法。现在学习的是第41页，共43页v重要的定理重要的定理定理定理3.8：对任意正整数对任意正整数n,r,rn 现在学习的是第42页，共43页v重要的定理重要的定理牛顿二项式定理：牛顿二项式定理：对任意正整数对任意正整数n，有，有证明：证明：当当(x+y)n的乘积展开时，的乘积展开时，其形式如其形式如 ，j=0,1,2,n。当从当从n个个(x+y)项中选择项中选择n-j个个x，其余其余j项选择项选择y时时，得到一个，得到一个 ，因此系数应为，因此系数应为。定理定理3.9：对任意正整数对任意正整数n，有，有现在学习的是第43页，共43页