*组合分析*第8章组合分析初步8.1加法法则与乘法法则8.2基本排列组合的计数方法8.3递推方程的求解与应用*8.1加法法则和乘法法则加法法则与乘法法则应用实例*加法法则使用条件：事件A与B产生方式不重叠适用问题：分类选取.各方式分别计数，再相加.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1或A2或…Ak”的产生方式有n1+n2+…+nk种.事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有m+n种产生方式.*乘法法则使用条件：事件A与B产生方式相互独立适用问题：分步选取.方式是连续的步骤，各步相互独立，分别计数，然后相乘.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1与A2与…Ak”的产生方式有n1n2…nk种.事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.*应用实例例1由数字1、2、3、4、5构成3位数.(1)如果各位数字都不相同，那么有多少种方法?(2)如果必须是偶数，则有多少种方法?(3)其中可以被5整除的有多少个?(4)其中比300大的有多少个?解(1)5×4×3=60.(2)个位为2,4，十位、百位各5种：2×5×5=50.(3)个位为5，十位和百位同(2)：1×5×5=25.(4)百位取3,4或5，十位和个位各5种:3×5×5=75.*应用实例解：1400=23527正因子为：2i5j7k，0?i?3,0?j?2,0?k?1N=4×3×2=24例2求1400的不同的正因子个数*8.2基本排列组合的计数方法排列组合的分类集合的排列集合的组合多重集的排列多重集的组合*排列组合的分类选取问题：设n元集合S，从S中选取r个元素.根据是否有序，是否允许重复可将该问题分为四个子类型不重复重复有序集合排列P(n,r)多重集排列无序集合组合C(n,r)多重集组合*集合的排列从n元集S中有序、不重复选取的r个元素称为S的一个r-排列，S的所有r排列的数目记作S的r-环排列数=*集合的组合从n元集S中无序、不重复选取的r个元素称为S的一个r组合，S的所有r组合的数目记作应用方法：公式代入组合证明（一一对应）(例如定理8.7推论2)*组合公式的应用（I）解令A={1,4,…,298}，B={2,5,…,299}C={3,6,…,300}将方法分类：分别取自A,B,C:各A,B,C各取1个：例1从1—300中任取3个数使得其和能被3整除有多少种方法？*解1000!=1000?999?998?…?2?1将上面的每个因子分解，若分解式中共有i个5,j个2，那么min{i,j}就是0的个数.1,…,1000中有500个是2的倍数，j500;200个是5的倍数，40个是25的倍数（多加40个5），8个是125的倍数（再多加8个5），1个是625的倍数（再多加1个5）i=200+40+8+1=249.min{i,j}=249.例2求1000！的末尾有多少个0？*多重集S={n1?a1,n2?a2,…,nk?ak}，0ni?+∞(1)全排列:r=n,n1+n2+…+nk=n（占位模型）(定理8.6)证明：分步选取，先放a1,有种方法；再放a2,有种方法，...,放ak有