组合数学(第四章二项式系数).ppt

目目录录（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有禁区的排列有禁区的排列问题问题本章小结 习题目目录录1.目目录录（2）第六章第六章 递递推关系推关系6.1 Fibonacci数列6.2 常系数线性齐次递推关系的求解6.3 常系数线性非齐次递推关系的求解6.4 用迭代和归纳法求解递推关系本章小结 习题第七章第七章 生成函数生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5 Catalan数和Stiring数本章小结 习题第八章第八章 Polya定理定理8.1置换群中的共轭类与轨道8.2 Polya定理的特殊形式及其应用本章小结 习题*课课程程总结总结2.教学目教学目标标：1掌握二掌握二项项式定理、式定理、证证明方法及其明方法及其应应用；用；2掌握推广的二掌握推广的二项项式定理；式定理；3掌握多掌握多项项式定理、式定理、证证明方法及其明方法及其应应用；用；4理解一些理解一些组组合恒等式的意合恒等式的意义义及其及其证证明方法；明方法；5非降路径非降路径问题问题的的组组合意合意义义及及应应用；用；重点：重点：二二项项式定理、多式定理、多项项式定理式定理证证明方法及其明方法及其应应用；用；难难点：点：一些一些组组合恒等式合恒等式证证明方法，非降路径明方法，非降路径问题组问题组合意合意义义及及应应用。用。3.4.1二项式定理1.二项式系数组合数C(n,k)或者 也叫二项式系数.2.组合数的定义()nk4.3.组合数的一些恒等式（1）对称式（2）抽取式（3）Pascal公式(4.1)(4.2)(4.3)5.抽取式（抽取式（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人做班人做班人做班人做班长长长长，问问问问有有有有多少种方法？多少种方法？多少种方法？多少种方法？6.证证明明：因因为为(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)又称又称二二项项式系数式系数。7.推推论论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 8.推推论论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 元集合的偶子集个数与元集合的偶子集个数与元集合的偶子集个数与元集合的偶子集个数与奇子集个数相等奇子集个数相等奇子集个数相等奇子集个数相等 9.恒等式恒等式(4.6)：证证明明：考考虑虑盒盒子子1中中有有n个个有有区区别别的的球球，从从中中取取一一个个球球放放入入盒盒子子2中中，再再取取任任意意多多个个球球放放入入盒盒子子3中中。等等式式左左端端表表示示先先从从盒盒子子1中中取取k(k=1,2,n)个个球球，再再从从中中取取一一个个放放入入盒盒子子2中中，剩剩下下的的k-1个个球球放放入入盒盒子子3中中。等等式式右右端端表表示示先先从从盒盒子子1中中取取一一个个放放入入盒盒子子2中中，剩剩下下的的n-1个个球球是是否否放放入入盒盒子子3中中均均有有两两种种可可能能。显显然然两两种种取取法法结结果是一果是一样样的。得的。得证证。或通或通过过计计算算证证明：明：10.恒等式恒等式(4.6)：证证明：明：证证法法3由二由二项项式定理有式定理有对对上式两上式两边边微商得微商得然后令然后令x=1得得注：如令注：如令x=-1，可，可证证明下面明下面恒等式恒等式。11.类类（4.6）恒等式）恒等式(习题习题4.7)：证证明：明：将等式两将等式两边对边对x微分得微分得在上式中，令在上式中，令x=-1得得即即得得证证。12.恒等式恒等式(习题习题4.8积积分方法分方法)：证证明：明：将等式两将等式两边对边对x从从0到到1积积分得分得即即得得证证。13.类类恒等式恒等式(4.7)：恒等式恒等式(4.7)：证证明：明：将等式两将等式两边对边对x微分得微分得将等式两将等式两边边同乘以同乘以x后再后再对对x微分得微分得在上式中，令在上式中，令x=1得得得得证证。注：如令注：如令x=-1，即可，即可证证明另一明另一恒等式恒等式(4.7)。14.恒等式恒等式(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)种。得种。得证证。或通或通过计过计算算证证明：明：15.恒等式恒等式(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)证证明明：设设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的系数即可得的系数即可得证证。16.恒等式恒等式(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)：17.恒等式恒等式(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也成立。由也成立。由归纳归纳原理，得原理，得证证。18.恒等式恒等式(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)19.恒等式恒等式(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)20.数学数学归纳归纳法法二二项项式系数公式，特式系数公式，特别别是是Pascal公式公式比比较级较级数展开式中的系数（二数展开式中的系数（二项项式定理或母函数法）式定理或母函数法）积积分微分法分微分法组组合分析法合分析法21.例例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).22.在式（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).其中每相邻两项之差就是二阶等差级数的项，把这个 等式叫做三阶等差级数的求和公式.23.例例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.24.例例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)25.例4.4证明：从n名女同学和n名男同学中，选出n名同学组成一个社团，其中一人担任社团主席，且必须由女同学担任，问有多少种选法？26.引引例例、非非降降路路径径问问题题从从(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)。多重集多重集S=*a1,*a2,*ak的的r组组合数合数F(k,r)=C(k+r-1,r)27.由由引引例例，我我们们已已经经知知道道，从从(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)点点，有多少条路径？有多少条路径？28.证证明明：这这是是上上一一小小节节的的组组合合恒恒等等式式。等等式式左左端端表表示示从从(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类类，根据加法法，根据加法法则则即可得即可得证证。例例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)29.例例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线为线为止，能保止，能保证证每个人所走的非降路径不同。每个人所走的非降路径不同。30.例例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)，再由加法法，再由加法法则则，即可得，即可得证证。(m-l,l)31.例例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)点的非降路径点的非降路径.(n,n)A32.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).由由对对称性可知，所求的路径数是称性可知，所求的路径数是2C(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的非降路径数？的非降路径数？33.例例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)。34.从点从点(0,0)点到点到(n,n)的非降路径的非降路径总总数数为为C(2n,n)条，从而得到条，从而得到不穿不穿过对过对角角线线的非降路径数是的非降路径数是N=C(2n,n)-C(2n,n-1)=例例6、求从求从(0,0)点到点到(n,n)点的除端点外点的除端点外不穿不穿过过直直线线y=x的非降路径数？的非降路径数？35.例例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)点点.36.例例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)个个.37.例例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上的格子点的路径上的格子点的路径时时一一一一对应对应的。的。38.若若从从(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关系，关系，问问有多少条路径有多少条路径？39.牛牛牛牛顿顿顿顿40.恒等式恒等式(4.15)：恒等式恒等式(4.16)：恒等式恒等式(4.17)：41.恒等式恒等式(4.18)：证证明明：注注意意，这这个个恒恒等等式式与与前前面面的的有有一一个个很很不不一一样样的的地地方方，就就是是C(+j,j),C(+k+1,k)是是广广义义的的二二项项式式系系数数。根根据据广广义义的的二二项项式式系系数数的的定定义义，Pascal公公式式C(,k)=C(-1,k)+C(-1,k-1)对对实实数数和和整整数数k同同样样成立。与恒等式成立。与恒等式1类类似，反复使用似，反复使用Pascal公式即可得公式即可得证证。42.推推论论4.2.1：推推论论4.2.2：证证明：明：(4.19)43.(4.19)(4.20)(4.21)(4.22)推推论论1.10.1：推推论论1.10.2：推推论论1.10.3：推推论论1.10.4：推推论论1.10.5：证证明：明：当当=1/2时时，C(,0)=1，而，而对对于于k0，有，有将上式代入推将上式代入推论论4.2.1即可得即可得证证。44.推推论论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)45.4.5多项式定理定理4.3（多项式定理）设n是正整数，则对一切实数x1,x2,xt有46.多项式定理证明 对对于于n个因子中的每一个，个因子中的每一个，选选取取m 个数个数x1,x2,xt中的一中的一个并形成乘个并形成乘积积。用用这这种方法得到的种方法得到的结结果共有果共有t n项项，并且每一，并且每一项项都可以写都可以写成成的形式，其中的形式，其中n1,n2,，nt是非是非负负数，且数，且其和其和为为n。通通过选择过选择n个因子中的个因子中的n1个个为为x1，剩下的，剩下的n-n1个因子中的个因子中的n2个个为为x2,剩下的剩下的n-n1-nt-1个因子中的个因子中的nt个个为为xt,得到得到项项。由乘法原理得到由乘法原理得到该项该项出出现现的次数的次数为为47.4.5多项式定理有多少个不同的乘积项?乘积项的系数和是多少？推论1 的展开式在合并同类项以后不同的项数是证明：的展开式中每一项都可以写成 的形式，其中n1+n2+nt=n.每一项对应于该方程的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数推论2 ，其中求和是对方程的一切非负整数解求和.证明：在多项式定理中令 即可.48.4.5多项式定理多项式系数 的组合意义：1.它是多项式 中 项的系数；2.它是多重集合S S=n1a1+n2a2+ntat的排列数；3.如果我们把n个不同的球放到t个不同的盒子里并且使得第一个盒子里有n1个球，第二个盒子里有n2个球，第t个盒子里有nt个球，那么放球的方案数是 .49.例4.6 在(2x-3y+5z)6 的展开式中，x3yz2项的系数是多少？解：4.5多多项项式定理式定理50.4.5多项式定理例4.7 试试试试用用用用组组组组合学合学合学合学论证论证论证论证法法法法证证证证明恒等式明恒等式明恒等式明恒等式证明：左边是把n个不同的球放到t个不同的盒子里并且使得第一个盒子里有n1个球，第二个盒子里有n2个球，第t个盒子里有nt个球的方案数.任取一个球n1，然后把放球的方法进行分类：a1放到第一个盒子的放法数是 ；a1放到第二个盒子的放法数是 ；a1放到t第二个盒子的放法数是 .由加法法则等式得证.51.4.6基本组合计数的应用例1某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？52.4.6基本组合计数的应用解:每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有 =35把不同的钥匙。任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持 20把不同的钥匙。为加深理解，举一个较简单的例子：人中人到场，所求如上。共有 =6把不同的钥匙。每人有 =3把钥匙。53.钥钥匙匙123456人人ABCD54.4.6基本组合计数的应用例例2脱氧核糖核酸(DNA)的分子由A(腺嘌呤),G(鸟嘌呤),C(胞嘧啶)和T(胸腺嘧啶)4种碱基核糖核苷酸，以不同数目和种类排列成两条多核苷酸单链，这两条单链之间通过氢键把配对的碱基连接起来，形成双螺旋结构。连接过程总是A和T配对，G和C配对。显然长度为n的核苷酸链共有4n 种不同方式。生物遗传信息是由DNA分子中4个碱基核苷酸象电报密码似的以不同的排列顺序记录下来，它载着人类的全部基因或全部遗传信息。所谓基因就是DNA上一小段,平均长度为900-1500个碱基对。人的DNA约有3109 碱基对。核糖核酸(RNA)也是一种遗传物质，它是由A,G,C,U(尿嘧啶)4种碱基核苷酸排列而成的多核苷酸单链。55.4.6基本组合计数的应用 通过基因将它的遗传信息传递给RNA,然后再传给蛋白质来表现其功能。(1)蛋白质分子中有20种氨基酸，在RNA 中以一定顺序相连的3个核苷酸决定1种氨基酸，三联体遗传密码有43=64个排列方式。它保证了20种氨基酸密码的需要。(2)例如RNA链：CCGGUCCGAAAG 酶将它分解成为G片断(即利用G将RNA分解)。CCG,G,UCCG,AAAG.56.4.6基本组合计数的应用 显然有4!