组合数学第四章二项式系数课件.ppt

组合数学课件第四章二项式系数第1页，此课件共58页哦目录（目录（1）第第1章章 什么是组合数学什么是组合数学1.1引例引例1.2组合数学研究对象、内容和方法组合数学研究对象、内容和方法第第2章章 鸽巢原理鸽巢原理2.1 鸽巢原理：简单形式鸽巢原理：简单形式2.2 鸽巢原理：加强形式鸽巢原理：加强形式2.3 Ramsey定理定理2.4 鸽巢原理与鸽巢原理与Ramsey定理的应用定理的应用本章小结习题第第3章章 排列与组合排列与组合3.1 两个基本的计数原理两个基本的计数原理3.2 集合的排列与组合集合的排列与组合3.3 多重集的排列与组合多重集的排列与组合本章小结习题第四章第四章 二项式系数二项式系数4.1 二项式定理二项式定理4.2组合恒等式组合恒等式4.3非降路径问题非降路径问题4.4牛顿二项式定理牛顿二项式定理4.5多项式定理多项式定理4.6 基本组合计数的应用基本组合计数的应用本章小结习题第五章第五章 包含排斥原理包含排斥原理5.1 包含排斥原理包含排斥原理5.2 多重集的多重集的r-组合数组合数5.3错位排列错位排列5.4 有限制条件的排列问题有限制条件的排列问题5.5有禁区的排列问题有禁区的排列问题本章小结习题目目 录录第2页，此课件共58页哦目录（目录（2）第六章第六章 递推关系递推关系6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系本章小结习题第七章第七章 生成函数生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5Catalan数和Stiring数本章小结习题 第八章第八章 Polya定理定理8.1置换群中的共轭类与轨道8.2Polya定理的特殊形式及其应用本章小结习题*课程总结课程总结第3页，此课件共58页哦教学目标：教学目标：1掌握二项式定理、证明方法及其应用；掌握二项式定理、证明方法及其应用；2掌握推广的二项式定理；掌握推广的二项式定理；3掌握多项式定理、证明方法及其应用；掌握多项式定理、证明方法及其应用；4理解一些组合恒等式的意义及其证明方法；理解一些组合恒等式的意义及其证明方法；5非降路径问题的组合意义及应用；非降路径问题的组合意义及应用；重点：重点：二项式定理、多项式定理证明方法及其应用；二项式定理、多项式定理证明方法及其应用；难点：难点：一些组合恒等式证明方法，非降路径问题组合意义及应用。一些组合恒等式证明方法，非降路径问题组合意义及应用。第4页，此课件共58页哦4.1二项式定理1.二项式系数组合数C(n,k)或者 也叫二项式系数.2.组合数的定义()nk第5页，此课件共58页哦3.组合数的一些恒等式（1）对称式（2）抽取式（3）Pascal公式(4.1)(4.2)(4.3)第6页，此课件共58页哦4.2 组合恒等式及其含义抽取式(4.2)抽取式（抽取式（4.2）：）：如如n,kN，有有C(n,k)=(n/k)C(n-1,k-1)证证明明：从从n个个元元素素中中取取k个个的的组组合合可可先先从从n个个元元素素中中取取1个个，再再从从剩剩下下的的n-1个个元元素素中中选选择择k-1个个，组组合合数数为为C(n-1,k-1)。选选出出的的k个个元素都有可能被第一次选中，因是组合，故重复度为元素都有可能被第一次选中，因是组合，故重复度为k。得证。得证。或通过计算证明：或通过计算证明：证：某班有证：某班有证：某班有证：某班有n n名同学，要选出名同学，要选出名同学，要选出名同学，要选出k k位班委会成员，再位班委会成员，再位班委会成员，再位班委会成员，再选选选选1 1名作书记，这名书记不可以是班委会成员，问有名作书记，这名书记不可以是班委会成员，问有名作书记，这名书记不可以是班委会成员，问有名作书记，这名书记不可以是班委会成员，问有多少种不同的方案？多少种不同的方案？多少种不同的方案？多少种不同的方案？证明：从证明：从证明：从证明：从n n名同学中选出名同学中选出名同学中选出名同学中选出k k位组成班委，位组成班委，位组成班委，位组成班委，在在在在k k位班委中选位班委中选位班委中选位班委中选1 1人做班长，问有多少种人做班长，问有多少种人做班长，问有多少种人做班长，问有多少种方法？方法？方法？方法？第7页，此课件共58页哦4.1二项式定理证证明明：因因为为(x+y)n=(x+y)(x+y)(x+y)，等等式式右右端端有有n个个因因子子，项项xkyn-k是是从从这这n个个因因子子中中选选取取k个个因因子子，k=0,1,n。在在这这k个个(x+y)里里都都取取x，而而从从剩剩下下的的n-k个个因因子子(x+y)中中选选取取y作作乘乘积积得得到到，因因此此xkyn-k的系数为上述选法的个数的系数为上述选法的个数C(n,k)。故有。故有证毕。证毕。注：可用数学归纳法证明，证明略；注：可用数学归纳法证明，证明略；C(n,k)又称又称二项式系数二项式系数。第8页，此课件共58页哦4.1二项式定理推论1推论推论4.1.1：推论推论4.1.2：推论推论4.1.3：证明：证明：在推论在推论4.1.2中令中令x=1，即可得证。，即可得证。利利用用组组合合分分析析，等等式式左左端端相相当当于于从从A=an中中任任意意选选择择k(0kn)个个元元素素的的所所有有可可能能数数目目，即即对对n个个元元素素，每每一一个个都都有有被被选选择择和和不不被被选选择择的的可可能能，总总的的可可能数为能数为2n。另外，该等式还表明另外，该等式还表明A的所有子集个数为的所有子集个数为2n。(4.4)n n元集合的所有子集个数是元集合的所有子集个数是元集合的所有子集个数是元集合的所有子集个数是2 2n n 第9页，此课件共58页哦4.1二项式定理推论2推论推论4.1.1：推论推论4.1.2：推论推论4.1.3：推论推论4.1.4：证明：证明：在推论在推论4.1.2中令中令x=-1，即可得证。，即可得证。另外，该等式还表明另外，该等式还表明A=an的偶数子集个数和奇数子集个数相等。的偶数子集个数和奇数子集个数相等。(4.5)(4.5)即即 n n 元集合的偶子集个数与奇子集个元集合的偶子集个数与奇子集个元集合的偶子集个数与奇子集个元集合的偶子集个数与奇子集个数相等数相等数相等数相等 第10页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.6)恒等式恒等式(4.6)：证证明明：考考虑虑盒盒子子1中中有有n个个有有区区别别的的球球，从从中中取取一一个个球球放放入入盒盒子子2中中，再再取取任任意意多多个个球球放放入入盒盒子子3中中。等等式式左左端端表表示示先先从从盒盒子子1中中取取k(k=1,2,n)个个球球，再再从从中中取取一一个个放放入入盒盒子子2中中，剩剩下下的的k-1个个球球放放入入盒盒子子3中中。等等式式右右端端表表示示先先从从盒盒子子1中中取取一一个个放放入入盒盒子子2中中，剩剩下下的的n-1个个球球是是否否放放入入盒盒子子3中均有两种可能。显然两种取法结果是一样的。得证。中均有两种可能。显然两种取法结果是一样的。得证。或通过或通过计算计算证明：证明：第11页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.6)恒等式恒等式(4.6)：证明：证明：证法证法3 由二项式定理有由二项式定理有对上式两边微商得对上式两边微商得然后令然后令x=1得得注：如令注：如令x=-1，可证明下面，可证明下面恒等式恒等式。第12页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.6)类（类（4.6）恒等式）恒等式(习题习题4.7)：证明：证明：将等式两边对将等式两边对x微分得微分得在上式中，令在上式中，令x=-1得得即即得证。得证。第13页，此课件共58页哦4.2组合恒等式及其含义恒等式(4.6)恒等式恒等式(习题习题4.8积分方法积分方法)：证明：证明：将等式两边对将等式两边对x从从0到到1积分得积分得即即得证。得证。第14页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.7)类恒等式类恒等式(4.7)：恒等式恒等式(4.7)：证明：证明：将等式两边对将等式两边对x微分得微分得将等式两边同乘以将等式两边同乘以x后再对后再对x微分得微分得在上式中，令在上式中，令x=1得得得证。得证。注：如令注：如令x=-1，即可证明另一，即可证明另一恒等式恒等式(4.7)。第15页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.8)恒等式恒等式(4.8)：如如n,l,rN,lr，有有C(n,l)C(l,r)=C(n,r)C(n-r,l-r)从从从从n n个候选人中，选出个候选人中，选出个候选人中，选出个候选人中，选出l l个常委，再选出个常委，再选出个常委，再选出个常委，再选出r r位政治局常位政治局常位政治局常位政治局常委，选法的个数？委，选法的个数？委，选法的个数？委，选法的个数？证证明明：等等式式的的左左端端可可看看作作是是先先从从n个个元元素素中中取取l个个元元素素，然然后后再再从从所所得得的的l个个元元素素中中再再选选择择r个个元元素素的的方方法法数数。这这种种选选法法与与直直接接从从n个个元元素素中中选选取取r个个元元素素的的选选法法不不同同.因因为为同同样样的的r个个元元素素可可以以多多次次出出 现现.例例 如如 7元元 集集 a,b,c,d,e,j,k，从从 中中 选选 5个个 元元 素素，比比 如如 说说a,b,c,d,e和和a,b,c,j,k，它它们们都都可可以以选选出出同同样样的的3个个元元素素a,b,c，不不难难看看出出，某某r个个元元素素可可以以重重复复出出现现的的次次数数就就是是包包含含它它们们的的l元元子子集集的的个个数数，而而这这种种l元元子子集集的的其其余余l-r个个元元素素可可以以取取自自n元元集集的的n-r个个元元素素,所所以以这这种种l元元子子集集有有 个个.综综上上所所述述，通通过过先先选选l个个元素然后再选元素然后再选r个元素的选法应该有个元素的选法应该有C(n,r)C(n-r,l-r)种。得证。种。得证。或通过计算证明：或通过计算证明：第16页，此课件共58页哦恒等式恒等式(4.9)：Vandermonde恒等式，如恒等式，如n,mN且且rmin(m,n)，有，有C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0)4.2 组合恒等式及其含义恒等式(4.9)证证明明：设设A=am,B=bn,且且AB=，则则AB=C有有m+n个个元元素素。C的的r组组合合个个数数为为C(m+n,r)，而而C的的每每个个r组组合合无无非非是是先先从从A中中取取k个个元元素素，再再从从B中中取取出出r-k个个元元素素组组成成(k=0,1,r)。由由乘乘法法法法则则共共有有C(m,k)C(n,r-k)种取法，再由加法法则即可得证。种取法，再由加法法则即可得证。或通过或通过比较系数法比较系数法证明：证明：比较等式两边比较等式两边xr的系数即可得证。的系数即可得证。第17页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.10)恒等式恒等式(4.10)：恒等式恒等式(4.10特例特例)：恒等式恒等式(4.9)：Vandermonde恒等式，如恒等式，如n,mN且且rmin(m,n)，有，有C(m+n,r)=C(n,0)C(m,r)+C(n,1)C(m,r-1)+C(n,r)C(m,0)恒等式恒等式(4.10)：第18页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.11)恒等式恒等式(4.11)：证证明明：利利用用组组合合分分析析法法，在在集集合合A=an+1的的n+1个个不不同同元元素素选选出出k+1个个元元素素的的组组合合可可分分为为以以下下多多种种情情况况：如如k+1个个元元素素中中包包含含a1，相相当当于于从从除除去去a1的的n个个元元素素中中选选出出k个个元元素素的的组组合合，组组合合数数为为C(n,k)；如如不不包包含含a1但但包包含含a2，相相当当于于从从除除去去a1,a2的的n-1个个元元素素中中选选出出k个个元元素素的的组组合合，再再加加上上a2而而得得到到，组组合合数数为为C(n-1,k),同同理理如如不不包包含含a1,a2,an-k+1，但但包包含含an-k+2，相相当当于于从从剩剩下下的的k个个元元素素中中选选出出k个个元元素素的的组组合合，再再加加上上an-k+2而而得得到到，组组合合数数为为C(k,k)；注意，；注意，ik时时，C(k,k)=0。由加法法则得。由加法法则得或对固定的或对固定的k，对，对n使用使用归纳法归纳法，当，当n=0时，有时，有可见，当可见，当n=0时，等式成立。时，等式成立。如对任意如对任意n等式成立，则有等式成立，则有可见等式对可见等式对n+1也成立。由归纳原理，得证。也成立。由归纳原理，得证。第19页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.12)恒等式恒等式(4.12)：如如n,rN，有有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)证明证明I：反复利用反复利用Pascal公式，即可证明。公式，即可证明。或利用组合分析法，在集合或利用组合分析法，在集合A=an+r+1的的n+r+1个不同元素选出个不同元素选出r个元素的个元素的组合可分为以下多种情况：如组合可分为以下多种情况：如r个元素中不包含个元素中不包含a1，相当于从除去，相当于从除去a1的的n+r个元素中选出个元素中选出r个元素的组合，组合数为个元素的组合，组合数为C(n+r,r)；如；如r个元素中包个元素中包含含a1但不包含但不包含a2，相当于从除去，相当于从除去a1,a2的的n+r-1个元素中选出个元素中选出r-1个元素的组个元素的组合，再加上合，再加上a1而得到，组合数为而得到，组合数为C(n+r-1,r-1),同理如同理如r个元素中包含个元素中包含a1,a2,ar-1，但不包含，但不包含ar，相当于从剩下的，相当于从剩下的n+1个元素中选出个元素中选出1个元素的组个元素的组合，再加上合，再加上a1,a2,ar-1而得到，组合数为而得到，组合数为C(n+1,1)；如；如r个元素中包含个元素中包含a1,a2,ar，相当于从剩下的，相当于从剩下的n个元素中选出个元素中选出0个元素的组合，组合数为个元素的组合，组合数为C(n,0)。由加法法则得。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)第20页，此课件共58页哦4.2 组合恒等式及其含义恒等式(4.12)恒等式恒等式(4.12)：如如n,rN，有有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)证证明明II：等等式式的的左左端端可可看看作作是是在在集集合合A=an+2的的n+2个个不不同同元元素素允允许许重重复复的的选选出出r个个元元素素的的组组合合，可可分分为为以以下下多多种种情情况况：如如r个个元元素素中中不不包包含含a1，相相当当于于从从除除去去a1的的n+1个个元元素素中中允允许许重重复复的的选选出出r个个元元素素的的组组合合，组组合合数数为为C(n+r,r)；如如r个个元元素素中中只只包包含含一一个个a1，相相当当于于从从除除去去a1的的n+1个个元元素素中中允允许许重重复复的的选选出出r-1个个元元素素的的组组合合，再再加加上上a1而而得得到到，组组合合数数为为C(n+r-1,r-1)；如如r个个元元素素中中包包含含两两个个a1，相相当当于于从从除除去去a1的的n+1个个元元素素中中允允许许重重复复的的选选出出r-2个个元元素素的的组组合合，再再加加上上两两个个a1而而得得到到，组组合合数数为为C(n+r-2,r-2),同理如同理如r个元素中包含个元素中包含r个个a1，其组合数为，其组合数为C(n,0)。由加法法则得。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)第21页，此课件共58页哦4.2 组合恒等式证明方法 数学归纳法数学归纳法 二项式系数公式，特别是二项式系数公式，特别是Pascal 公式公式 比较级数展开式中的系数（二项式定理或母函数法）比较级数展开式中的系数（二项式定理或母函数法）积分微分法积分微分法 组合分析法组合分析法第22页，此课件共58页哦4.2 组合恒等式及其含义例4.1例例4.1 如如n,rN，r n,有有C(n,r+1)=C(r,r)+C(r+1,r)+C(n-1,r)证明证明在上面的等式中，用n+r代替n，得恒等式(4.13):C(n+r,r+1)=C(r,r)+C(r+1,r)+C(r+n-1,r).第23页，此课件共58页哦在式（4.13）中，如果令r=1，就得到 1+2+3+n=C(n+1,2)=n(n+1)/2.这是等差级数的求和公式.如果令r=2，则有 1+C(3,2)+C(4,2)+C(n+1,2)=C(n+2,3)=n(n+1)(n+2)/6.在这个等式中每相邻两项之差就是等差级数的项，称这个等式叫做二阶等差级数求和公式.如果令r=3，则有 1+C(4,3)+C(5,3)+C(n+2,3)=C(n+3,4).其中每相邻两项之差就是二阶等差级数的项，把这个 等式叫做三阶等差级数的求和公式.第24页，此课件共58页哦4.2 组合恒等式及其含义例4.2例例4.2 计算计算 12+22+32+n2,13+23+33+n3.解解 对任何正整数对任何正整数k，有，有k2=2C(k,2)+C(k,1),k3=6C(k,3)+6C(k,2)+C(k,1).所以有所以有 12+22+n2 =2C(1,2)+C(2,2)+C(n,2)+C(1,1)+C(2,1)+C(n,1)=2(n+1)n(n-1)/6+(n+1)n/2 =n(n+1)(2n+1)/6.13+23+n3 =6C(1,3)+C(2,3)+C(n,3)+6C(1,2)+C(2,2)+C(n,2)+C(1,1)+C(2,1)+C(n,1)=6(n+1,4)+6(n+1,3)+(n+1,2)=2(n+1)n(n-1)/6+(n+1)n/2 =n(n+1)/22.第25页，此课件共58页哦4.2 组合恒等式及其含义例4.3例例4.3 证明若证明若p是不等于是不等于2的素数，则当的素数，则当C(2p,p)被被p除时余数是除时余数是2.证明证明 在恒在恒等式等式(4.10)中中令令m=n=p得得可可以以证证明明，如如果果p为为素素数数且且0kp，则则p|C(p,k).因因为为由由组组合合数数C(p,k)的的计计算算公公式式知知k!整整除除p(p-1)(p-k+1).又又由由于于p是是素素数数且且k1,则则k!|(p-1)(p-k+1)；若若k=1,也也有有k!|(p-1)(p-k+1).所所以以C(p,k)是是p的的倍倍数数.在在等等式式(4.14)中中，C(p,1)2+C(p,2)2+C(p,p-1)2一一定定是是p的的倍倍数数，而而C(p,0)2+C(p,p)2=1+1=2，故当，故当p2时，时，C(2p,p)除以除以p的余数是的余数是2.(4.14)第26页，此课件共58页哦例4.4证明：从n名女同学和n名男同学中，选出n名同学组成一个社团，其中一人担任社团主席，且必须由女同学担任，问有多少种选法？第27页，此课件共58页哦4.3非降路径问题引非降路径问题引例引例、非降路径问题从(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？解解：设设从从(0,0)点点水水平平方方向向向向前前进进一一步步为为x，垂垂直直方方向向向向上上进进一一步步为为y。于于是是从从(0,0)点点到到(m,n)点点，水水平平方方向向走走m步步，垂垂直直方方向向走走n步步。一一条条从从(0,0)点点到到(m,n)点点的的非非降降路路径径与与重重集集m*x,n*y的的一一个个全全排排列列一一一一对对应应，故故所所求非降路径数为求非降路径数为(m+n)!/(m!n!)=C(m+n,m)。另另外外，垂垂直直方方向向需需要要走走n步步，相相当当于于在在X轴轴0,1,m共共m+1个个端端点点处处重重复复的的选选择择n个个位位置置向向上上走走，与与一一条条从从(0,0)点点到到(m,n)点点的的非非降降路路径径一一一一对对应应，故故所所求非降路径数为求非降路径数为F(m+1,n)=C(m+n,n)。Y (m-1,n)(m,n)(m,n-1)(0,0)X 多重集多重集S=*a1,*a2,*ak 的的r组合数组合数F(k,r)=C(k+r-1,r)第28页，此课件共58页哦4.3 非降路径问题例2 由由引引例例，我我们们已已经经知知道道，从从(0,0)点点到到(m,n)点点的的非非降降路路径径数数就就是是组组合合数数C(m+n,m),而而且且从从(0,0)点点到到(m,n)点点的的非非降降路路径径数数等等于于从从(0,0)点点到到(n,m)点的非降路径数点的非降路径数,即即C(m+n,m)=C(m+n,n).另另外外，一一条条从从(0,0)点点到到(m,n)点点的的路路径径可可分分为为两两类类情情况况，一一种种是是从从(0,0)点点到到(m,n-1)点点的的非非降降路路径径，另另一一种种是是从从(0,0)点点到到(m-1,n-1)点点的的非非降路径，根据上述结论，有降路径，根据上述结论，有C(m+n,n)=C(m+n-1,m)+C(m+n-1,m-1)这是这是Pascal公式的另一种形式。公式的另一种形式。例2、非降路径问题从(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？Y (m-1,n)(m,n)(m,n-1)(0,0)X 第29页，此课件共58页哦4.3 非降路径问题例3证证明明：这这是是上上一一小小节节的的组组合合恒恒等等式式。等等式式左左端端表表示示从从(0,0)点点到到(n+1,r)点点的的非非降降路路径径数数，右右端端第第1项项表表示示从从(0,0)点点到到(n,r)点点的的路路径径数数，右右端端第第2项项表表示示从从(0,0)点点到到(n,r-1)点点的的非非降降路路径径数数，右右端端最最后后1项项表表示示从从(0,0)点到点到(n,0)点的非降路径数。点的非降路径数。这这说说明明从从(0,0)点点到到(n+1,r)点点的的非非降降路路径径根根据据是是否否经经过过(n,i)到到(n+1,i)(i=0,1,r)，可分为，可分为r+1类，根据加法法则即可得证。类，根据加法法则即可得证。Y (n,r)(n+1,r)(0,0)(n,0)X 例3、如n,rN，有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)第30页，此课件共58页哦 Y P(0,n)P1(1,n-1)X (0,0)Q(n,0)4.3 非降路径问题例4例4、如nN，有C(n,0)+C(n,1)+C(n,n)=2n组组合合含含义义：这这是是推推论论4.1.3。等等式式左左端端第第1项项表表示示从从(0,0)点点到到P(0,n)点点的的非非降降路路径径数数，第第2项项表表示示从从(0,0)点点到到P1(1,n-1)点点的的非非降降路路径径数数，左左端端最后最后1项表示从项表示从(0,0)点到点到Q(n,0)点的非降路径数。点的非降路径数。这这说说明明从从(0,0)点点到到PQ上上各各格格子子点点的的非非降降路路径径总总和和为为2n。也也说说明明2n个个人人从从(0,0)点点出出发发，每每到到一一个个十十字字路路口口便便分分成成两两组组，直直至至到到达达PQ线线为为止止，能能保保证每个人所走的非降路径不同。证每个人所走的非降路径不同。第31页，此课件共58页哦4.3 非降路径问题例5例5、Vandermonde恒等式如n,mN,rmin(m,n)，有C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0)证证明明：等等式式左左端端表表示示从从(0,0)点点到到(m+n-r,r)点点的的非非降降路路径径数数。从从(0,0)点点到到(m+n-r,r)点点的的每每一一条条路路径径均均穿穿过过PQ线线上上的的格格子子点点(m-l,l),l=0,1,r，从从(0,0)点点到到(m-l,l)点点的的非非降降路路径径数数为为C(m,l)，再再从从(m-l,l)点点到到(m+n-r,r)点点的的非非降降路路径径数数为为C(n,r-l)，由由乘乘法法法法则则，从从(0,0)点点出出发发经经过过(m-l,l)点点到到(m+n-r,r)点的非降路径数为点的非降路径数为C(m,l)C(n,r-l)，再由加法法则，即可得证。，再由加法法则，即可得证。Y P(m-r,r)(m+n-r,r)(0,0)Q(m,0)X (m-l,l)第32页，此课件共58页哦4.3 非降路径问题例6-1例6、求从(0,0)点到(n,n)点的除端点外不接触直线y=x的非降路径数？解解：先先考考虑虑对对角角线线下下方方的的路路径径.这这种种路路径径都都是是从从(0,0)点点出出发发经经过过(1,0)点点及及(n,n-1)点点到到达达(n,n)的的.我我们们可可以以把把它它看看作作是是从从(1,0)点点出出发发到到达达(n,n-1)点点的不接触对角线的非降路径的不接触对角线的非降路径.从从(1,0)点点到到达达(n,n-1)点点的的所所有有的的非非降降路路径径数数是是C(2n-2,n-1),对对其其中中的的任任意意一一条条接接触触对对角角线线的的路路径径，我我们们可可以以把把它它从从最最后后离离开开对对角角线线的的点点（如如A点点）到到(1,0)点点之之间间的的部部分分关关于于对对角角线线作作一一个个反反射射，就就得得到到一一条条从从(0,1)点点出发经过出发经过A点到达点到达(n,n-1)点的非降路径点的非降路径.Y (n,n-1)(0,1)(0,0)(1,0)Q(n,0)X (n,n)A第33页，此课件共58页哦4.3 非降路径问题例6-2 反反之之，任任何何一一条条从从(0,1)点点出出发发，穿穿过过对对角角线线而而到到达达(n,n-1)点点的的非非降降路路径径，也也可可以以通通过过这这样样的的反反射射对对应应到到一一条条从从(1,0)点点出出发发接接触触到到对对角角线线而而到到达达(n,n-1)点点的的非非降降路路径径.从从(0,1)点点到到达达(n,n-1)点点的的非非降降路路径径数数是是C(2n-2,n)，从从而而在在对对角角线线下下方方的的路路径径数数是是C(2n-2,n-1)-C(2n-2,n).由对称性可知，所求的路径数是由对称性可知，所求的路径数是 2 C(2n-2,n-1)-C(2n-2,n)=2C(2n-2,n-1)/n =C(2n,n)/(2n-1).例6、求从(0,0)点到(n,n)点的除端点外不接触直线y=x的非降路径数？第34页，此课件共58页哦例6、求从(0,0)点到(n,n)点的除端点外不穿过直线y=x的非降路径数？解：采用分类处理的方法。解：采用分类处理的方法。将将所所有有从从(0,0)点点到到(n,n)的的非非降降路路径径分分成成两两类类：穿穿过过对对角角线线的的与与不不穿穿过过对对角角线线的的。只只要要求求出出穿穿过过对对角角线线的的路路径径数数N1，那那么么从从总总数数中中减减去去N1就就得得到到所求的路径条数。所求的路径条数。任任何何一一条条从从(0,0)点点到到(n,n)的的穿穿过过对对角角线线的的路路径径一一定定要要接接触触直直线线y=x+1,有有可可能能接接触触多多次次，但但最最后后离离开开这这条条直直线线上上的的一一点点P，沿沿直直线线y=x+1下下方方的的一一条条非非降降路路径径到到达达(n,n)点点。把把这这条条路路径径的的前前半半段段，即即(0,0)点点到到P点点的的部部分分，以以直直线线y=x+1为为轴轴进进行行翻翻转转，生生成成一一段段新新的的从从(-1,1)点点到到P点点的的部部分分非非降降路路径径。用用这这段段新新路路径径替替换换原原来来路路径径的的前前半半段段，就就得得到到一一条条从从(-1,1)点点到到(n,n)点点非非降降路路径径.而而这这种种路路径径与与从从中中间间穿穿过过对对角角线线的的非非降降路路径径之之间间是是一一一一对对应应的。因此，从点的。因此，从点(0,0)点到点到(n,n)的穿过对角线的非降路径数的穿过对角线的非降路径数N1=C(2n,n-1)。第35页，此课件共58页哦 从点从点(0,0)点到点到(n,n)的非降路径总数为的非降路径总数为C(2n,n)条，从而得到不穿条，从而得到不穿过对角线的非降路径数是过对角线的非降路径数是N=C(2n,n)-C(2n,n-1)=例6、求从(0,0)点到(n,n)点的除端点外不穿过直线y=x的非降路径数？第36页，此课件共58页哦4.3 非降路径问题例7-1例7、求集合1,2,n上的单调递增函数的个数.解解：任任给给集集合合1,2,n上上的的一一个个单单调调递递增增函函数数，我我们们可可以以作作一一条条对对应应的的折折线线.以以横横坐坐标标代代表表x,纵纵坐坐标标代代表表f(x),在在图图中中可可以以得得到到n个个格格点点：(1,f(1),(2,f(x),(n,f(n).从从(1,1)点点出出发发向向上上作作连连线线到到(1,f(1)点点.如如果果f(2)=f(1),则则继继续续向向右右连连线线到到(2,f(2);如如果果f(2)f(1),则则由由(1,f(1)点点向向右右经经过过(2,f(1)再再向向上上连连线线到到(2,f(2)点点.按按照照这这种种方方法法一一直直将将折折线线连连到到(n,f(n)点点.第37页，此课件共58页哦4.3 非降路径问题例7-2例7、求集合1,2,n上的单调递增函数的个数.解解：若若f(n)=n,就就将将折折线线向向右右连连到到(n+1,n)点点，若若f(n)n,则则向向右右经经(n+1,f(n)点点再再向向上上到到(n+1,n)点点。这这样样就就得得到到一一条条从从(1,1)点到点到(n+1,n)点的非降路径。点的非降路径。不不难难看看出出，所所求求的的单单调调递递增增函函数数与与这这种种非非降降路路径径之之间间存存在在着着一一一一对对应应，因因此此集集合合1,2,n上上的的单单调调函函数数有有C(2n-1,n)个个.第38页，此课件共58页哦4.3 非降路径问题例8-1例8、从(0,0)点到(m,n)点(mn)的，要求中间经过的每一个格子点(a,b)恒满足ab关系，问有多少条路径？解解：从从(0,0)点点到到(m,n)点点的的路路径径数数为为C(m+n,m)，但但需需要要排排除除碰碰到到或或穿穿过过y=x格格子子点点的的路路径径数数，即即去去掉掉ab的的情情况况。第第一一步步必必须须从从(0,0)点点到到(1,0)点点，因因此此问问题题等等价价于于求求从从(1,0)点点到到(m,n)点点的的路路径径数数。因因为为mn，故故从从(0,1)点点到到(m,n)点点的的路路径径必必然然穿穿过过y=x上上的的格格子子点点。下下面面建建立立从从(0,1)点点到到(m,n)点点的的每每一一条条路路径径，与与从从(1,0)点点到到(m,n)点点但但经经过过y=x上上的的格格子子点点的路径时一一对应的。的路径时一一对应的。Y (m,n)(0,1)(0,0)(1,0)Q(m,0)X 第39页，此课件共58页哦4.3 非降路径问题例8-2 Y (m,n)(0,1)(0,0)(1,0)Q(m,0)X 若若从从(0,1)点点到到(m,n)点点的的路路径径与与y=x的的交交点点从从左左往往右右数数最最后后一一个个是是P，作作从从(1,0)点点到到P点点关关于于y=x的的与与上上述述(0,1)点点到到P点点的的路路径径对对称称的的一一条条路路径径，于于是是从从(0,1)点点到到(m,n)点点的的一一条条路路径径，就就有有一一条条从从(1,0)点点到到(m,n)点点但但经经过过y=x上上的的格格子子点点的的路路径径与与之之对对应应。反反之之，一一条条从从(1,0)点点到到(m,n)点点但但经经过过y=x上上的的格格子子点点的的路路径径，必必存存在在一一条条从从(0,1)点点到到(m,n)点点的的一一条条路路径径与之对应。与之对应。故所求的路径数为故所求的路径数为C(m+n-1,n)-C(m+n-1,n-1)=(m-n)(m+n-1)!/(m!n!)例8、从(0,0)点到(m,n)点(mn)的，要求中间经过的每一个格子点(a,b)恒满足ab关系，问有多少条路径？第40页，此课件共58页哦4.4牛顿二项式定理广义广义二项式系数二项式系数 为：为：牛顿二项式定理：牛顿二项式定理：牛顿牛顿牛顿牛顿第41页，此课件共58页哦4.4 牛顿二项式定理牛顿二项式定理 恒等式恒等式(4.15)：恒等式恒等式(4.16)：恒等式恒等式(4.17)：第42页，此课件共58页哦4.4 牛顿二项式定理牛顿二项式定理 恒等式恒等式(4.18)：证证明明：注注意意，这这个个恒恒等等式式与与前前面面的的有有一一个个很很不不一一样样的的地地方方，就就是是C(+j,j),C(+k+1,k)是是广广义义的的二二项项式式系系数数。根根据据广广义义的的二二项项式式系系数数的的定定义义，Pascal公公式式C(,k)=C(-1,k)+C(-1,k-1)对对实实数数和和整整数数k同同样样成成立立。与与恒恒等等式式1类类似似，反复使用反复使用Pascal公式即可得证。公式即可得证。第43页，此课件共58页哦4.4 牛顿二项式定理推论1推论推论4.2.1：推论推论4.2.2：证明：证明：(4.19)第44页，此课件共58页哦(4.19)(4.20)(4.21)(4.22)4.4牛顿二项式定理推论2推论推论1.10.1：推论推论1.10.2：推论推论1.10.3：推论推论1.10.4：推论推论1.10.5：证明：证明：当当=1/2时，时，C(,0)=1，而对于，而对于k0，有，有将上式代入推论将上式代入推论4.2.1即可得证。即可得证。第45页，此课件共58页哦4.4 牛顿二项式定理推论3推论推论4.2.1：推论推论4.2.2：推论推论4.2.3：推论推论4.2.4：推论推论4.2.5：推论推论4.2.6：(4.19)(4.20)(4.21)(4.22)第46页，此课件共58页哦4.5多项式定理定理4.3（多项式定理）设n是正整数，则对一切实数x1,x2,xt有第47页，此课件共58页哦多项式定理证明 对于对于n个因子中的每一个，选取个因子中的每一个，选取 m 个数个数x1,x2,xt中的一个并中的一个并形成乘积。形成乘积。用这种方法得到的结果共有用这种方法得到的结果共有t n项，并且每一项都可以写成项，并且每一项都可以写成 的形式，其中的形式，其中n1,n2,，nt是非负数，且其和为是非负数，且其和为n。通过选择通过选择n个因子中的个因子中的n1个为个为x1，剩下的，剩下的n-n1个因子中的个因子中的n2个个为为x2,剩下的剩下的n-n1-nt-1个因子中的个因子中的nt个为个为xt,得到得到 项。项。由乘法原理得到该项出现的次数为由乘法原理得到该项出现的次数为第48页，此课件共58页哦4.5多项式定理有多少个不同的乘积项?乘积项的系数和是多少？推论1的展开式在合并同类项以后不同的项数是证明：的展开式中每一项都可以写成 的形式，其中n1+n2+nt=n.每一项对应于该方程的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数推论2，其中求和是对方程的一切非负整数解求和.证明：在多项式定理中令 即可.第49页，此课件共58页哦4.5多项式定理多项式系数 的组合意义：1.它是多项式 中 项的系数；2.它是多重集合S=n1a1+n2a2+ntat的排列数；3.如果我们把n个不同的球放到t个不同的盒