排列组合公式讲稿.ppt

《排列组合公式讲稿.ppt》由会员分享，可在线阅读，更多相关《排列组合公式讲稿.ppt（122页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于排列组合公式第一页，讲稿共一百二十二页哦排列与组合 从五个候选人中选出选出两个代表 把5本不同的书安排安排在书架上 从五个候选人中选出两个代表时，有10种可能的结果。把5本不同的书安排在书架上有120种方法 选出-组合；安排-排列第二页，讲稿共一百二十二页哦一、排列排列组合组合公式 排列问题：从某个集合中有序有序地选取若干个元素的问题 组合问题：从某个集合中无序无序地选取若干个元素的问题 注意：可以重复 不能重复第三页，讲稿共一百二十二页哦排列 无重排列 可重排列 从1,2,9中选取数字构成四位数，使得每位数字都不同，有多少个？从1,2,9中选取数字构成四位数，使得不同数位上的数字可以相同

2、，有多少个？第四页，讲稿共一百二十二页哦1、无重排列 n个元素的r-无重排列无重排列数：排列的长度r 计算（一般情形）：乘法原理 r=n时,n个元素的全排列 r=0时 rn时第五页，讲稿共一百二十二页哦2、可重排列 n个元素的r-可重排列可重排列数 计算（乘法原理）第六页，讲稿共一百二十二页哦例题 在1和10,000,000,000之间的一百亿个数中，有多少个数含有数码1？又有多少个数不含数码1？不含1:910 含1:1010-910+1第七页，讲稿共一百二十二页哦例题 一个二元序列是由一些0和1所组成的序列。n码二元序列指该序列中数码的个数为n。试问，含有偶数个0的n码二元序列的个数是多少？

3、2n-1 考虑n码四元序列，即以0,1,2和3为其数码的序列。则含0和1的总个数为偶数的序列有多少个？4n/2第八页，讲稿共一百二十二页哦例题 求n码四元序列中含有偶数个0的个数？第九页，讲稿共一百二十二页哦放球问题 设nr，把r个不同的球放入n个不同的盒子，这里每一盒最多只能装一物，允许空盒。放球的方法数为多少？第一个球有n种选法，第二个球有n-1种，等等，乘法原理 P(n,r)第十页，讲稿共一百二十二页哦放球问题 把r个不同的球放入n个不同的盒子，一个盒中可以放多个球，也允许空盒。放球的方法数为多少？第一个球有n种选法，第二个球有n种，等等，乘法原理 nr 这里n和r的大小没有限制第十一页

4、，讲稿共一百二十二页哦放球问题 把r个不同的球放入n个不同的盒子，一个盒中可以放多个球，也允许空盒。考虑每个盒子中球的次序。放球的方法数为多少？把这样一个方法设想为r个不同的球和n-1个相同的盒间板的一个有序安排。C(r+n-1,n-1)=C(r+n-1,r)=F(n,r)另解：有n种方法放第一个球，第一个球放入一个盒后，可以把这个球当成是一个添加的隔板，它把该盒分成两个盒，因此放第二个球有n+1种方法。等等第十二页，讲稿共一百二十二页哦放球问题：例题 今欲在五根旗杆上悬挂七面不同的旗子，全部旗都得展示出来，但并非所有的旗杆都得使用，问有多少种安排的方法？七部汽车通过五间收费亭的方式数？第十三

5、页，讲稿共一百二十二页哦组合 无重组合 可重组合 从a,b,c中选取2个不同元素，选法数是多少？从a,b,c中选取5个元素，元素可以相同，选法数是多少？第十四页，讲稿共一百二十二页哦3、无重组合（Combination）n个元素的r-无重组合无重组合数 无重组合数与无重排列数的关系 计算 r=0时 r=n时 rn时第十五页，讲稿共一百二十二页哦组合数的推广rnC)!(!rnrn!)1()1(rrnnnrnrnC)!(!rnrn!)1()1(rrnnnrnCZrR,0,00,10,!)1()1(rrrrrr第十六页，讲稿共一百二十二页哦几个记号)1()1(nxxxxn下阶乘函数上阶乘函数)1()

