离散数学第12章-基本的组合计数公式省名师优质课赛课获奖课件市赛课一等奖课件.ppt

组合数学研究内容组合数学研究内容组合存在性组合存在性组累计数组累计数组合枚举组合枚举组合优化组合优化本书内容本书内容基本组累计数公式基本组累计数公式递推方程与生成函数递推方程与生成函数第四部分第四部分 组合数学组合数学1/521第十二章第十二章 基本组累计数公式基本组累计数公式主要内容主要内容加法法则与乘法法则加法法则与乘法法则排列与组合排列与组合二项式定理与组合恒等式二项式定理与组合恒等式多项式定理多项式定理2/52212.1 加法法则与乘法法则加法法则与乘法法则加法法则加法法则乘法法则乘法法则分类处理与分步处理分类处理与分步处理3/523加法法则加法法则加法法则加法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生方种产生方式，则式，则“事件事件A或或B”有有 m+n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式不重合产生方式不重合适用问题：分类选取适用问题：分类选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方式，种产生方式，,事件事件 Ak 有有 pk 种产生方式，则种产生方式，则“事件事件A1或或 A2或或 Ak”有有 p1+p2+pk 种产生方式种产生方式.4/524乘法法则乘法法则乘法法则乘法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则“事件事件A与与B”有有 m n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生方式，则种产生方式，则“事件事件A1与与 A2与与 Ak”有有 p1 p2 pk 种产生方式种产生方式.5/525分类处理与分步处理分类处理与分步处理分类处理：对产生方式集合进行划分，分别计数，然后使分类处理：对产生方式集合进行划分，分别计数，然后使用加法法则用加法法则分步处理：一个产生方式分解为若干独立步骤，对每步分分步处理：一个产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则别进行计数，然后使用乘法法则分类与分步结合使用分类与分步结合使用 先分类，每类内部分步先分类，每类内部分步 先分步，每步又分类先分步，每步又分类6/526实例：关系计数实例：关系计数例例1 设设A为为 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种选择，依据乘法法则，组成矩种选择，依据乘法法则，组成矩阵方法数是阵方法数是(1)在自反关系矩阵中，主对角线元素都是在自反关系矩阵中，主对角线元素都是1，其它位置元，其它位置元素能够是素能够是1，也能够是，也能够是0，有，有2种选择种选择.这种位置有这种位置有n2 n个，个，根根据乘法法则，自反关系个数据乘法法则，自反关系个数7/527解答解答(3)非主对角线位置分成非主对角线位置分成(n2 n)/2组，每组包含元素组，每组包含元素rij和和rji.根根据反对称性质，据反对称性质，rij与与rji取值有以下取值有以下3种可能：种可能：rij=1,rji=0；rij=0,rji=1；rij=rji=0.全部这些位置元素选择方法数为全部这些位置元素选择方法数为 .再考虑到主对角再考虑到主对角线元素选取，由乘法法则总方法数为线元素选取，由乘法法则总方法数为(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!.8/528A0 netid (7位)hosted (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位)例例2 2：Ipv4Ipv4网址计数网址计数32位地址位地址 网络标识网络标识+主机标识主机标识(1)A类：最大网络；类：最大网络；B类：中等网络；类：中等网络；C：小网络；：小网络；D：多路广播；：多路广播；E：备用：备用(2)限制条件：限制条件：1111111在在A类中类中netid部分无效部分无效 hostid部分不允许全部分不允许全0或全或全1 9/529 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 NNA+NB+NC3737091842解答解答10/5210选取问题：设选取问题：设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元素.依据是否有序依据是否有序,是否允许重复是否允许重复,将该问题分为四个子类型将该问题分为四个子类型不重复不重复选选取取重复重复选选取取有序有序选选取取集合排列集合排列多重集排列多重集排列无序无序选选取取集合组合集合组合多重集组合多重集组合12.2 排列与组合排列与组合11/5211定义定义12.1 设设S为为n元集，元集，(1)从从 S 中有序选取中有序选取 r 个元素称为个元素称为 S 一个一个 r 排列排列，S 不一样不一样 r 排列总数记作排列总数记作 P(n,r),r=n排列是排列是S全排列全排列.(2)从从 S 中无序选取中无序选取 r 个元素称为个元素称为 S 一个一个 r 组合，组合，S 不一样不一样 r 组合总数记作组合总数记作 C(n,r)集合排列集合排列定理定理1.1 设设n,r为自然数，要求为自然数，要求0!=1，则，则12/5212下面考虑下面考虑 n r 情况情况.(1)排列第一个元素有排列第一个元素有 n 种选择方式种选择方式.排列第二个元素有排列第二个元素有n 1种选法种选法,第第 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/5213推论推论 设设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)=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公式公式，也对应了，也对应了杨辉三角形杨辉三角形证实方法：公式代入并化简，组合证实证实方法：公式代入并化简，组合证实14/5214杨辉三角杨辉三角111121133114641510 1011615 20515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=615/5215多重集排列与组合多重集排列与组合定义定义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 组合组合 注意：注意：多重集中元素重复度，多重集中元素重复度，0 ni +,当当ni+，表示，表示ai重复重复选取次数没有限制选取次数没有限制S子集子集 X=x1 a1,x2 a2,xk ak,其中其中0 xi +16/5216多重集排列计数多重集排列计数定理定理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.依据乘法法则依据乘法法则,(2)r 个位置中每个位置都有个位置中每个位置都有 k 种选法，由乘法法则得种选法，由乘法法则得 kr 17/5217多重集组合多重集组合定理定理12.3 多重集多重集 S=n1 a1,n2 a2,nk ak，0ni +当当 r ni,Sr 组合数为组合数为 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 1个个 0 全排列数为全排列数为18/5218例例3 排列排列26个字母，使得个字母，使得 a 与与 b 之间恰有之间恰有7个字母，求方个字母，求方法数法数.解解 固定固定a 和和 b,中间选中间选7个字母，有个字母，有2 P(24,7)种方法，种方法，将它看作大字母与其余将它看作大字母与其余17个字母全排列有个字母全排列有18！种，共！种，共 N=2 P(24,7)18!组累计数应用组累计数应用解解 相当于相当于2n 不一样球放到不一样球放到 n 个相同盒子，每个盒子个相同盒子，每个盒子2个，个，放法为放法为例例4 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？19/5219解解 使用一一对应思想求解这个问题使用一一对应思想求解这个问题.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中选择中选择 k 个不相邻数，有多少种方个不相邻数，有多少种方法？法？一一对应技巧一一对应技巧20/5220主要内容主要内容二项式定理二项式定理组合恒等式组合恒等式非降路径问题非降路径问题12.3 二项式定理与组合恒等式二项式定理与组合恒等式21/5221二项式定理二项式定理定理定理12.4 设设 n 是正整数，对一切是正整数，对一切 x 和和 y 证实方法证实方法:数学归纳法、组合分析法数学归纳法、组合分析法.证证 当乘积被展开时其中项都是下述形式：当乘积被展开时其中项都是下述形式：xi yn i,i=0,1,2,n.而组成形如而组成形如 xiyn i 项，必须从项，必须从n 个个和和(x+y)中选中选 i 个提供个提供 x，其它，其它 n i 个提供个提供 y.所以，所以，xiyn i 系数是系数是 ，定理得证，定理得证.22/5222二项式定理应用二项式定理应用解解 由二项式定理由二项式定理令令i=13 得到展开式中得到展开式中x12y13系数，即系数，即 例例6 求在求在(2x3y)25展开式中展开式中x12y13系数系数.23/5223组合恒等式：递推式组合恒等式：递推式证实方法：公式代入、组合分析证实方法：公式代入、组合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项之和或者差），然后合并24/5224组合恒等式：基本求和式组合恒等式：基本求和式证实证实公式公式4.方法：二方法：二项项式定理或者式定理或者组组合分析合分析.设设S=1,2,n，下面，下面计计数数S 全部子集全部子集.一个方法就是分一个方法就是分类处类处理，理，n元集合元集合 k子集个数是子集个数是依据加法法则，子集总数是依据加法法则，子集总数是另一个方法是分步处理，为组成另一个方法是分步处理，为组成 S 子集子集A，每个元素有，每个元素有 2 种选择，依据乘法法则，子集总数是种选择，依据乘法法则，子集总数是2n.25/5225恒等式求和恒等式求和:变系数和变系数和证实方法：证实方法：二项式定理、级数求导二项式定理、级数求导 其它组合恒等式代入其它组合恒等式代入26/5226证实公式证实公式627/5227证实公式证实公式728/5228恒等式恒等式:变上项求和变上项求和证实证实 组组合分析合分析.令令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个元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证29/5229恒等式恒等式:乘积转换式乘积转换式证实方法：组合分析证实方法：组合分析.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，求和时提到和号外面，求和时提到和号外面.30/5230恒等式恒等式:积之和积之和关系关系证证明思明思绪绪：考：考虑虑集合集合A=a1,a2,am，B=b1,b2,bn.等等式右式右边计边计数了从数了从这这两个集合中两个集合中选选出出r个元素方法个元素方法.将将这这些些选选法按照含有法按照含有A中元素个数中元素个数 k 进进行分行分类类，k=0,1,r.然后使用加法法然后使用加法法则则.31/5231组合恒等式解题方法小结组合恒等式解题方法小结证实方法：证实方法：已知恒等式带入已知恒等式带入二项式定理二项式定理幂级数求导、积分幂级数求导、积分归纳法归纳法组合分析组合分析求和方法：求和方法：Pascal公式公式级数求和级数求和观察和结果，然后使用归纳法证实观察和结果，然后使用归纳法证实利用已知公式利用已知公式32/5232非降路径计数非降路径计数(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)33/5233从从(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)接触对角线接触对角线 非降路径数非降路径数关系关系:N=2N1=2N2=2N0 N3(0,0)(1,0)(n,n-1)(n,n)限制条件非降路径数限制条件非降路径数34/5234N3:从从(1,0)到到(n,n 1)接触对角线接触对角线 非降路径数非降路径数N4:从从(0,1)到到(n,n 1)无限制条件无限制条件 非降路径数非降路径数关系关系:N3=N4 一一对应一一对应(1,0)(0,1)(n,n-1)(0,0)(n,n)35/5235例例7 A=1,2,m,B=1,2,n，N1:B上单调递增函数个上单调递增函数个 数是数是(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)应用应用:单调函数计数单调函数计数36/5236栈输出计数栈输出计数例例8 将将1,2,n 按照次序输入栈，有多少个不一样输按照次序输入栈，有多少个不一样输出序列？出序列？分析：将进栈、出栈分别记作分析：将进栈、出栈分别记作 x,y,出栈序列是出栈序列是 n个个x，n个个y 排列，排列，排列中任何前缀排列中任何前缀 x 个数不少于个数不少于y 个数，个数，等于从等于从(0,0)到到(n,n)不穿过对角线非降路径数不穿过对角线非降路径数37/5237输入：输入：1,2,3,4,5,输出输出：3,2,4,1,5进进,进进,进进,出出,出出,进进,出出,出出,进进,出出 x,x,x,y,y,x,y,y,x,y 12534栈输出计数栈输出计数38/5238栈输出计数栈输出计数从从(0,0)到到(n,n)穿穿过对角线非降路径过对角线非降路径从从(-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)39/5239A=1,2,m,B=1,2,nf:AB函数计数小结函数计数小结40/5240.定理定理12.6 设设n为正整数，为正整数，xi为实数，为实数，i=1,2,t.求和是对满足方程求和是对满足方程n1+n2+nt=n一切非负整数解求一切非负整数解求在在n个因式中个因式中选选n1个因式个因式贡贡献献x1,从剩下从剩下n n1个因式个因式选选n2个因式个因式贡贡献献x2,从剩下从剩下n n1 n2 nt 1个因式中个因式中选选 nt个因式个因式贡贡献献 xt.证实证实 展开式中项展开式中项是以下组成是以下组成:12.4 多项式多项式定理定理41/5241推论推论推论推论1 多项式展开式中不一样项数为方程多项式展开式中不一样项数为方程 非负整数解个数非负整数解个数 C(n+t 1,n)推论推论2 例例9 求求(2x1 3x2+5x3)6 中中 x13x2x32 系数系数.解解 由多项式定理得由多项式定理得42/5242多项式系数多项式系数组合意义组合意义多项式系数多项式系数多重集多重集 S=n1 a1,n2 a2,nt at 全排列数全排列数 n个不一样球放到个不一样球放到 t 个不一样盒子使得第一个盒子含个不一样盒子使得第一个盒子含n1个个球，第二个盒子含球，第二个盒子含n2个球，个球，第，第 t 个盒子含个盒子含 nt 个球方案个球方案数数符号符号43/5243第十二章第十二章 习题课习题课主要内容主要内容基本计数基本计数 计数法则：加法法则、乘法法则计数法则：加法法则、乘法法则 计数模型：选取问题、非降路径问题、方程非负整数计数模型：选取问题、非降路径问题、方程非负整数 解问题解问题 处理方法：分类处理、分步处理、一一对应思想处理方法：分类处理、分步处理、一一对应思想 计数符号计数符号 组合数或二项式系数组合数或二项式系数 C(m,n)：组合恒等式：组合恒等式 排列数排列数 P(m,n)多项式系数多项式系数 二项式定理与多项式定理二项式定理与多项式定理44/5244基本要求基本要求能够熟练使用加法法则与乘法法则能够熟练使用加法法则与乘法法则熟悉和应用基本组累计数模型：熟悉和应用基本组累计数模型：选取问题选取问题 不等方程解不等方程解 非降路径非降路径熟悉二项式定理与多项式定理熟悉二项式定理与多项式定理能证实组合恒等式并对二项式系数进行求和能证实组合恒等式并对二项式系数进行求和了解多项式系数及其相关公式了解多项式系数及其相关公式45/5245练习练习1：基本组累计数基本组累计数1.求求1400不一样正因子个数不一样正因子个数.解解 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.46/5246练习练习2：基本组累计数：基本组累计数2把把10个不一样球放到个不一样球放到6个不一样盒子里，允许空盒，且前个不一样盒子里，允许空盒，且前2个盒子球总数至多是个盒子球总数至多是4，问有多少种方法？，问有多少种方法？解解 依据前两个盒子含球数依据前两个盒子含球数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)2k 4n k 最终使用加法法则对最终使用加法法则对k求和，就得到所求方法数是求和，就得到所求方法数是47/52473由由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 种方法种方法.把每个把每个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)48/5248练习练习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 表示满足表示满足 A B S 有序对有序对 个数，个数，用二项式定理证实用二项式定理证实N=3n方法二方法二.S中每个元素能够有中每个元素能够有3种选法：同时加入种选法：同时加入A和和B，不，不加入加入 A 但加入但加入B，A 和和 B 都不加入；都不加入；所以，所以，n 个元素总共个元素总共3n 种选法种选法.49/5249练习练习55.证实证实方法一方法一.利用已知等式利用已知等式将上述两式相加得将上述两式相加得50/5250练习练习5方法二方法二 利用积分利用积分51/5251练习练习66.求和求和52/5252