离散数学第8章

第第8 8章章 组合计数基础组合计数基础1第第8章章 组合计数基础组合计数基础引言引言 组合问题的处理技巧组合问题的处理技巧8.1 基本计数规则基本计数规则8.2 排列与组合排列与组合8.3 二项式定理与组合恒等式二项式定理与组合恒等式8.4 多项式定理多项式定理2组合问题的处理技巧组合问题的处理技巧一一对应一一对应数学归纳法数学归纳法上下界逼近上下界逼近3一一对应与上下界逼近一一对应与上下界逼近例例1 1 在允许移动被切割的物体的情况下，在允许移动被切割的物体的情况下，最少用多少次切割可以将最少用多少次切割可以将 3 3 3 的立的立方体切成方体切成 27个单位边长的立方体？个单位边长的立方体？中间的小立方体的中间的小立方体的6个面都是切割产生的面，每次切割个面都是切割产生的面，每次切割至多产生一个面，至少需要至多产生一个面，至少需要6次切割。存在一种切割方次切割。存在一种切割方法恰好用法恰好用 6 次切割。次切割。例例2 100个选手淘汰赛，为产生冠军至少需要多少轮比赛？个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法方法1：50+25+12+6+3+2+1=99 方法方法2：比赛次数与淘汰人数之间存在一一对应，总计淘：比赛次数与淘汰人数之间存在一一对应，总计淘汰汰99人，因此至少需要人，因此至少需要99场比赛场比赛.48.1 基本计数规则基本计数规则8.1.1 加法法则加法法则8.1.2 乘法法则乘法法则8.1.3 分类处理与分步处理分类处理与分步处理5加法法则加法法则加法法则加法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则“事件事件A或或B”有有 m+n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1或或 A2或或 Ak”有有 p1+p2+pk 种产生的方式种产生的方式.6乘法法则乘法法则乘法法则乘法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则“事件事件A与与B”有有 m n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，,事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则“事件事件A1与与 A2与与 Ak”有有 p1 p2 pk 种产生的方式种产生的方式.7分类处理与分步处理分类处理与分步处理分类处理：对产生方式的集合进行划分，分别计数，然分类处理：对产生方式的集合进行划分，分别计数，然后使用加法法则后使用加法法则分步处理：一种产生方式分解为若干独立步骤，对每步分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则分别进行计数，然后使用乘法法则分类与分步结合使用：分类与分步结合使用：先分类，每类内部分步先分类，每类内部分步 先分步，每步又分类先分步，每步又分类8应用实例应用实例例例3 设设A,B,C 是是3个城市，从个城市，从A 到到 B 有有3条道路，从条道路，从B 到到C 有有2条道路，从条道路，从A 直接到直接到 C 有有4条道路，问从条道路，问从 A 到到 C 有有多少种不同的方式？多少种不同的方式？解：解：N=3 2+4=10例例4 求求1400的不同的正因子个数的不同的正因子个数 1400=23 52 7 解：正因子为：解：正因子为：2i 5j 7k，其中，其中 0 i 3,0 j 2,0 k 1 N=(3+1)(2+1)(1+1)=2498.2 排列与组合排列与组合引言引言 选取问题选取问题8.2.1 集合的排列与组合集合的排列与组合8.2.2 多重集的排列与组合多重集的排列与组合10选取问题选取问题-组合计数模型组合计数模型1设设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元素.根据是否有序，是否允许重复可以将该问题分为四个子类根据是否有序，是否允许重复可以将该问题分为四个子类型型不重复不重复选取取重复重复选取取有序有序选取取集合的排列集合的排列多重集的排列多重集的排列无序无序选取取集合的集合的组合合多重集的多重集的组合合11集合的排列集合的排列定义定义 从从 n 元集元集 S 中有序、不重复选取的中有序、不重复选取的 r 个元素称为个元素称为 S 的一个的一个 r 排列排列，S 的所有的所有 r 排列的数目记作排列的数目记作 P(n,r)定理定理8.1 证明证明 使用乘法法则使用乘法法则推论推论 S 的环排列数的环排列数=12集合的组合集合的组合定义定义 从从 n 元集元集 S 中无序、不重复选取的中无序、不重复选取的 r 个元素称为个元素称为 S 的一个的一个 r 组合，组合，S 的所有的所有 r 组合的数目记作组合的数目记作 C(n,r)定理定理8.2 推论推论 设设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)13证明方法证明方法方法方法1：公式代入并化简：公式代入并化简方法方法2：组合证明：组合证明实例：证明实例：证明 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)组合数相等组合数相等.C(n,r)=C(n 1,r 1)+C(n 1,r)称为称为 Pascal公式公式，也对应，也对应了了杨杨辉三角形辉三角形，两种证明方法都适用两种证明方法都适用.14杨辉三角杨辉三角15基本计数公式的应用基本计数公式的应用解解 分类选取分类选取 A=1,4,298 B=2,5,299 C=3,6,300分别取自分别取自 A,B,C:各各 C(100,3)A,B,C 各取各取 1 个（分步处理）：个（分步处理）：C(100,1)3 N=3C(100,3)+1003=1485100例例8.5 从从1300中任取中任取3个数使得其和能被个数使得其和能被3整除有多少整除有多少种方法？种方法？16基本计数公式的应用基本计数公式的应用(续续)解解:1000!=1000 999 998 2 1将上面的每个因子分解，若分解式中共有将上面的每个因子分解，若分解式中共有i 个个5,j 个个2，那么那么min(i,j)就是就是0的个数的个数.1,1000中有中有 500个是个是 2 的倍数，的倍数，j 500;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？17基本计数公式的应用基本计数公式的应用(续续)例例3 设设A为为 n 元集，问元集，问(1)A上的自反关系有多少个？上的自反关系有多少个？(2)A上的反自反关系有多少个？上的反自反关系有多少个？(3)A上的对称关系有多少个？上的对称关系有多少个？(4)A上的反对称关系有多少个？上的反对称关系有多少个？(5)A上既不对称也不是反对称上既不对称也不是反对称 的关系有多少个？的关系有多少个？18多重集的排列多重集的排列定理定理8.3 多重集多重集S=n1 a1,n2 a2,nk ak，0 ni +(1)全排列全排列 r=n,n1+n2+nk=n 证明：分步选取证明：分步选取.先放先放a1,有有C(n,n1)种方法；再放种方法；再放a2,有有C(n n1,n2)种方法种方法,.,放放ak,有有C(n n1 n2 nk 1,nk)种方法种方法 (2)若若r ni 时，每个位置都有时，每个位置都有 k 种选法，得种选法，得 kr.19多重集的组合多重集的组合定理定理8.4 多重集多重集 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 1个个 0 的全排列数为的全排列数为20实例实例例例5 排列排列26个字母，使得个字母，使得 a 与与 b 之间恰有之间恰有7个字母，求方个字母，求方法数法数.解：解：设盒子的球数依次记为设盒子的球数依次记为 x1,x2,xn,则满足则满足 x1+x2+xn=r，x1,x2,xn 为非负整数为非负整数 N=C(n+r 1,r)例例4 r 个相同的球放到个相同的球放到 n 个不同的盒子里，每个盒子球数个不同的盒子里，每个盒子球数不限，求放球方法数不限，求放球方法数.解：解：固定固定a 和和 b,中间选中间选7个字母，有个字母，有2 P(24,7)种方法，种方法，将它看作大字母与其余将它看作大字母与其余17个字母全排列有个字母全排列有18！种，共！种，共 N=2 P(24,7)18!21实例实例(续续)例例6(1)10个男孩，个男孩，5个女孩站成一排，若没有女孩相邻，个女孩站成一排，若没有女孩相邻，有多少种方法？有多少种方法？(2)如果站成一个圆圈，有多少种方法？如果站成一个圆圈，有多少种方法？解解:(1)P(10,10)P(11,5)(2)P(10,10)P(10,5)/10解：相当于解：相当于2n 不同的球放到不同的球放到 n 个相同的盒子，每个盒子个相同的盒子，每个盒子2个，放法为个，放法为例例7 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？22实例实例(续续)解解 使用一一对应的思想求解这个问题使用一一对应的思想求解这个问题.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)例例8 从从S=1,2,n中选择中选择 k 个不相邻的数，有多少种个不相邻的数，有多少种方法？方法？238.3二项式定理与组合恒等式二项式定理与组合恒等式8.3.1 二项式定理8.3.2 组合恒等式8.3.3 非降路径问题24二项式定理二项式定理定理定理8.5 设设 n 是正整数，对一切是正整数，对一切 x 和和 y 证明方法证明方法:数学归纳法、组合分析法数学归纳法、组合分析法.证证 当乘积被展开时其中的项都是下述形式：当乘积被展开时其中的项都是下述形式：xi yn i,i=0,1,2,n.而构成形如而构成形如 xiyn i 的项，必须从的项，必须从n 个个和和(x+y)中选中选 i 个提供个提供 x，其它的，其它的 n i 个提供个提供 y.因此，因此，xiyn i 的系数是的系数是 ，定理得证，定理得证.25二项式定理的应用二项式定理的应用例例1 求在求在(2x3y)25的展开式中的展开式中x12y13的系数的系数.解解 由二项式定理由二项式定理令令i=13 得到展开式中得到展开式中x12y13的系数，即的系数，即 26组合恒等式组合恒等式递推式递推式证明方法：公式代入、组合分析证明方法：公式代入、组合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项之和或者差），然后合并27组合恒等式组合恒等式变下项求和变下项求和证明公式明公式4.方法：二方法：二项式定理或者式定理或者组合分析合分析.设S=1,2,n，下面，下面计数数S 的所有子集的所有子集.一种方法就是分一种方法就是分类处理，理，n元集合的元集合的 k子集个数是子集个数是根据加法法则，子集总数是根据加法法则，子集总数是另一种方法是分步处理，为构成另一种方法是分步处理，为构成 S 的子集的子集A，每个元素有，每个元素有 2 种选择，根据乘法法则，子集总数是种选择，根据乘法法则，子集总数是2n.28恒等式求和恒等式求和变系数和变系数和证明方法：证明方法：二项式定理、级数求导二项式定理、级数求导 其他组合恒等式代入其他组合恒等式代入29证明公式证明公式6(二项式定理二项式定理+求导求导)30证明公式证明公式7(已知恒等式代入已知恒等式代入)31恒等式恒等式变上项求和变上项求和证明明 组合分析合分析.令令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个元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证32恒等式恒等式乘积转换式乘积转换式证明方法：组合分析证明方法：组合分析.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，求和时提到和号外面，求和时提到和号外面.33恒等式恒等式积之和积之和关系关系证明思路：考明思路：考虑集合集合A=a1,a2,am，B=b1,b2,bn.等等式右式右边计数了从数了从这两个集合中两个集合中选出出r个元素的方法个元素的方法.将将这些些选法按照含有法按照含有A中元素的个数中元素的个数 k 进行分行分类，k=0,1,r.然后使用加法法然后使用加法法则.34组合恒等式解题方法小结组合恒等式解题方法小结证明方法：证明方法：已知恒等式带入已知恒等式带入 二项式定理二项式定理 幂级数的求导、积分幂级数的求导、积分 归纳法归纳法 组合分析组合分析 求和方法：求和方法：Pascal公式公式 级数求和级数求和 观察和的结果，然后使用归纳法证明观察和的结果，然后使用归纳法证明 利用已知的公式利用已知的公式35非降路径问题非降路径问题基本计数模型限制条件下的非降路径数非降路径模型的应用证明恒等式证明恒等式单调函数计数单调函数计数栈的输出栈的输出 36基本计数模型基本计数模型(0,0)到到(m,n)的非降路径数：的非降路径数：C(m+n,m)(a,b)到到(m,n)的非降路径数：的非降路径数：等于等于(0,0)到到(m a,n b)的非降路径数的非降路径数(a,b)经过经过(c,d)到到(m,n)的非降路径数：乘法法则的非降路径数：乘法法则37限制条件的非降路径数限制条件的非降路径数从从(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 38一一对应一一对应N3:从从(1,0)到到(n,n 1)接触对角线的接触对角线的 非降路径数非降路径数N4:从从(0,1)到到(n,n 1)无限制条件的无限制条件的 非降路径数非降路径数关系关系:N3=N4 39应用应用证明恒等式证明恒等式例例2 证明证明 证：证：计数计数(0,0)到到(m+n r,r)的非降路径数的非降路径数按照按照 k分类，再分步分类，再分步.(0,0)到到(m k,k)路径数，路径数，(m k,k)到到(m+n r,r)的的路径数路径数40应用应用单调函数计数单调函数计数例例3 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)41函数计数小结函数计数小结A=1,2,m,B=1,2,nf:AB42应用应用栈输出的计数栈输出的计数例例4 将将1,2,n按照顺序输入栈按照顺序输入栈,有多少个不同的输出序列？有多少个不同的输出序列？解：将进栈、出栈分别记作解：将进栈、出栈分别记作 x,y,出栈序列是出栈序列是n个个x，n个个y的排的排列，排列中任何前缀的列，排列中任何前缀的 x 个数不少于个数不少于y 的个数的个数.等于从等于从(0,0)到到(n,n)的不穿过对角线的非降路径数的不穿过对角线的非降路径数.实例：实例：n=5 x,x,x,y,y,x,y,y,x,y 进进,进进,进进,出出,出出,进进,出出,出出,进进,出出 3,2,4,1,543应用应用栈输出的计数栈输出的计数(续续)N:堆栈输出个数堆栈输出个数N:(0,0)到到(n,n)不不 穿过对角线的穿过对角线的 非降路径数非降路径数N0:(0,0)到到(n,n)的的 非降路径总数非降路径总数N1:(0,0)到到(n,n)的的 穿过对角线的穿过对角线的 非降路径数非降路径数N2:(1,1)到到(n,n)的非降路径数的非降路径数.关系：关系：N=N =N0 N1,N1=N2448.4.1 多项式定理8.4.2 多项式系数8.4 多项式定理多项式定理45多项式定理多项式定理.定理定理8.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.证明证明 展开式中的项展开式中的项是如下构成的是如下构成的:46推论推论推论1 多项式展开式中不同的项数为方程 的非负整数解的个数 C(n+t 1,n)推论2 例例1 求求(2x1 3x2+5x3)6 中中 x13x2x32 的系数的系数.解解 由多项式定理得由多项式定理得47多项式系数多项式系数组合意义组合意义 多项式系数多项式系数 多重集多重集 S=n1 a1,n2 a2,nt at 的全排列数的全排列数 n个不同的球放到个不同的球放到 t 个不同的盒子使得第一个盒子个不同的盒子使得第一个盒子 含含n1个球，第二个盒子含个球，第二个盒子含n2个球，个球，第，第 t 个盒子个盒子 含含 nt 个球的方案数个球的方案数48多项式系数多项式系数(续续)恒等式恒等式推论推论2 2定理定理8.68.6组合证明组合证明49