6、1(nxxxxn)1()1(nn!)1()1(!nnnnCnn第十七页，讲稿共一百二十二页哦计算32132102153第十八页，讲稿共一百二十二页哦例题 如果一个凸十边形无三条对角线在这个十边形的内部交于一点，问这些对角线被它们的交点分成多少条线段？第十九页，讲稿共一百二十二页哦多边形第二十页，讲稿共一百二十二页哦例题 对角线的条数为C(10,2)-10=45-10=35任选两条对角线，可能相交在多边形内部，可能交点为多边形的顶点，可能无交点（交点在多边形外）任选四个顶点，对应一个交点，每个对角线分成两段 每个对角线是一段 35+C(10,4)2=455第二十一页，讲稿共一百二十二页哦例题C(

7、5,2)-5+C(5,4)2=15C(10,2)-10+C(10,4)2=455C(4,2)-4+C(4,4)2=4第二十二页，讲稿共一百二十二页哦4、可重组合 n个元素的r-可重组合可重组合 例子 计算 一一对应的思想第二十三页，讲稿共一百二十二页哦推论 方程x1+x2+xn=r 的非负整数解的个数。nr时，此方程的正整数解的个数 n元集合的r-可重组合数，要求每个元素至少出现一次。正整数r的n-长有序分拆的个数 求x1+x2+x3+x4=20的整数解的数目，其中x1 3,x2 1,x3 0,x4 5。第二十四页，讲稿共一百二十二页哦例题 从为数众多的一分币、二分币、一角币和二角币中，可以有

8、多少种方法选出六枚来？F(4,6)=C(4+6-1,6)=C(9,6)=84第二十五页，讲稿共一百二十二页哦例题 某糕点厂将8种糕点装盒，若每盒有一打糕点，求市场上能买到多少种该厂出品的盒装糕点？某糕点厂将8种糕点装盒，若每盒有一打糕点，且要求每种糕点至少放一块。求市场上能买到多少种该厂出品的盒装糕点？第二十六页，讲稿共一百二十二页哦例题 摇三个不同的骰子的时候，可能的结果的个数是多少？63=216。如果这三个骰子是没有区别的，则可能结果的个数是多少？从1,2,3,4,5,6这六个数中允许重复地选出三个数。F(6,3)=C(6+3-1,3)=56 将r个骰子掷一次，总共可以掷出多少种不同结果？

9、F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5)第二十七页，讲稿共一百二十二页哦有约束条件的排列：引例 用两面红旗、三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？第二十八页，讲稿共一百二十二页哦5、有约束条件的排列 设有k个元素a1，a2，ak，由它们组成一个n-长的排列，其中对1ik，ai出现的次数为ni，n1+n2+nk=n，求排列的总数。求解方法1 求解方法2第二十九页，讲稿共一百二十二页哦例题 五条短划和八个点可以安排成多少种不同的方式？如果只用这十三个短划和点中的七个，则有多少种不同的方式？!8!5!13!7!0!7+!6!1!7+!5!2!7+!4

10、!3!7+!3!4!7+!2!5!7第三十页，讲稿共一百二十二页哦例题 证明对任意正整数k,(k!)!能被(k!)(k-1)!整除。提示：k!个物体，其中k个物体属于第一类，k个物体属于第二类，k个物体属于第(k-1)!类。第三十一页，讲稿共一百二十二页哦推论 多项式(x1+x2+xr)n的展开式中有 项，其中项 的系数为 。rnrnnxxx21216321)532(xxx23231xxxnrxxx)(21rrrnrnnnnnnnnnrxxxnnnn21212121,21为非负整数第三十二页，讲稿共一百二十二页哦例题 数1400有多少个正因数？1400=23 52 7(3+1)(2+1)(1+

11、1)=24第三十三页，讲稿共一百二十二页哦放球问题 设nr，把r个相同的球放入n个不同的盒子使得每盒至多装一个球，方法数？选盒子即可 C(n,r)第三十四页，讲稿共一百二十二页哦放球问题 把r个相同的球放入n个不同的盒子，每盒可以装任意多个球，方法数？放这r个球，等价于从n个盒中选出r个来装这r个球而允许诸盒重复选取。F(n,r)=C(n+r-1,r)另解：把分配这r个球入n个盒子设想为这r个球和n-1个隔板的一个排列。球是相同的，隔板也是相同的。C(n+r-1,r)第三十五页，讲稿共一百二十二页哦放球问题 设r n，把r个相同的球放入n个不同的盒子中，盒子中可以放入任意多个球，但不允许空盒，

12、方法数？现在每个盒中放入一个球，再放剩下的r-n个球 C(r-n)+n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)第三十六页，讲稿共一百二十二页哦放球问题 设r n，把r个相同的球放入n个不同的盒子中，要求每一盒至少包含q个球，方法数？现在每个盒中放入q个球，再放剩下的r-qn个球 C(r-qn)+n-1,r-qn)=C(n-nq+r-1,r-nq)=C(n-nq+r-1,n-1)第三十七页，讲稿共一百二十二页哦放球问题：例题 今有五封不同的信要经由一个讯道传送。又有总共15个空白要插在这些信之间而使得每两封信之间至少有三个空白。有多少种方法安排这些信和空白？信的安排5！对一种信

