离散数学第四部分组合数学.课件.ppt

1、1组合数学的研究内容组合数学的研究内容l 组合存在性组合存在性l 组合计数组合计数l 组合枚举组合枚举l 组合优化组合优化本书的内容本书的内容l 基本的组合计数公式基本的组合计数公式l 递推方程与生成函数递推方程与生成函数第四部分第四部分 组合数学组合数学2第十二章第十二章 基本的组合计数公式基本的组合计数公式主要内容主要内容l 加法法则与乘法法则加法法则与乘法法则l 排列与组合排列与组合l 二项式定理与组合恒等式二项式定理与组合恒等式l 多项式定理多项式定理312.1 加法法则与乘法法则加法法则与乘法法则l 加法法则加法法则l 乘法法则乘法法则l 分类处理与分步处理分类处理与分步处理4加法法

2、则加法法则加法法则加法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生方种产生方式，则式，则“事件事件A或或B”有有 m+n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1或或 A2或或 Ak”有有 p1+p2+pk 种产生的方式种产生的方式.5乘法法则乘法法则乘法法则乘法法则：事件：事件A 有

3、有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则“事件事件A与与B”有有 m n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1与与 A2与与 Ak”有有 p1 p2 pk 种产生的方式种产生的方式.6分类处理与分步处理分类处理与分步处理l 分类处理：对产生方式的集合进行划分，分别计数，然后

4、分类处理：对产生方式的集合进行划分，分别计数，然后使用加法法则使用加法法则l 分步处理：一种产生方式分解为若干独立步骤，对每步分分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则别进行计数，然后使用乘法法则l 分类与分步结合使用分类与分步结合使用 先分类，每类内部分步先分类，每类内部分步 先分步，每步又分类先分步，每步又分类7实例实例例例1 设设A，使个城市，从到有条道路，从，使个城市，从到有条道路，从到有条道路，从直接到有条道路，问从到到有条道路，从直接到有条道路，问从到有多少种不同的方式？有多少种不同的方式？解：解：8实例：关系计数实例：关系计数例例 设设A为为

5、 n 元集，问元集，问(1)A上的自反关系有多少个？上的自反关系有多少个？(2)A上的对称关系有多少个？上的对称关系有多少个？(3)A上的反对称关系有多少个？上的反对称关系有多少个？(4)A上的函数有多少个？其中双射函数有多少个？上的函数有多少个？其中双射函数有多少个？(2)考虑对称关系的矩阵考虑对称关系的矩阵.i 行行 j 列列(ij)的元素的元素 rij=rji.能够独立能够独立选择选择0或或1的位置有的位置有(n2 n)/2个个.加上主对角线的加上主对角线的n个位置，总计个位置，总计(n2+n)/2个位置，每个位置个位置，每个位置2种选择，根据乘法法则，构成矩种选择，根据乘法法则，构成矩

