数学竞赛辅导讲座组合恒等式、组合不等式

《数学竞赛辅导讲座组合恒等式、组合不等式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学竞赛辅导讲座：组合恒等式、组合不等式知识、方法、技能Ⅰ．组合恒等式①竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础，加以推广、补充而形成的一类组合问题.组合恒等式的证明要借助于高中常见的基础组合等式.例如⑥⑤④③②组合恒等式的证明方法有：①恒等变形，变换求和指标；②建立递推关系；③数学归纳法；④考虑组合意义；⑤母函数.Ⅱ．组合不等式组事不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少，但是近年来组合不等式的证明却出现在国内、国际大赛上.例如1993年中国高中数学联赛二试第二大题为：设A是一个有n个元素的集

2、合，A的m个子集A1，A2…，Am两两互不包含，试证：（1）（2）其中

3、Ai

4、表示Ai所含元素的个数，表示n个不同元素取

5、Ai

6、的组合数.再如1998年第39届国际数学奥林匹克竞赛中第二大试题为：在某一次竞赛中，共有a个参赛选手与b个裁判，其中b≥3，且为奇数.每个裁判对每个选手的评分中只有“通过”或“不及格”两个等级，设k是满足条件的整数；任何两个裁判至多可对k个选手有完全相同的评分.证明：4因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有：1．在集合间建立单射，利用集合阶的不等关系定理，设X和Y都是有限集，f为从X

7、到Y的一个映射，（1）若f为单射，则

8、X

9、≤

10、Y

11、；（2）若f为满射，则

12、X

13、≥

14、Y

15、.2．利用容斥原理例如：设元素a属于集族{A1，A2，…，An}的k个不同集合，则在中a被计算了k次，当k≥2时，集合两两的交集共有个.由于中至少少被计算了k－1次，这样我们得到下面的不等式：组合不等式（*）可由容斥公式：删去右边第三个和式起的所有和式得到.采用这种办法，我们可以从容斥公式得到另外一些组合不等式，只是要注意这些不等式的方向的变化.3．利用抽屉原则由于抽世原则的结论本身就是组合不等式关系，所以我们利用抽屉原则，巧妙构造抽屉的方法证明组

16、合不等式.4．利用组合分析在复杂的组合计数问题、离散极值问题等问题中，会出现一些组合不等式，这时可运用组合分析方法证明之.赛题精讲例1证明：4【分析】把，变换求和指标.【证明】，则所以即，从而有.例2求证：证明设，则由基本恒等式得【说明】注意到an中各项的系数均与n无关，且符号正负相同，由此想到an与an－1之间必定存在着某些联系，且是递推关系.例3求证：【分析】考虑到恒等式，仿例2解决.【证明】令因为，，4令①于是由①式得.这说明{an}为等差数列，而a0=1,a1=2，故公差d=1，且an=n+1.【说明】此题运用变换求和指标的

17、方法，找出了an，an－1，an－2之间的线性关系式，再由初始条件求得an.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组事恒等式时经常用到.4