13、的安排，有4个信件位置，安排15个空白，要求每个信件位置至少有三个空白。5！C(4-4 3+15-1,4-1)=5!C(6,3)第三十八页，讲稿共一百二十二页哦放球问题 有n个球，其中第一种颜色n1个，第二种颜色n2个，第k种颜色nk个。将这n个球放入n个不同的盒中，每一个盒装一个球。问分配方案数？等价于这n个球的排列数。另解：选盒子装每种颜色的球。第三十九页，讲稿共一百二十二页哦放球问题 有r个球，其中第一种颜色n1个，第二种颜色n2个，第k种颜色nk个。将这r个球放入n个不同的盒中，每一个盒装一个球（rn）。问分配方案数？方法一：先选盒子，再分配球。方法二：针对每种颜色的球选盒子。第四十页

14、，讲稿共一百二十二页哦多重集合 通常的“集合”具有无重性。在多重集中，同一个元素可以出现多次。1,2,3是一个集合，而1,1,1,2,2,3不是一个集合，而是一个多重集，简记为31,22,13。计算多重集的势时，出现多次的元素则需要按出现的次数计算。上面多重集的势为6。可重组合与可重排列可以看作是多重集的组合与排列问题。第四十一页，讲稿共一百二十二页哦可重排列与可重组合n个元素a1,a2,an的r-无重组合(排列)可以看做多重集1a1,1 a2,1 an的r-组合(排列)。n个元素a1,a2,an的r-可重组合(排列)可以看做多重集a1,a2,an的r-组合(排列)。有限制的排列问题可以看做多

15、重集n1a1,n2 a2,nk ak的全排列。第四十二页，讲稿共一百二十二页哦分组与分堆 固定分组：无序分组：分堆 不定分组 固定分组与分堆的区别是讲不讲组间的次序，只在各组元素个数相等时有区别固定分组与不定分组的区别是每个组的元素个数是不是确定，只在各组元素个数不等时才有区别。第四十三页，讲稿共一百二十二页哦区分 将12本书平均分给A,B,C,D四个学生，每人三本，有多少种分法？将12本书平均分成四堆有多少种分法？将12本书平均分给A,B,C,D四个学生，使得每人各得三本，有多少种分法？第四十四页，讲稿共一百二十二页哦区分 将12本书分给四个学生，使得A,B各得四本，C,D各得2本，有多少种

16、分法？将12本书分成四堆，有两堆各4本，另外两堆各2本，有多少种分法？将12本书分给A,B,C,D四个学生，使得有两个学生各得4本，有两个学生各得2本，有多少种分法？第四十五页，讲稿共一百二十二页哦区分 将12本书分给四个学生，A得5本，B得4本，C得2本，D得1本，有多少种分法？将12本书分成四堆，其本数分别为5,4,2,1，有多少种分法？将12本书分给A,B,C,D四个学生，使得有1人得5本，有一人得4本，有1人得两本，有1人得1本，有多少种分法？第四十六页，讲稿共一百二十二页哦限距组合：引例 书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这样的选法有多少种？第四十七

