10-1 组合分析

《10-1 组合分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章组合分析初步10.1加法法则和乘法法则10.2基本排列组合的计数方法10.3递推方程的求解与应用加法法则使用条件：事件A与B产生方式不重叠适用问题：分类选取.方式分别计数，再相加.事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有m+n种产生方式.mnAB

2、A∪B

3、=

4、A

5、+

6、B

7、当A和B是不同的两个事件集合时，加法法则也可以表示为加法法则的推广事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1或A2或…Ak”有n1+n2+…+nk种产生的方

8、式.使用条件：各事件Ai的产生方式不重叠当A1、A2、…Ak”是不同的多个事件集合时，加法法则也可以表示为

9、A1∪A2∪…∪Ak

10、=

11、A1

12、+

13、A2

14、+…+

15、Ak

16、n1A1n2A2nkAk……乘法法则使用条件：事件A与B产生方式相互独立适用问题：分步选取.方式是连续的步骤，各步相互独立，分别计数，然后相乘.当A和B是不同的两个事件集合时，乘法法则也可以表示为事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.

17、A∩B

18、=

19、A

20、·

21、B

22、乘法法的推广事件A1有n1种产生方式，事件A2有

23、n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1与A2与…Ak”有n1·n2·…·nk种产生的方式.使用条件：各事件Ai的产生方式相互独立当A1、A2、…Ak”是不同的多个事件集合时，乘法法则也可以表示为

24、A1∩A2∩…∩Ak

25、=

26、A1

27、·

28、A2

29、·…·

30、Ak

31、应用实例例1设A,B,C是3个城市，从A到B有3条道路，从B到C有2条道路，从A直接到C有4条道路，问：(1)从A到C有多少种不同的方式？AC共有32+4=10种方式(2)从A到C，最后又回到A有多少种不同的方式？其中经过B的有多少种

32、方式？从ACA共有1010=100种方式其中不经过B的共有44=16种方式则经过B的共有100-16=84各方式。ABC应用实例例2求1400的不同的正因子个数。解：1400的素因子分解是1400=14×100=23×52×7因此，1400的任何正因子都具有下述形式：2i×5j×7k其中0i3,0j2,0k1根据乘法法则，1400的正因子数是i,j,k的选法数：N=(3+1)(2+1)(1+1)=2410.2基本排列组合的计数方法例1：从{1,2,…,9}中选取数字构成4位数，若要求每个

33、数字不相同，问有多少种方法？9×8×7×6=P94不允许重复的有序选取----集合的排列例2：从{1,2,…,9}中选取数字构成4位数，问有多少种方法？9×9×9×9=94允许重复的有序选取----多重集的排列排列组合的分类例3：从5种不同的球中每次取3个不同的球，问有多少种方法？C53不允许重复的无序选取—集合的组合例4：从5种不同的球(每种球至少有3个)，每次取3个球，问有多少种方法？C73允许重复的无序选取—多重集的组合排列组合的分类选取问题：设n元集合S，从S中选取r个元素.根据是否有序，是否允许重

34、复可将该问题分为四个子类型不重复重复有序集合排列P(n,r)多重集排列无序集合组合C(n,r)多重集组合集合的排列从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作S的r-环排列数=ABC,BCA,CAB在环上只能算一种排列。ACB实例5解：固定a和b中间选7个字母，有种方法将它看作大字母与其余17的全排列,有18！种，排列26个字母，使得a与b之间恰有7个字母，求方法数.ab1234567891011121314151617181234567实例610个男孩，5个女孩站成一

35、排，若没女孩相邻，有多少种方法？解:共有10个男孩，所以不同的排列有共有11个位置由5个女孩选择排列，共有所以总共有(2)如果站成一个圆圈,有多少种方法？共有10个男孩，不同的排列有共有10个位置由5个女孩选择，共有所以总共有12345678910实例79本不同的书，其中4本红皮，5本白皮.(1)9本书的排列方式数有多少？(2)若白皮书必须放在一起，那么有多少方法？(3)若白皮书必须放在一起，红皮书也必须放在一起，那么有多少方法？(4)若白皮书和红皮书必须相间，有多少方法？解：9!5！5！(3)5!4!2!

36、(4)5！4！集合的组合从n元集S中无序、不重复选取的r个元素称为S的一个r组合，S的所有r组合的数目记作例3：从5种不同的球中每次取3个不同的球，问有多少种方法？基本计数公式的应用解：把1~300分成A、B、C三个集合，令A={x

37、x≡1(mod3)}={1,4,…,298}，

38、A

39、=100B={x

40、x≡2(mod3)}={2,5,…,299}，

41、B

42、=100C={x

43、x≡0(mod3)}={3,6,…,300