《离散数学第十二章 基本的组合计数公式.ppt》由会员分享，可在线阅读，更多相关《离散数学第十二章 基本的组合计数公式.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合数学的研究内容组合数学的研究内容l组合存在性组合存在性l组合计数组合计数l组合枚举组合枚举l组合优化组合优化本书的内容本书的内容l基本的组合计数公式基本的组合计数公式l递推方程与生成函数递推方程与生成函数第四部分第四部分 组合数学组合数学1第十二章第十二章 基本的组合计数公式基本的组合计数公式主要内容主要内容l加法法则与乘法法则加法法则与乘法法则l排列与组合排列与组合l二项式定理与组合恒等式二项式定理与组合恒等式l多项式定理多项式定理212.1 加法法则与乘法法则加法法则与乘法法则l加法法则加法法则l乘法法则乘法法则l分类处理与分步处理分类处理与分步处理3加法法则加法法则加法法则加法法则：
2、事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生方种产生方式，则式，则“事件事件A或或B”有有 m+n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方式，种产生方式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1或或 A2或或 Ak”有有 p1+p2+pk 种产生的方式种产生的方式.4乘法法则乘法法则乘法法则乘法法则：事件：事件A 有有 m 种产生方式，事件种产
3、生方式，事件 B 有有n 种产生种产生方式，则方式，则“事件事件A与与B”有有 m n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1与与 A2与与 Ak”有有 p1 p2 pk 种产生的方式种产生的方式.5分类处理与分步处理分类处理与分步处理l分类处理：对产生方式的集合进行划分，分别计数，然后分类处理：对产生方式的集合进行
4、划分，分别计数，然后使用加法法则使用加法法则l分步处理：一种产生方式分解为若干独立步骤，对每步分分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则别进行计数，然后使用乘法法则l分类与分步结合使用分类与分步结合使用 先分类，每类内部分步先分类，每类内部分步 先分步，每步又分类先分步，每步又分类6实例实例例例1 设设A，使个城市，从到有条道路，从，使个城市，从到有条道路，从到有条道路，从直接到有条道路，问从到到有条道路，从直接到有条道路，问从到有多少种不同的方式？有多少种不同的方式？解：解：7实例：关系计数实例：关系计数例例 设设A为为 n 元集，问元集，问(1)A上的
5、自反关系有多少个？上的自反关系有多少个？(2)A上的对称关系有多少个？上的对称关系有多少个？(3)A上的反对称关系有多少个？上的反对称关系有多少个？(4)A上的函数有多少个？其中双射函数有多少个？上的函数有多少个？其中双射函数有多少个？.(2)考虑对称关系的矩阵考虑对称关系的矩阵.i 行行 j 列列(ij)的元素的元素 rij=rji.能够独能够独立立选择选择0或或1的位置有的位置有(n2 n)/2个个.加上主对角线的加上主对角线的n个位置，总计个位置，总计(n2+n)/2个位置，每个位置个位置，每个位置2种选择，根据乘法法则，构成矩种选择，根据乘法法则，构成矩阵的方法数是阵的方法数是(1)在
6、自反关系矩阵中，主对角线元素都是在自反关系矩阵中，主对角线元素都是1，其他位置的元，其他位置的元素可以是素可以是1，也可以是，也可以是0，有，有2种选择种选择.这种位置有这种位置有n2 n个，根个，根据乘法法则，自反关系的个数据乘法法则，自反关系的个数8解答解答(3)非主对角线位置分成非主对角线位置分成(n2 n)/2组，每组包含元素组，每组包含元素rij和和rji.根根据反对称的性质，据反对称的性质，rij与与rji的取值有以下的取值有以下3种可能：种可能：rij=1,rji=0；rij=0,rji=1；rij=rji=0.所有这些位置元素的选择方法数为所有这些位置元素的选择方法数为 .再考
7、虑到主对角再考虑到主对角线元素的选取，由乘法法则总方法数为线元素的选取，由乘法法则总方法数为(4)设设A=x1,x2,xn，任何，任何A上的函数上的函数 f:AA具有下述形式：具有下述形式：f=,其中每个其中每个yi（i=1,2,n）有）有n种可能的选择，根据乘法法则，种可能的选择，根据乘法法则，有有nn个不同的函数个不同的函数.若若 f 是双射的，那么是双射的，那么y1确定以后，确定以后，y2只有只有n 1种可能的取值种可能的取值,yn只有只有1种取值种取值.构成双射函数的方法构成双射函数的方法数数是是n(n 1)(n 2)1=n!.9A0 netid (7位)hostid (24位)B1
8、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部分不允许全部分不允许全0或全或全1 10 netid hostidA类：类：0+7位，位，24位位B类：类：10+14
9、位，位，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 NNA+NB+NC3737091842解答解答11选取问题：设选取问题：设 n 元集合元集合 S，从，从
10、S 中选取中选取 r 个元素个元素.根据是否有序根据是否有序,是否允许重复是否允许重复,将该问题分为四个子类型将该问题分为四个子类型不重复不重复选选取取重复重复选选取取有序有序选选取取集合的排列集合的排列多重集的排列多重集的排列无序无序选选取取集合的集合的组组合合多重集的多重集的组组合合12.2 排列与组合排列与组合12定义定义12.1 设设S为为n元集，元集，(1)从从 S 中有序选取的中有序选取的 r 个元素称为个元素称为 S 的一个的一个 r 排列排列，S 的的不同不同 r 排列总数记作排列总数记作 P(n,r),r=n的排列是的排列是S的全排列的全排列.(2)从从 S 中无序选取的中无
11、序选取的 r 个元素称为个元素称为 S 的一个的一个 r 组合，组合，S 的的不同不同 r 组合总数记作组合总数记作 C(n,r)集合的排列集合的排列定理定理1.1 设设n,r为自然数，规定为自然数，规定0!=1，则，则13下面考虑下面考虑 n r 的情况的情况.(1)排列的第一个元素有排列的第一个元素有 n 种选择的方式种选择的方式.排列的第二个元排列的第二个元素有素有n 1种选法种选法,第第 r 个元素的方式数个元素的方式数 n r+1.根据乘根据乘法法则，总的选法数为法法则，总的选法数为 n(n 1)(n 2)(n r+1)=(2)分两步构成分两步构成 r 排列排列.首先无序地选出首先无
12、序地选出r个元素，然后再构个元素，然后再构造这造这r个元素的全排列个元素的全排列.无序选择无序选择r个元素的方法数是个元素的方法数是C(n,r)；针对每种选法，能构造；针对每种选法，能构造 r!个不同的全排列个不同的全排列.根据乘法法根据乘法法则，不同的则，不同的 r 排列数满足排列数满足 P(n,r)=C(n,r)r!组合数组合数C(n,r)也称为也称为二项式系数二项式系数，记作，记作证明证明14推论推论 设设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)推论推论例例3 证明证明 C(n,r)
13、=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 的的 n r 组合数相等组合数相等.公式公式(3)称为称为 Pascal公式公式，也对应了，也对应了杨辉三角形杨辉三角形证明方法：公式代入并化简，组合证明证明方法：公式代入并化简，组合证明15杨辉三角杨辉三角111121133114641510
14、1011615 20515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=616多重集的排列与组合多重集的排列与组合定义定义12.2 多重集多重集 S=n1 a1,n2 a2,nk ak，n=n1+n2+nk 表表示示 S 中元素的总数中元素的总数.(1)从从S 中有序选取的中有序选取的r个元素称为多重集个元素称为多重集 S 的一个的一个 r 排列排列.r=n 的排列称为的排列称为 S 的的全排列全排列(2)从从 S 中无序选取的中无序选取的 r 个元素称作多重集个元素称作多重集 S 的一个的一个r 组合组合 注意：注意：l多重集中元素的重复度，多重集中
15、元素的重复度，0 ni +,当当ni+，表示，表示ai重重复选取的次数没有限制复选取的次数没有限制lS的子集的子集 X=x1 a1,x2 a2,xk ak,其中其中0 xi +17多重集的排列计数多重集的排列计数定理定理12.2 设设S=n1 a1,n2 a2,nk ak为多重集，为多重集，(1)S 的全排列数是的全排列数是 (2)若若r ni，i=1,2,k，那么，那么S 的的 r 排列数是排列数是 kr 证明证明 (1)有有C(n,n1)种方法放种方法放a1，有，有C(n n1,n2)种方法放种方法放a2,最后有最后有C(n n1 n2 nk 1,nk)方法放方法放ak.根据乘法法则根据乘
16、法法则,(2)r 个位置中的每个位置都有个位置中的每个位置都有 k 种选法，由乘法法则得种选法，由乘法法则得 kr 18多重集的组合多重集的组合定理定理12.3 多重集多重集 S=n1 a1,n2 a2,nk ak，0ni +当当 r ni,S的的r 组合数为组合数为 N=C(k+r 1,r),证明证明 一个一个 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
17、 1个个 0 的全排列数为的全排列数为19公式小结公式小结()多重集多重集n1 a1,n2 a2,nk ak的全排列数是的全排列数是 (4)多重集多重集 S=n1 a1,n2 a2,nk ak，0ni +当当 r ni,S的的r 组合数为组合数为 N=C(k+r 1,r),20例例3 排列排列26个字母，使得个字母，使得 a 与与 b 之间恰有之间恰有7个字母，求方个字母，求方法数法数.解解 固定固定a 和和 b,中间选中间选7个字母，有个字母，有2 P(24,7)种方法，种方法，将它看作大字母与其余将它看作大字母与其余17个字母全排列有个字母全排列有18！种，共！种，共 N=2 P(24,7
18、)18!组合计数的应用组合计数的应用解解 相当于相当于2n 不同的球放到不同的球放到 n 个相同的盒子，每个盒子个相同的盒子，每个盒子2个，放法为个，放法为例例4 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？21解解 使用一一对应的思想求解这个问题使用一一对应的思想求解这个问题.a1,a2,ak：k个不相邻的数个不相邻的数,属于集合属于集合1,2,nb1,b2,bk：k个允许相邻的数个允许相邻的数,属于集合属于集合1,n(k 1)对应规则是对应规则是 bi=ai(i 1).i=1,2,k 因此因此 N=C(n k+1,k)例例5 从从S=1,2,n中选择
19、中选择 k 个不相邻的数，有多少种个不相邻的数，有多少种方法？方法？一一对应的技巧一一对应的技巧22主要内容主要内容l二项式定理二项式定理l组合恒等式组合恒等式l非降路径问题非降路径问题12.3 二项式定理与组合恒等式二项式定理与组合恒等式23二项式定理二项式定理定理定理12.4 设设 n 是正整数，对一切是正整数，对一切 x 和和 y 证明方法证明方法:数学归纳法、组合分析法数学归纳法、组合分析法.证证 当乘积被展开时其中的项都是下述形式：当乘积被展开时其中的项都是下述形式：xi yn i,i=0,1,2,n.而构成形如而构成形如 xiyn i 的项，必须从的项，必须从n 个个和和(x+y)
20、中选中选 i 个提供个提供 x，其它的，其它的 n i 个提供个提供 y.因此，因此，xiyn i 的系数是的系数是 ，定理得证，定理得证.24二项式定理的应用二项式定理的应用解解 由二项式定理由二项式定理令令i=13 得到展开式中得到展开式中x12y13的系数，即的系数，即 例例6 求在求在(2x3y)25的展开式中的展开式中x12y13的系数的系数.25组合恒等式：递推式组合恒等式：递推式证明方法：公式代入、组合分析证明方法：公式代入、组合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项
21、之和或者差），然后合并26组合恒等式：基本求和式组合恒等式：基本求和式证证明公式明公式4.方法：二方法：二项项式定理或者式定理或者组组合分析合分析.设设S=1,2,n，下面，下面计计数数S 的所有子集的所有子集.一种方法就是分一种方法就是分类处类处理，理，n元集合的元集合的 k子集个数是子集个数是根据加法法则，子集总数是根据加法法则，子集总数是另一种方法是分步处理，为构成另一种方法是分步处理，为构成 S 的子集的子集A，每个元素有，每个元素有 2 种选择，根据乘法法则，子集总数是种选择，根据乘法法则，子集总数是2n.27恒等式求和恒等式求和:变系数和变系数和证明方法：证明方法：二项式定理、级数
22、求导二项式定理、级数求导 其他组合恒等式代入其他组合恒等式代入28证明公式证明公式629证明公式证明公式730恒等式恒等式:变上项求和变上项求和证证明明 组组合分析合分析.令令S=a1,a2,an+1为为n+1元集合元集合.等式右等式右边边是是 S 的的 k+1子集数子集数.考考虑虑另一种分另一种分类计类计数的方数的方法法.将所有的将所有的 k+1元子集分成如下元子集分成如下n+1类类：第第1类类：含：含a1,剩下剩下 k个元素取自个元素取自a2,an+1 第第2类类：不含：不含a1,含含a2,剩下剩下k个元素取自个元素取自 a3,an+1 不含不含a1,a2,an,含含an+1,剩下剩下k个
23、元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证31恒等式恒等式:乘积转换式乘积转换式证明方法：组合分析证明方法：组合分析.n 元集中选取元集中选取 r 个元素，然后在这个元素，然后在这 r 个元素中再选个元素中再选 k个个元素元素.不同的不同的 r 元子集可能选出相同的元子集可能选出相同的 k子集，例如子集，例如 a,b,c,d,e a,b,c,d b,c,d b,c,d,e b,c,d 重复度为：重复度为：应用：将变下限应用：将变下限 r 变成常数变成常数 k，求和时提到和号外面，求和时提到和号外面.32恒等式恒等式:积之和积之和关系关系证证明思路：考明思路：考虑虑集合集合A
24、=a1,a2,am，B=b1,b2,bn.等等式右式右边计边计数了从数了从这这两个集合中两个集合中选选出出r个元素的方法个元素的方法.将将这这些些选选法按照含有法按照含有A中元素的个数中元素的个数 k 进进行分行分类类，k=0,1,r.然后使用加法法然后使用加法法则则.33组合恒等式解题方法小结组合恒等式解题方法小结证明方法：证明方法：l已知恒等式带入已知恒等式带入l二项式定理二项式定理l幂级数的求导、积分幂级数的求导、积分l归纳法归纳法l组合分析组合分析求和方法：求和方法：lPascal公式公式l级数求和级数求和l观察和的结果，然后使用归纳法证明观察和的结果，然后使用归纳法证明l利用已知的公
25、式利用已知的公式34非降路径的计数非降路径的计数(0,0)到到(m,n)的非降路径数：的非降路径数：C(m+n,m)(a,b)到到(m,n)的非降路径数：的非降路径数：等于等于(0,0)到到(m a,n b)的非降路径数的非降路径数(a,b)经过经过(c,d)到到(m,n)的非降路径数：乘法法则的非降路径数：乘法法则(m,n)(0,0)35从从(0,0)到到(n,n)不接触对角线的非降路径数不接触对角线的非降路径数 NN1：从从(0,0)到到(n,n)下不接触对角下不接触对角 线非降路径数线非降路径数N2：从从(1,0)到到(n,n 1)下不接触对角下不接触对角 线非降路径数线非降路径数N0:
26、从从(1,0)到到(n,n 1)的非降路径数的非降路径数N3:从从(1,0)到到(n,n 1)接触对角线的接触对角线的 非降路径数非降路径数关系关系:N=2N1=2N2=2N0 N3(0,0)(1,0)(n,n-1)(n,n)限制条件的非降路径数限制条件的非降路径数36N3:从从(1,0)到到(n,n 1)接触对角线的接触对角线的 非降路径数非降路径数N4:从从(0,1)到到(n,n 1)无限制条件的无限制条件的 非降路径数非降路径数关系关系:N3=N4 一一对应一一对应(1,0)(0,1)(n,n-1)(0,0)(n,n)37例例7 A=1,2,m,B=1,2,n，N1:B上单调递增函数个上
27、单调递增函数个 数是数是(1,1)到到(n+1,n)的非降路径数的非降路径数N:B上单调函数个数上单调函数个数 N=2N1N2:A到到B单调递增函数个单调递增函数个 数是从数是从(1,1)到到(m+1,n)的非降路径数的非降路径数 N:A到到B单调函数数，单调函数数，N =2N2 严格单调递增函数、递减函数个数都是严格单调递增函数、递减函数个数都是C(n,m)(1,f(1)(2,f(2)(n,f(n)(n+1,n)(1,1)应用应用:单调函数计数单调函数计数38栈输出的计数栈输出的计数例例8 将将1,2,n 按照顺序输入栈，有多少个不同的输按照顺序输入栈，有多少个不同的输出序列？出序列？分析：
28、将进栈、出栈分别记作分析：将进栈、出栈分别记作 x,y,出栈序列是出栈序列是 n个个x，n个个y 的排列，的排列，排列中任何前缀的排列中任何前缀的 x 个数不少于个数不少于y 的个数，的个数，等于从等于从(0,0)到到(n,n)的不穿过对角线的非降路径数的不穿过对角线的非降路径数39输入：输入：1,2,3,4,5,输出输出：3,2,4,1,5进进,进进,进进,出出,出出,进进,出出,出出,进进,出出 x,x,x,y,y,x,y,y,x,y 12534栈输出的计数栈输出的计数40栈输出的计数栈输出的计数从从(0,0)到到(n,n)的穿的穿过对角线的非降路径过对角线的非降路径从从(-1,1)到到(
29、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)41A=1,2,m,B=1,2,nf:AB函数计数小结函数计数小结42.定理定理12.6 设设n为正整数，为正整数，xi为实数，为实数，i=1,2,t.求和是对满足方程求和是对满足方程n1+n2+nt=n的一切非负整数解求的一切非负整数解求在在n个因式中个因式中选选n1个因式个因式贡贡献献x1,从剩下从剩下n n1个因式个因式选选n2个因式个因式贡贡献献x
30、2,从剩下的从剩下的n n1 n2 nt 1个因式中个因式中选选 nt个因式个因式贡贡献献 xt.证明证明 展开式中的项展开式中的项是如下构成的是如下构成的:12.4 多项式多项式定理定理43推论推论推论推论1 多项式展开式中不同的项数为方程多项式展开式中不同的项数为方程 的非负整数解的个数的非负整数解的个数 C(n+t 1,n)推论推论2 例例9 求求(2x1 3x2+5x3)6 中中 x13x2x32 的系数的系数.解解 由多项式定理得由多项式定理得44多项式系数多项式系数组合意义组合意义l多项式系数多项式系数l多重集多重集 S=n1 a1,n2 a2,nt at 的全排列数的全排列数l
31、n个不同的球放到个不同的球放到 t 个不同的盒子使得第一个盒子含个不同的盒子使得第一个盒子含n1个个球，第二个盒子含球，第二个盒子含n2个球，个球，第，第 t 个盒子含个盒子含 nt 个球的方个球的方案数案数符号符号45第十二章第十二章 习题课习题课主要内容主要内容基本计数基本计数l 计数法则：加法法则、乘法法则计数法则：加法法则、乘法法则l 计数模型：选取问题、非降路径问题、方程的非负整数计数模型：选取问题、非降路径问题、方程的非负整数 解问题解问题l 处理方法：分类处理、分步处理、一一对应思想处理方法：分类处理、分步处理、一一对应思想 计数符号计数符号l 组合数或二项式系数组合数或二项式系
32、数 C(m,n)：组合恒等式：组合恒等式l 排列数排列数 P(m,n)l 多项式系数多项式系数l 二项式定理与多项式定理二项式定理与多项式定理46基本要求基本要求l能够熟练使用加法法则与乘法法则能够熟练使用加法法则与乘法法则l熟悉和应用基本的组合计数模型：熟悉和应用基本的组合计数模型：选取问题选取问题 不等方程的解不等方程的解 非降路径非降路径l熟悉二项式定理与多项式定理熟悉二项式定理与多项式定理l能证明组合恒等式并对二项式系数进行求和能证明组合恒等式并对二项式系数进行求和l了解多项式系数及其相关公式了解多项式系数及其相关公式47练习练习1：基本的组合计数基本的组合计数1.求求1400的不同的
33、正因子个数的不同的正因子个数.解解 1400的素因子分解式是的素因子分解式是 1400=23 52 71400的任何正因子都具有下述形式：的任何正因子都具有下述形式：2i 5j 7k，其中，其中 0 i 3,0 j 2,0 k 1.根据乘法法则，根据乘法法则，1400的正因子数是的正因子数是 i,j,k 的选法数的选法数 N=(1+3)(1+2)(1+1)=24.48练习练习2：基本的组合计数：基本的组合计数2把把10个不同的球放到个不同的球放到6个不同的盒子里，允许空盒，且前个不同的盒子里，允许空盒，且前2个盒子球的总数至多是个盒子球的总数至多是4，问有多少种方法？，问有多少种方法？解解 根
34、据前两个盒子含球数根据前两个盒子含球数k对放法分类，其中对放法分类，其中 k=0,1,2,3,4.对于给定的对于给定的 k，再分步处理计算放球的方法数：，再分步处理计算放球的方法数：从从10个球中选放入前两个盒子的个球中选放入前两个盒子的k个球，有个球，有C(10,k)选法；选法；把选好的把选好的k个球分到个球分到2个盒子里，每个球可以有个盒子里，每个球可以有2种选择，种选择，有有2k 种分法；种分法；剩下的剩下的 n k个球分到其他个球分到其他4个盒子里有个盒子里有4n k 种分法种分法.根据乘法法则，使得前两个盒子含根据乘法法则，使得前两个盒子含k个球的放法数是个球的放法数是 C(10,k
35、)2k 4n k 最后使用加法法则对最后使用加法法则对k求和，就得到所求的方法数是求和，就得到所求的方法数是493由由m个个A和和n个个B构成序列，其中构成序列，其中m,n为正整数，为正整数，m n.如如果要求每个果要求每个A后面至少紧跟着后面至少紧跟着1个个B,问有多少个不同的序列？问有多少个不同的序列？3.方法一方法一.先放先放 n 个个B，只有，只有1种方法种方法.然后，在每个然后，在每个B之间的之间的n 个位置中选择个位置中选择 m 个位置放个位置放A,有有C(n,m)种方法种方法.练习练习3：基本的组合计数：基本的组合计数方法二方法二.先放先放 m 个个AB，只有，只有1 种方法种方
36、法.把每个把每个AB 看作格板，看作格板，m 个格板构成个格板构成 m+1个空格，在空格中放入个空格，在空格中放入 n m 个个B.这相这相当当于方程于方程 x1+x2+xm+1=n m 的非负整数解的个数，因此的非负整数解的个数，因此 N=C(n m+m+1 1,n m)=C(n,n m)=C(n,m)50练习练习4方法一方法一.令令|A|=k，按照，按照 k=0,1,n 将有序对将有序对分类分类.给定给定 k，选，选 A方法数是方法数是C(n,k)；选选 B 中剩下的中剩下的 n k 个元素个元素,每个元素有每个元素有2 种选法，有种选法，有2n k 个个不同的不同的 B 集合集合.由乘法
37、法则，这样的由乘法法则，这样的有有C(n,k)2n k 个，个，再使用加法法则和二项式定理，从而得到再使用加法法则和二项式定理，从而得到4.设设 S 是是 n 元集，元集，N 表示满足表示满足 A B S 的有序对的有序对 的个的个数，用二项式定理证明数，用二项式定理证明N=3n方法二方法二.S中的每个元素可以有中的每个元素可以有3种选法：同时加入种选法：同时加入A和和B，不，不加入加入 A 但加入但加入B，A 和和 B 都不加入；都不加入；因此，因此，n 个元素总共个元素总共3n 种选法种选法.51练习练习55.证明证明方法一方法一.利用已知等式利用已知等式将上述两式相加得将上述两式相加得5
38、2练习练习5方法二方法二 利用积分利用积分53练习练习66.求和求和54主要内容主要内容l递推方程的定义及实例递推方程的定义及实例l递推方程的公式解法递推方程的公式解法l递推方程的其他解法递推方程的其他解法l生成函数及其应用生成函数及其应用l指数生成函数及其应用指数生成函数及其应用lCatalan数与数与Stirling数数第十三章第十三章 递推方程与生成函数递推方程与生成函数5513.1递推方程的定义及实例递推方程的定义及实例定义定义13.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(in)联系起来的等式叫做关于序列联系起来的等式叫做关于序
39、列 an 的的递推方递推方程程.当给定递推方程和适当的初值就唯一确定了序列当给定递推方程和适当的初值就唯一确定了序列.Fibonacci数列数列：1，1，2，3，5，8，记作，记作 fn.递推方程递推方程 fn=fn 1+fn 2 初值初值 f0=1，f1=1 阶乘计算数列：阶乘计算数列：1，2，6，24，5！，！，,记作记作 F(n)递推方程递推方程 F(n)=nF(n 1)初值初值 F(1)=1 56例例1 从从A柱将这些圆盘移到柱将这些圆盘移到C柱上去柱上去.如果把一个圆盘从如果把一个圆盘从一个柱子移到另一个柱子称作一次移动，在移动和放置一个柱子移到另一个柱子称作一次移动，在移动和放置时
40、允许使用时允许使用B柱，但不允许大圆盘放到小圆盘的上面柱，但不允许大圆盘放到小圆盘的上面.问问把所有的圆盘的从把所有的圆盘的从A移到移到C总计需要多少次移动？总计需要多少次移动？初值是初值是 T(1)=1 可证明解是可证明解是 T(n)=2n 1 移移动动n个盘子的总次数为个盘子的总次数为T(n).因此得到递推方程因此得到递推方程 T(n)=2T(n 1)+1.递推方程的实例递推方程的实例:Hanoi塔塔57两个排序算法两个排序算法归并算法归并算法 Mergesort(A,p,r)/对对A的下标的下标p到到r之间数排序之间数排序1.if p 0 and Ai key5.do Ai+1 Ai;i i 17.Ai+1 key 58递推方程的实例递推方程的实例:算法分析算法分析例例2 哪种排序算法在最坏情况下复杂度比较低？哪种排序算法在最坏情况下复杂度比较低？插入排序，归并排序插入排序，归并排序 插入排序插入排序 W(n)=W(n 1)+n 1 W(1)=0解得解得 W(n)=O(n2).归并排序，不妨设归并排序，不妨设 n=2k.W(n)=2W(n/2)+n1 W(1)=0解得解得 W(n)=O(nlogn)59