17、页，讲稿共一百二十二页哦6、限距组合 设A=1,2,n，它的任一r-无重组合均可以依自然顺序排出a1,a2,ar，其中a1a2 ar。设k是非负整数，用f(k,n,r)表示A的一切满足条件ai+1-aik+1(1ir-1)的r-无重组合数，求f(k,n,r)。求解思想：一一对应 k=0时第四十八页，讲稿共一百二十二页哦例题 书架上有1-24共24卷百科全书，从其中选5卷使得任何两卷都不相继，这样的选法有多少种？第四十九页，讲稿共一百二十二页哦7、圆排列 n个元素的r-无重圆排列数 圆排列与线排列的区别 计算第五十页，讲稿共一百二十二页哦例题例1把20个不同的钉子钉在鼓表面一周，订钉子的方式有

18、种。例2把20个不同的珍珠串成项链，串项链的方式有 种。项链问题项链问题第五十一页，讲稿共一百二十二页哦例 从1到300间取出3个不同的数，使它们的和被3整除，有多少种取法？提示：将1到300这300个整数按照除以3的余数分成3组，考虑选出的3个数属于哪些组。第五十二页，讲稿共一百二十二页哦例 下图中有多少个矩形？第五十三页，讲稿共一百二十二页哦映射的个数n元集X到m元集A的映射的个数将X看作物件的集合，A看作盒子的集合。则一个映射表示把物件放入盒子的一种安排。要求(1)每个物体都要放入某个盒子；(2)一个物体不得放入两个盒子；(3)允许多个物体放入同一盒子；(4)可以剩有空盒子。若将X看作有

19、标号的位置的集合，A看作排在这些位置的字母的组合，则一个映射对应一个长为n的字。则(1)字长必须为n；(2)一个位置只能放一个字母；(3)多个位置可以重复出现同一字母；(4)有些字母有可能不出现。第五十四页，讲稿共一百二十二页哦例题n元集合X到m元集合A的映射的个数？将n个物体放在m个的盒子中的不同放法？n元集合X到m元集合A的单射的个数？把n个物体放入m个盒子，每个盒子至多放一个物体的安排有多少种？3个物体分放到4个不同的盒子中，要求每个盒子至多放一个物体的放法数？第五十五页，讲稿共一百二十二页哦映射 设映射f：1,2,n 1,2,m(nm)(1)若f是严格递增的，则不同的f有多少个？(2)

20、若f是不减的，则不同的f有多少个？第五十六页，讲稿共一百二十二页哦例题1、从A=a,b,c中任取两个不同的字母构成的字共有多少个？2、m元集合的n元子集的个数？3、平面上任三点都不共线的25个点，可形成多少条直线？可形成多少个三角形？第五十七页，讲稿共一百二十二页哦例题用26个英文字母能构成多少个含有3个、4个或5个元音的长为8位的单词？（其中，一个字母出现在单词中的次数不限）第五十八页，讲稿共一百二十二页哦例题从一副52张扑克牌中任取13张得一手牌，在每一手牌中不考虑这13张牌的次序，则总共有多少手不同的牌？把一副52张扑克牌分给4个人，每人得13张，则总共有多少种不同的牌局？第五十九页，讲

21、稿共一百二十二页哦例题用4个a，4个b，2个c和2个d这12个字母能组成多少个具有12个字母的字？用字母a，b，c组成5个字母的字，每个字中a至多出现2次，b至多出现1次，c至多出现3次。这种字的个数是多少？第六十页，讲稿共一百二十二页哦例题 单词mississippi中字母的排列数为？求多重集3a,2b,4c的8排列的个数？第六十一页，讲稿共一百二十二页哦例题求26个英文字母的全排列中，任意两个元音字母都不相邻的方案数？第六十二页，讲稿共一百二十二页哦例题Banach火柴盒问题：某数学家随身携带A,B两盒火柴，要用火柴时就随意从其中一盒中取出一根。假定开始两个火柴盒各放有n根火柴，问在某一次