6、阵的方法数是阵的方法数是 2/)(22nn (1)在自反关系矩阵中，主对角线元素都是在自反关系矩阵中，主对角线元素都是1，其他位置的元，其他位置的元素可以是素可以是1，也可以是，也可以是0，有，有2种选择种选择.这种位置有这种位置有n2 n个，根个，根据乘法法则，自反关系的个数据乘法法则，自反关系的个数nn 229解答解答(3)非主对角线位置分成非主对角线位置分成(n2 n)/2组，每组包含元素组，每组包含元素rij和和rji.根根据反对称的性质，据反对称的性质，rij与与rji的取值有以下的取值有以下3种可能：种可能：rij=1,rji=0；rij=0,rji=1；rij=rji=0.所有这

7、些位置元素的选择方法数为所有这些位置元素的选择方法数为 .再考虑到主对角再考虑到主对角线元素的选取，由乘法法则总方法数为线元素的选取，由乘法法则总方法数为2/)(23nn 2/)(232nnn(4)设设A=x1,x2,xn，任何，任何A上的函数上的函数 f:AA具有下述形式：具有下述形式：f=,其中每个其中每个yi（i=1,2,n）有）有n种可能的选择，根据乘法法则，种可能的选择，根据乘法法则，有有nn个不同的函数个不同的函数.若若 f 是双射的，那么是双射的，那么y1确定以后，确定以后，y2只有只有n 1种可能的取值种可能的取值,yn只有只有1种取值种取值.构成双射函数的方法数构成双射函数的

8、方法数是是n(n 1)(n 2)1=n!.10A0 netid (7位)hostid (24位)B1 0 netid(14位)hostid(16位)C1 1 0 netid(21位)hostid(8位位)D1 1 1 0 (28位)E1 1 1 1 0 (27位)例：例：Ipv4Ipv4网址计数网址计数32位地址位地址 网络标识网络标识+主机标识主机标识(1)A类：最大网络；类：最大网络；B类：中等网络；类：中等网络；C：小网络；：小网络；D：多路广播；：多路广播；E：备用：备用(2)限制条件：限制条件：1111111在在A类中的类中的netid部分无效部分无效 hostid部分不允许全部分不

9、允许全0或全或全1 11 netid hostidA类：类：0+7位，位，24位位B类：类：10+14位，位，16位位C类：类：110+21位，位，8位位限制条件：限制条件：1111111在在A类中的类中的netid部分无效部分无效 hostid部分不允许全部分不允许全0或全或全1 A类：类：netid 27 1,hosted 224 2，NA127 167772142130706178 B类：类：netid 214,hosted 216 2，NB16384 655341073709056 C类：类：netid 221,hosted 28 2,NC2097152 254532676608 NN

10、A+NB+NC3737091842解答解答12选取问题：设选取问题：设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元素.根据是否有序根据是否有序,是否允许重复是否允许重复,将该问题分为四个子类型将该问题分为四个子类型不重复选取不重复选取重复选取重复选取有序选取有序选取集合的排列集合的排列多重集的排列多重集的排列无序选取无序选取集合的组合集合的组合多重集的组合多重集的组合12.2 排列与组合排列与组合13定义定义12.1 设设S为为n元集，元集，(1)从从 S 中有序选取的中有序选取的 r 个元素称为个元素称为 S 的一个的一个 r 排列排列，S 的的不同不同 r 排列总数记作

11、排列总数记作 P(n,r),r=n的排列是的排列是S的全排列的全排列.(2)从从 S 中无序选取的中无序选取的 r 个元素称为个元素称为 S 的一个的一个 r 组合，组合，S 的的不同不同 r 组合总数记作组合总数记作 C(n,r)集合的排列集合的排列 rnrnrnnrnP0)!(!),()1(rnrnrnrnrrnPrnC0)!(!),(),()2(定理定理1.1 设设n,r为自然数，规定为自然数，规定0!=1，则，则14下面考虑下面考虑 n r 的情况的情况.(1)排列的第一个元素有排列的第一个元素有 n 种选择的方式种选择的方式.排列的第二个元素排列的第二个元素有有n 1种选法种选法,第

12、第 r 个元素的方式数个元素的方式数 n r+1.根据乘法法根据乘法法则，总的选法数为则，总的选法数为 n(n 1)(n 2)(n r+1)=(2)分两步构成分两步构成 r 排列排列.首先无序地选出首先无序地选出r个元素，然后再构造个元素，然后再构造这这r个元素的全排列个元素的全排列.无序选择无序选择r个元素的方法数是个元素的方法数是C(n,r)；针对每种选法，能构造针对每种选法，能构造 r!个不同的全排列个不同的全排列.根据乘法法则，根据乘法法则，不同的不同的 r 排列数满足排列数满足 P(n,r)=C(n,r)r!组合数组合数C(n,r)也称为也称为二项式系数二项式系数，记作，记作证明证明

13、)!(!rnn rn15推论推论 设设n,r为正整数，则为正整数，则 (1)C(n,r)=(2)C(n,r)=C(n,n r)(3)C(n,r)=C(n 1,r 1)+C(n 1,r)推论推论)11 ,rC(nrn例例3 证明证明 C(n,r)=C(n,n r)证证 设设 S=1,2,n是是n元集合，对于元集合，对于S 的任意的任意 r 组合组合 A=a1,a2,ar，都存在一个，都存在一个S 的的 n r 组合组合S A与之对应与之对应.显然不同显然不同的的 r 组合对应了不同的组合对应了不同的 n r 组合，反之也对，因此组合，反之也对，因此 S 的的 r 组合组合数恰好与数恰好与 S 的

14、的 n r 组合数相等组合数相等.公式公式(3)称为称为 Pascal公式公式，也对应了，也对应了杨辉三角形杨辉三角形证明方法：公式代入并化简，组合证明证明方法：公式代入并化简，组合证明16杨辉三角杨辉三角111121133114641510 1011615 20515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=617多重集的排列与组合多重集的排列与组合定义定义12.2 多重集多重集 S=n1 a1,n2 a2,nk ak，n=n1+n2+nk 表表示示 S 中元素的总数中元素的总数.(1)从从S 中有序选取的中有序选取的r个元素称为多重集个元素称为

15、多重集 S 的一个的一个 r 排列排列.r=n 的排列称为的排列称为 S 的的全排列全排列(2)从从 S 中无序选取的中无序选取的 r 个元素称作多重集个元素称作多重集 S 的一个的一个r 组合组合 注意：注意：l 多重集中元素的重复度，多重集中元素的重复度，0 ni +,当当ni+，表示，表示ai重重复选取的次数没有限制复选取的次数没有限制l S的子集的子集 X=x1 a1,x2 a2,xk ak,其中其中0 xi +18多重集的排列计数多重集的排列计数定理定理12.2 设设S=n1 a1,n2 a2,nk ak为多重集，为多重集，(1)S 的全排列数是的全排列数是 (2)若若r ni，i=

16、1,2,k，那么，那么S 的的 r 排列数是排列数是 kr!.!21knnnn证明证明 (1)有有C(n,n1)种方法放种方法放a1，有，有C(n n1,n2)种方法放种方法放a2,最后有最后有C(n n1 n2 nk 1,nk)方法放方法放ak.根据乘法法则根据乘法法则,(2)r 个位置中的每个位置都有个位置中的每个位置都有 k 种选法，由乘法法则得种选法，由乘法法则得 kr!0!)!.(.)!(!)!()!(!2111212111121211kkkkk.nnnnnnnnnnnnnnnnnn),nn.nn).C(n,nn)C(nC(n,n 19多重集的组合多重集的组合定理定理12.3 多重集

17、多重集 S=n1 a1,n2 a2,nk ak，0ni +当当 r ni,S的的r 组合数为组合数为 N=C(k+r 1,r),),1()!1(!)!1(rrkCkrkrN 证明证明 一个一个 r 组合为组合为 x1 a1,x2 a2,xk ak，其中其中 x1+x2+xk=r,xi 为非负整数为非负整数.这个不定方程的这个不定方程的非负整数解对应于下述排列非负整数解对应于下述排列 11 0 11 0 11 0 0 11 x1个个 x2个个 x3个个 xk个个r 个个1，k 1个个 0 的全排列数为的全排列数为20公式小结公式小结 rnrnrnnrnP0)!(!),()1(rnrnrnrnrr

18、nPrnC0)!(!),(),()2()多重集多重集n1 a1,n2 a2,nk ak的全排列数是的全排列数是 !.!21knnnn(4)多重集多重集 S=n1 a1,n2 a2,nk ak，0ni +当当 r ni,S的的r 组合数为组合数为 N=C(k+r 1,r),21例例3 排列排列26个字母，使得个字母，使得 a 与与 b 之间恰有之间恰有7个字母，求方个字母，求方法数法数.解解 固定固定a 和和 b,中间选中间选7个字母，有个字母，有2 P(24,7)种方法，种方法，将它看作大字母与其余将它看作大字母与其余17个字母全排列有个字母全排列有18！种，共！种，共 N=2 P(24,7)

19、18!组合计数的应用组合计数的应用解解 相当于相当于2n 不同的球放到不同的球放到 n 个相同的盒子，每个盒子个相同的盒子，每个盒子2个，放法为个，放法为!2)!(22!0!2.2)!42()!22(22)!(2!2!1(2,2).2,2)(2,2)(2!1 nnnnnnnCnCnnNn 例例4 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？22解解 使用一一对应的思想求解这个问题使用一一对应的思想求解这个问题.a1,a2,ak：k个不相邻的数个不相邻的数,属于集合属于集合1,2,nb1,b2,bk：k个允许相邻的数个允许相邻的数,属于集合属于集合1,n(

20、k 1)对应规则是对应规则是 bi=ai(i 1).i=1,2,k 因此因此 N=C(n k+1,k)例例5 从从S=1,2,n中选择中选择 k 个不相邻的数，有多少种个不相邻的数，有多少种方法？方法？一一对应的技巧一一对应的技巧23主要内容主要内容l 二项式定理二项式定理l 组合恒等式组合恒等式l 非降路径问题非降路径问题12.3 二项式定理与组合恒等式二项式定理与组合恒等式24二项式定理二项式定理定理定理12.4 设设 n 是正整数，对一切是正整数，对一切 x 和和 y nkknknyxknyx0)(证明方法证明方法:数学归纳法、组合分析法数学归纳法、组合分析法.证证 当乘积被展开时其中的

21、项都是下述形式：当乘积被展开时其中的项都是下述形式：xi yn i,i=0,1,2,n.而构成形如而构成形如 xiyn i 的项，必须从的项，必须从n 个个和和(x+y)中选中选 i 个提供个提供 x，其它的，其它的 n i 个提供个提供 y.因此，因此，xiyn i 的系数是的系数是 ，定理得证，定理得证.in25二项式定理的应用二项式定理的应用解解 由二项式定理由二项式定理令令i=13 得到展开式中得到展开式中x12y13的系数，即的系数，即 2502525)3()2(25)3(2(iiiyxiyx1312131232!12!13!25)3(21325 例例6 求在求在(2x3y)25的展

22、开式中的展开式中x12y13的系数的系数.26组合恒等式：递推式组合恒等式：递推式 111.311.2.1knknknknknknknnkn证明方法：公式代入、组合分析证明方法：公式代入、组合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项之和或者差），然后合并27组合恒等式：基本求和式组合恒等式：基本求和式NnknNnknnkknnk 0)1(.5,2.400证明公式证明公式4.方法：二项式定理或者组合分析方法：二项式定理或者组合分析.设设S=1,2,n，下面计数，下面计数S 的所有子集的

23、所有子集.一种方法就是分类处理，一种方法就是分类处理，n元集合的元集合的 k子集个数是子集个数是 kn nkkn0根据加法法则，子集总数是根据加法法则，子集总数是另一种方法是分步处理，为构成另一种方法是分步处理，为构成 S 的子集的子集A，每个元素有，每个元素有 2 种选择，根据乘法法则，子集总数是种选择，根据乘法法则，子集总数是2n.28恒等式求和恒等式求和:变系数和变系数和202102)1(.72.6 nnknnknnknknknk证明方法：证明方法：二项式定理、级数求导二项式定理、级数求导 其他组合恒等式代入其他组合恒等式代入29证明公式证明公式6 nknknnkknnkknkknknk

24、xknknxknkxnxknxknx0111111012)1(1)1(令令求导求导30证明公式证明公式7212110111112022)1(22)1(211111)1(111)1(1111 nnnnnknknknknknknknnnnnnknknknnknknknknknknknknkknk变限变限常量外提常量外提消去变系数消去变系数31恒等式恒等式:变上项求和变上项求和Nknknklnl ,11.80证明证明 组合分析组合分析.令令S=a1,a2,an+1为为n+1元集合元集合.等式右边是等式右边是 S 的的 k+1子集数子集数.考虑另一种分类计数的方考虑另一种分类计数的方法法.将所有的将所

25、有的 k+1元子集分成如下元子集分成如下n+1类：类：第第1类：含类：含a1,剩下剩下 k个元素取自个元素取自a2,an+1 kn kn1 第第2类：不含类：不含a1,含含a2,剩下剩下k个元素取自个元素取自 a3,an+1 k0 不含不含a1,a2,an,含含an+1,剩下剩下k个元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证32恒等式恒等式:乘积转换式乘积转换式 krknknkrrn.9证明方法：组合分析证明方法：组合分析.n 元集中选取元集中选取 r 个元素，然后在这个元素，然后在这 r 个元素中再选个元素中再选 k个个元素元素.不同的不同的 r 元子集可能选出相同的元子

26、集可能选出相同的 k子集，例如子集，例如 a,b,c,d,e a,b,c,d b,c,d b,c,d,e b,c,d 重复度为：重复度为：应用：将变下限应用：将变下限 r 变成常数变成常数 k，求和时提到和号外面，求和时提到和号外面.krkn33恒等式恒等式:积之和积之和NnmmnmknkmnmrNrnmrnmkrnkmnkrk ,.11),min(,.1000 mnmknkmnnmknnkmnknk00关系关系证明思路：考虑集合证明思路：考虑集合A=a1,a2,am，B=b1,b2,bn.等等式右边计数了从这两个集合中选出式右边计数了从这两个集合中选出r个元素的方法个元素的方法.将这将这些选

27、法按照含有些选法按照含有A中元素的个数中元素的个数 k 进行分类，进行分类，k=0,1,r.然后使用加法法则然后使用加法法则.34组合恒等式解题方法小结组合恒等式解题方法小结证明方法：证明方法：l 已知恒等式带入已知恒等式带入l 二项式定理二项式定理l 幂级数的求导、积分幂级数的求导、积分l 归纳法归纳法l 组合分析组合分析求和方法：求和方法：l Pascal公式公式l 级数求和级数求和l 观察和的结果，然后使用归纳法证明观察和的结果，然后使用归纳法证明l 利用已知的公式利用已知的公式35非降路径的计数非降路径的计数(0,0)到到(m,n)的非降路径数：的非降路径数：C(m+n,m)(a,b)

28、到到(m,n)的非降路径数：的非降路径数：等于等于(0,0)到到(m a,n b)的非降路径数的非降路径数(a,b)经过经过(c,d)到到(m,n)的非降路径数：乘法法则的非降路径数：乘法法则(m,n)(0,0)36从从(0,0)到到(n,n)不接触对角线的非降路径数不接触对角线的非降路径数 NN1：从从(0,0)到到(n,n)下不接触对角下不接触对角 线非降路径数线非降路径数N2：从从(1,0)到到(n,n 1)下不接触对角下不接触对角 线非降路径数线非降路径数N0:从从(1,0)到到(n,n 1)的非降路径数的非降路径数N3:从从(1,0)到到(n,n 1)接触对角线的接触对角线的 非降路

29、径数非降路径数关系关系:N=2N1=2N2=2N0 N3(0,0)(1,0)(n,n-1)(n,n)限制条件的非降路径数限制条件的非降路径数37 1222221222 2 24030nnnnnnnNNNNNN3:从从(1,0)到到(n,n 1)接触对角线的接触对角线的 非降路径数非降路径数N4:从从(0,1)到到(n,n 1)无限制条件的无限制条件的 非降路径数非降路径数关系关系:N3=N4 一一对应一一对应(1,0)(0,1)(n,n-1)(0,0)(n,n)38例例7 A=1,2,m,B=1,2,n，N1:B上单调递增函数个上单调递增函数个 数是数是(1,1)到到(n+1,n)的非降路径数

30、的非降路径数N:B上单调函数个数上单调函数个数 N=2N1N2:A到到B单调递增函数个单调递增函数个 数是从数是从(1,1)到到(m+1,n)的非降路径数的非降路径数 N:A到到B单调函数数，单调函数数，N =2N2 严格单调递增函数、递减函数个数都是严格单调递增函数、递减函数个数都是C(n,m)nnN122 mnmN12(1,f(1)(2,f(2)(n,f(n)(n+1,n)(1,1)应用应用:单调函数计数单调函数计数39栈输出的计数栈输出的计数例例8 将将1,2,n 按照顺序输入栈，有多少个不同的输按照顺序输入栈，有多少个不同的输出序列？出序列？分析：将进栈、出栈分别记作分析：将进栈、出栈

31、分别记作 x,y,出栈序列是出栈序列是 n个个x，n个个y 的排列，的排列，排列中任何前缀的排列中任何前缀的 x 个数不少于个数不少于y 的个数，的个数，等于从等于从(0,0)到到(n,n)的不穿过对角线的非降路径数的不穿过对角线的非降路径数40输入：输入：1,2,3,4,5,输出输出：3,2,4,1,5进进,进进,进进,出出,出出,进进,出出,出出,进进,出出 x,x,x,y,y,x,y,y,x,y 12534栈输出的计数栈输出的计数41栈输出的计数栈输出的计数 nnnnnnnnnnnnnN211)!1()!1()!2(!)!2(122从从(0,0)到到(n,n)的穿的穿过对角线的非降路径过

32、对角线的非降路径从从(-1,1)到到(n,n)的的非降路径非降路径从从(0,0)到到(n,n)的非降的非降路径总数为路径总数为 C(2n,n)条，条，从从(-1,1)到到(n,n)的非降的非降路径数为路径数为 C(2n,n-1)条，条，(n,n)(0,0)(-1,0)(-1,1)42A=1,2,m,B=1,2,nf:AB函数计数小结函数计数小结43.定理定理12.6 设设n为正整数，为正整数，xi为实数，为实数，i=1,2,t.tntnntntxxxnnnnxxx.21212121求和是对满足方程求和是对满足方程n1+n2+nt=n的一切非负整数解求的一切非负整数解求 ttttnnnnnnnn

33、nnnnnnnnn.!.!.212111211在在n个因式中选个因式中选n1个因式贡献个因式贡献x1,从剩下从剩下n n1个因式选个因式选n2个因式贡献个因式贡献x2,从剩下的从剩下的n n1 n2 nt 1个因式中选个因式中选 nt个因式贡献个因式贡献 xt.tntnnx.xx2121证明证明 展开式中的项展开式中的项是如下构成的是如下构成的:12.4 多项式多项式定理定理44推论推论推论推论1 多项式展开式中不同的项数为方程多项式展开式中不同的项数为方程 的非负整数解的个数的非负整数解的个数 C(n+t 1,n)推论推论2 nttnnnn .21nnnnt .21例例9 求求(2x1 3x

34、2+5x3)6 中中 x13x2x32 的系数的系数.解解 由多项式定理得由多项式定理得3600025)3(8!2!1!3!65)3(2213623 45多项式系数多项式系数组合意义组合意义l 多项式系数多项式系数l 多重集多重集 S=n1 a1,n2 a2,nt at 的全排列数的全排列数l n个不同的球放到个不同的球放到 t 个不同的盒子使得第一个盒子含个不同的盒子使得第一个盒子含n1个个球，第二个盒子含球，第二个盒子含n2个球，个球，第，第 t 个盒子含个盒子含 nt 个球的方个球的方案数案数!.!.2121ttnnnnnnnn 符号符号46第十二章第十二章 习题课习题课主要内容主要内容

35、基本计数基本计数l 计数法则：加法法则、乘法法则计数法则：加法法则、乘法法则l 计数模型：选取问题、非降路径问题、方程的非负整数计数模型：选取问题、非降路径问题、方程的非负整数 解问题解问题l 处理方法：分类处理、分步处理、一一对应思想处理方法：分类处理、分步处理、一一对应思想 计数符号计数符号l 组合数或二项式系数组合数或二项式系数 C(m,n)：组合恒等式：组合恒等式l 排列数排列数 P(m,n)l 多项式系数多项式系数l 二项式定理与多项式定理二项式定理与多项式定理 tnnnn.2147基本要求基本要求l 能够熟练使用加法法则与乘法法则能够熟练使用加法法则与乘法法则l 熟悉和应用基本的组

36、合计数模型：熟悉和应用基本的组合计数模型：选取问题选取问题 不等方程的解不等方程的解 非降路径非降路径l 熟悉二项式定理与多项式定理熟悉二项式定理与多项式定理l 能证明组合恒等式并对二项式系数进行求和能证明组合恒等式并对二项式系数进行求和l 了解多项式系数及其相关公式了解多项式系数及其相关公式48练习练习1：基本的组合计数基本的组合计数1.求求1400的不同的正因子个数的不同的正因子个数.解解 1400的素因子分解式是的素因子分解式是 1400=23 52 71400的任何正因子都具有下述形式：的任何正因子都具有下述形式：2i 5j 7k，其中，其中 0 i 3,0 j 2,0 k 1.根据乘

37、法法则，根据乘法法则，1400的正因子数是的正因子数是 i,j,k 的选法数的选法数 N=(1+3)(1+2)(1+1)=24.49练习练习2：基本的组合计数：基本的组合计数2把把10个不同的球放到个不同的球放到6个不同的盒子里，允许空盒，且前个不同的盒子里，允许空盒，且前2个盒子球的总数至多是个盒子球的总数至多是4，问有多少种方法？，问有多少种方法？解解 根据前两个盒子含球数根据前两个盒子含球数k对放法分类，其中对放法分类，其中 k=0,1,2,3,4.对于给定的对于给定的 k，再分步处理计算放球的方法数：，再分步处理计算放球的方法数：从从10个球中选放入前两个盒子的个球中选放入前两个盒子的

38、k个球，有个球，有C(10,k)选法；选法；把选好的把选好的k个球分到个球分到2个盒子里，每个球可以有个盒子里，每个球可以有2种选择，种选择，有有2k 种分法；种分法；剩下的剩下的 n k个球分到其他个球分到其他4个盒子里有个盒子里有4n k 种分法种分法.根据乘法法则，使得前两个盒子含根据乘法法则，使得前两个盒子含k个球的放法数是个球的放法数是 C(10,k)2k 4n k 最后使用加法法则对最后使用加法法则对k求和，就得到所求的方法数是求和，就得到所求的方法数是4757913642),10(4010 kkkkC503由由m个个A和和n个个B构成序列，其中构成序列，其中m,n为正整数，为正整

39、数，m n.如如果要求每个果要求每个A后面至少紧跟着后面至少紧跟着1个个B,问有多少个不同的序列？问有多少个不同的序列？3.方法一方法一.先放先放 n 个个B，只有，只有1种方法种方法.然后，在每个然后，在每个B之间的之间的n 个位置中选择个位置中选择 m 个位置放个位置放A,有有C(n,m)种方法种方法.练习练习3：基本的组合计数：基本的组合计数方法二方法二.先放先放 m 个个AB，只有，只有1 种方法种方法.把每个把每个AB 看作格板，看作格板，m 个格板构成个格板构成 m+1个空格，在空格中放入个空格，在空格中放入 n m 个个B.这相当这相当于方程于方程 x1+x2+xm+1=n m

40、的非负整数解的个数，因此的非负整数解的个数，因此 N=C(n m+m+1 1,n m)=C(n,n m)=C(n,m)51练习练习4方法一方法一.令令|A|=k，按照，按照 k=0,1,n 将有序对将有序对分类分类.给定给定 k，选，选 A方法数是方法数是C(n,k)；选选 B 中剩下的中剩下的 n k 个元素个元素,每个元素有每个元素有2 种选法，有种选法，有2n k 个个不同的不同的 B 集合集合.由乘法法则，这样的由乘法法则，这样的有有C(n,k)2n k 个，个，再使用加法法则和二项式定理，从而得到再使用加法法则和二项式定理，从而得到4.设设 S 是是 n 元集，元集，N 表示满足表示

41、满足 A B S 的有序对的有序对 的个的个数，用二项式定理证明数，用二项式定理证明N=3nnnnkknknkknknCknCN3)21(21),(2),(00 方法二方法二.S中的每个元素可以有中的每个元素可以有3种选法：同时加入种选法：同时加入A和和B，不，不加入加入 A 但加入但加入B，A 和和 B 都不加入；都不加入；因此，因此，n 个元素总共个元素总共3n 种选法种选法.52练习练习5)2(2)1(10 nknknnk5.证明证明 nknnnkknnknk0112,2方法一方法一.利用已知等式利用已知等式将上述两式相加得将上述两式相加得)2(2)1(10 nknknnk53练习练习5方法二方法二 利用积分利用积分nknkknkxnkkxxxknxxkndxxfxknkxf)1()()1()(01000 )2(222)1()1()1()1()(1101 nnfknkxxnxxfnnnnknn54练习练习6 mkkkmn06.求和求和 mnmnmnmnmnmnmnmnmnmnmnmnmnmnkkmnmk11.332212.221101.11000