22、当数学家发现拿出的那一个火柴盒变空时，另一盒中尚剩p(pn)根火柴的概率是多少？第六十三页，讲稿共一百二十二页哦例题10个人排成一排，其中有2个人不愿彼此挨着，求所有不同的排列的数目。10！-29！或 8！A(9,2)=2903040 10个人围一圆桌入座，其中有2个人不愿彼此挨着就座，求所有不同的圆排列的数目。9!-28!或7！A(8,2)=282240第六十四页，讲稿共一百二十二页哦例题安排10个男生和5个女生排成一排，使任意2个女生都不相邻的排法有多少种？A(10,10)A(11,5)安排10个男生和5个女生围成圆圈入座，使任意2个女生都不相邻的坐法有多少种？第六十五页，讲稿共一百二十二

23、页哦例 从给定的6种不同的颜色中选不同的颜色将一个正方体的六个面染色，要求每个面染一种颜色，具有相同棱的面染成不同的颜色，则不同的染色方案有多少种？分析：一种颜色？两种颜色？三种颜色？相对的面染成相同的颜色,只有一种方式C(6,3)第六十六页，讲稿共一百二十二页哦四种颜色：五种颜色：六种颜色：C(6,4)C(4,2)C(6,5)C(5,1)3！/2C(6,6)C(5,1)3！第六十七页，讲稿共一百二十二页哦例 试求由1,3,5,7组成的数字不重复出现的整数的总和。分析：一位数1，3，5，7两位数个(十)位数为1的两位数的个数三位数个(十、百)位数为1的三位数的个数四位数个(十、百、千)位数为1

24、的四位数的个数第六十八页，讲稿共一百二十二页哦例 假定把全部的5码数印刷在纸条上，而一张纸条上印一个数。所谓5码数是由0,1,2,9这十个数字中的5个数字组成的数，开头的一个或者几个可以为0，例如00102,00000都是5码数，显然有100000个这样的5码数。然而由于数字0,1,6,8,9被倒过来就成了0,1,9,8,6。而一张纸条可以从上下两个方向正看和倒看，所以有些5码数可以共用一张纸条，如89166与99168。于是我们的问题是要用多少个不同的纸条才能做出这些5码数？第六十九页，讲稿共一百二十二页哦0 1 2 3 4 5 6 7 8 90 101 倒过来 8 8 6 9 9 6第七十

25、页，讲稿共一百二十二页哦1357813578倒过来 89166681898916668189不是5码数仍是5码数仍是5码数但不是自己而且是自己第七十一页，讲稿共一百二十二页哦5码数共105个倒过来仍是5码数的有55个倒过来不再是5码数的有10555个一个数一张纸条倒过来是自己的有3x52个倒过来不是自己的有553x52个一个数一张纸条两个数共用一张纸条第七十二页，讲稿共一百二十二页哦所以纸条的个数为(10555)+3x52+(553x52)/2105(553x52)/2=98475第七十三页，讲稿共一百二十二页哦例 甲、乙两方各有7名队员，按事先排好的顺序出场参加围棋擂台赛。双方先由1号参加比

26、赛，负者被淘汰，胜者再与对方2号队员比赛，直到有一方全部被淘汰，另一方获得胜利，形成一种比赛过程。那么所有可能出现的比赛过程的种数为多少？第七十四页，讲稿共一百二十二页哦甲乙1A1B2A2B3A3B4A4B5A5B6A6B7A7B箭头指向谁，表示谁负甲方赢：甲方赢：5A7A5A5A5A5A7A这是1234567,A A A A A A A的一个7-可重组合第七十五页，讲稿共一百二十二页哦5A7A5A5A5A5A7A甲乙1A1B2A2B3A3B4A4B5A5B6A6B7A7B第七十六页，讲稿共一百二十二页哦甲乙1A1B2A2B3A3B4A4B5A5B6A6B7A7B6A6A6A6A6A6A7A第

27、七十七页，讲稿共一百二十二页哦1A甲乙1A1B2A2B3A3B4A4B5A5B6A6B7A7B1A1A1A1A1A1A第七十八页，讲稿共一百二十二页哦例 某车站有6个进站口，今有9人进站，有多少种不同的进站方法？进站口人2ABCDEF13456789任务：给每个人选择进站口，选择进站的次序？第七十九页，讲稿共一百二十二页哦安排 ：ABCDEF16种方式1安排 ：27种方式222安排 ：38种方式3333安排 ：914种方式进站方式种数为6 7 814 145!=！方法一：第八十页，讲稿共一百二十二页哦123456取213456789的一个全排列，和5个213456789对应的进站方式为：913

28、456872方法二：第八十一页，讲稿共一百二十二页哦ABCDEF进站方式为：913456872213456789对应的排列为：第八十二页，讲稿共一百二十二页哦进站方式种数为141!1!1!5!！145!=！213456789的排列5个或14个位置取5个放方框(不讲顺序)，剩下的放人(将顺序)5149!C 149!59！14=5！第八十三页，讲稿共一百二十二页哦方法三：先选车站，A B C D EF 的9-可重组合AAACCDEEF再排人，213456789的排列213456789对应的进站方式为：ABCDEF913456872第八十四页，讲稿共一百二十二页哦对比 例 某车站有6个进站口，今有9

29、人进站，有多少种不同的进站方法？今欲在六根旗杆上悬挂九面不同的旗子，全部旗都得展示出来，但并非所有的旗杆都得使用，问有多少种安排的方法？第八十五页，讲稿共一百二十二页哦例 8个人 两两配对分成4组有多少种方式？128,a aa方法一 给每个人配对方法二 一对一对地选，注意会重复推广：2n个人两两配对分成n组有多少种方式？第八十六页，讲稿共一百二十二页哦非降路径问题从点 到达点 的非降路径非降路径(0,0)(2,3)第八十七页，讲稿共一百二十二页哦非降路径数 由(0,0)到(m,n)的非降路径数为 。由(a,b)到(m,n)的非降路径数为 。由(0,0)到(m,n),再到(a,b)的非降路径数

30、。第八十八页，讲稿共一百二十二页哦例题从点(0,0)到达点(m,n)，其中mn，要求中间所经过的路程上的点(a,b)都满足ab。问有多少种不同的路径？第八十九页，讲稿共一百二十二页哦分析从(0,0)到(m,n)的非降路径 过对角线必过对角线一一对应：反射(0,0)(0,1)(m,n)(0,0)(1,0)(m,n)不过对角线第九十页，讲稿共一百二十二页哦反射：从上向下看，找路径与对角线交点的第一个点，关于对角线反射左下边路径，与右上的路径组合成一条路径。第九十一页，讲稿共一百二十二页哦例题 求从点(0,0)到达点(n,n)且不与直线y=x相交的非降路径数？分析：上一例题的特殊情况第九十二页，讲稿

31、共一百二十二页哦例题 一场音乐会的票价为50元/张，排队买票的顾客中有n位持有50元的钞票，m位持有100元的钞票，售票处没有准备50元的零钱。试问有多少种排队的方法，使购票能顺利进行，不出现找不开钱的状况，假定每位顾客限买一张，每位顾客仅买票一张，而且nm。第九十三页，讲稿共一百二十二页哦例题 用(m+n)维0,1-行向量(a1,a2,am+n)表示一种购票排队状态，其中ai=1表示第i位持50元的钞票，ai=0表示第i人持100元的钞票。这样的行向量有m个0，n个1，所以这样的行向量共有C(m+n,m)个，每个行向量可以对应从点(0,0)到点(m,n)的非降路径。当ai=1时，对应路径中的

32、第i步沿y轴向上走一格，当ai=0时，对应路径中的第i步沿x轴向右走一格。为了使购票顺利进行，每个路径中的点(a,b)应满足ab。也就是每个路径在直线y=x的上方且不穿过直线 y=x，可以有交点。第九十四页，讲稿共一百二十二页哦由于nm，也就是在直线y=x-1上方的所有路径。从(0,0)到(m,n)的在直线y=x-1上方的非降路径从(0,1)到(m,n+1)的在直线y=x上方的非降路径从(0,0)到(m,n+1)的在直线y=x上方的非降路径1yx=-第n个Catalan数1mnmmnmnm 122nnnn第九十五页，讲稿共一百二十二页哦Catalan数 第n个Catalan数122nnnnCn

33、nnn211第九十六页，讲稿共一百二十二页哦Catalan数的组合学意义第九十七页，讲稿共一百二十二页哦例题n个+1和n个-1所组成的序列中所有其前k项(k=1,2,2n)之和不小于0的序列的数目是多少？满足条件的序列为好序列，不满足条件的为坏序列。好序列数=序列总数-坏序列数。n个+1和n个-1所组成的坏序列与n+1个+1和n-1个-1所组成的序列一一对应。第九十八页，讲稿共一百二十二页哦例题对每个坏序列，总可以找到最小的正奇数，使得ak=-1且ak之前的+1和-1的个数相等。将这个坏序列中前k项的每一项取反号，其余部分保持不变。所得序列为n+1个+1和n-1个-1组成的序列。-1,-1,1

34、,1,-1,1变为1,-1,1,1,-1,1反之，对任一由n+1个+1和n-1个-1组成的序列，从左到右扫描，当+1的个数第一次比-1的个数多1时就把这些扫描到的项全部取反号，其余项不变，结果得到满足要求的坏序列。1,-1,1,1,-1,1变为-1,-1,1,1,-1,1第九十九页，讲稿共一百二十二页哦二项式定理nyx)()(yxnrxxx)(21nx)1(第一百页，讲稿共一百二十二页哦组合恒等式组合数组合恒等式：由组合数构成的恒等式组合数的大小关系knn为奇数n为偶数第一百零一页，讲稿共一百二十二页哦1.证明一：计算证明二：组合分析法knknn第一百零二页，讲稿共一百二十二页哦第一百零三页，

35、讲稿共一百二十二页哦第一百零四页，讲稿共一百二十二页哦2.杨辉三角形计算Pascal三角形证明一：证明二：组合分析法 kn 1knkn1第一百零五页，讲稿共一百二十二页哦3.利用二项式代特殊值证明一：nnkkn20证明二：一方面，按照子集的个数分类求和n元集合的所有子集的个数另一方面，按照元素与集合的属于、不属于关系第一百零六页，讲稿共一百二十二页哦4.二项式定理代特殊值证明一：12531420nnnnnnn证明二：组合分析法第一百零七页，讲稿共一百二十二页哦5.kkn1 1kknkkn 2111kknkknkkn322211kknkknkknkkn1211nkknkkn011111nnkkn

36、kkn第一百零八页，讲稿共一百二十二页哦kkn1011111nnkknkknkkn101111nnkknkkn11nknnnnnnknnkn11朱世杰恒等式第一百零九页，讲稿共一百二十二页哦6.应用：11nknnnnnnknnkn11 21n1131211n 32n 21242322n 43n32353433n第一百一十页，讲稿共一百二十二页哦n2122221n33321n44421n第一百一十一页，讲稿共一百二十二页哦7.证明一：倒写，然后两式相加nnnknknnknknk1100012nn证明二：计算，提出n证明三：求导数证明四：组合分析法证明五：数学归纳法第一百一十二页，讲稿共一百二十二

37、页哦8.证明一：积分证明二：计算，分子分母同乘n+1nkkknk111)1(1nn1n第一百一十三页，讲稿共一百二十二页哦证明一：组合分析法证明二：利用多项式的系数证明三：非降路径法nmmknmkmnk210212121,mmnZnmm第一百一十四页，讲稿共一百二十二页哦证明三：非降路径法1xym1(,0)B m1(0,)m12(,)C mmn n(0,)n从 到 的非降路径过且仅过直线 上线段AB的一个格点(0,0)12(,)mmn n1xym1(,)mk k1(,)A mn n第一百一十五页，讲稿共一百二十二页哦证明一：计算证明二：组合分析法krknknkrrnkrn第一百一十六页，讲稿共

38、一百二十二页哦证明一：计算证明二：组合分析法11rnrnrn第一百一十七页，讲稿共一百二十二页哦证明一：数学归纳法证明二：一般项1)!1(!33!22!11nnn证明三：加减项证明四：组合分析法第一百一十八页，讲稿共一百二十二页哦例 设集合A=a1,a2,an，A 的m个子集A1,A2,Am 两两互不包含。试证：111miiAn(1)(2)21mAnmii第一百一十九页，讲稿共一百二十二页哦例 给出 的个位数字和十位数字。10031093a第一百二十页，讲稿共一百二十二页哦例 证明r个连续自然数的乘积可被r！整除。第一百二十一页，讲稿共一百二十二页哦感谢大家观看感谢大家观看第一百二十二页，讲稿共一百二十二页哦