《组合计数问题研究.doc》由会员分享，可在线阅读，更多相关《组合计数问题研究.doc（4页珍藏版）》请在三一办公上搜索。
1、组合计数问题研究 高一C班 张天豪组合计数就是计算集合元素的个数，它是组合数学的重要组成部分。合计数理论是组合数学中一个最基本的研究方向，主要研究满足一定条件的安排方式的数目及其计数问题。一、常用计数方法：1、基本方法和公式：枚举法加法原理：做一件事情，有几种方式，在第一种方式中m种不同的方法，在第二种方式中有n种不同的方法，在最后一种方式中有r种不同的方法，那么完成这件事情共有m+n+r种不同的方法。乘法原理：做一件事情，有几个步骤，在第一步中m种不同的方法，在第二步中有n种不同的方法，在最后一步中有r种不同的方法，那么完成这件事情共有mnr种不同的方法。递推方法：寻求递推公式如果一个数列的
2、第n项an与该数列的其他一项或多项之间存在对应关系，这个关系就称为该数列的递推公式。如斐波纳契数列的递推公式为an=a（n-1）+a（n-2）；等差数列递推公式：an=a(n-1)+d（d为公差）；等比数列递推公式：bn=b(n-1) q （q为公比）排列组合公式：组合计算公式从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；2、其他方法：母函数（生成函数） 配对原理 子集类 归纳法 二、解题心得归纳：1、运用加法原理或乘法原理：例题1:将编号为1
3、，2，3，4，5的五个小球放入编号为1，2，3，4，5的五个盒子中，每个盒子只放入一个，一共有多少种不同的放法？若编号为1的球恰好放在了1号盒子中，共有多少种不同的放法？若至少有一个球放入了同号的盒子中（即对号放入），共有多少种不同的放法？解答： 54321=120种4321=24种1）从五个球中选定1个球对号放入，有5种选法，其余的4个球均不对号放入，有9种放法，这样共有59=24种放法2）从五个球中选定2个球对号放入，有10种选法，其余的3个球均不对号放入，有2种放法，这样共有102=20种放法3）从五个球中选定3个球对号放入，有10种选法，其余的2个球均不对号放入，有1种放法，这样共有1
4、01=10种放法3）五个球均对号放入，有1种放法总共76种不同方法例题2：正整数324000能被多少个正整数整除？多少个正偶数整除？解答：32400=253453 正整数：654=120个 正偶数：554=100个2、寻求递推公式例题：一个楼梯共有10级台阶，规定每步可以迈一级台阶或二级台阶，最多可以迈三级台级，从地面上到最上面一级台阶，一共可以有多少种不同的迈法？解答：从简单情况入手寻求递推公式：（1）若有1级台阶，则只有一种迈法：a1=1；（2）若有2级台阶，则有两种迈法，则a2=2；（3）若有3级台阶，则有4种迈法，a3=4；（4）若有4级台阶，a4=a1+a2+a3=7（种）相应有a5
5、=a4+a2+a3=13（种） a6=a5+a4+a3=24（种） a10=a9+a8+a7=274（种）共有274种迈法3、运用排列组合公式例题：以正十边形的顶点作为三角形的顶点 请问这样一共可以构成多少个锐角或钝角三角形？解答：总共的三角形个数=120个直角三角形：在圆内接正十边形中以其顶点为端点的直径共有5条，以每条直径为斜边的直角三角形各有8个，因此直角三角形共有40个。可以构成锐角或钝角三角形80个。三、知识拓展补充：生成函数（母函数）（涉及到牛顿二项式定理）生成函数是组合数学中尤其是计数方面的一个重要理论和工具。其实质在于构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)
6、。生成函数的优势在于，某些生成函数可以化简为一个很简单的函数。比如：从 4个同学随机选n个同学出来有多少种选法。学过简单的排列与组合的同学都知道，答案就是C4n。也就是说。从n=0开始，问题的答案分别是1,4,6,4,1,0,0,0,.。那么它的生成函数g(x)就应该是g(x)=1+4x+6x2+4x3+x4。这不就是二项式展开吗？于是，g(x)=(1+x)4。例题：我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。解答：g(x)=(1+x2+x4+.) (1+x5+x10+
7、.)(1+x+x2+x3+x4)(1+x) =.(套用等比数列通项和公式)=(1-x)-2 =C(1,0)+C(2,1)x+C(3,2)x2+C(4,3)x3. =1+2x+3x2+4x3+5x4+. 指数为n的系数是n+1，故n+1就是我们所求得解。四、逻辑分析推理在解决问题中的关键性例题1：若有序正整数对（a,b)(ab)满足a+b=2008，ab互质，满足条件的(a,b)共有多少对？解答：a + b = 2008。a 、b奇偶性相同。而a、b同为偶数时，必含有公因数2，不能互质。因此a、b必同为奇数。比1004小的奇数总共有502个，其中2008=23251,因此舍去a=1251、325
8、1的情况，共有500对正整数对。例题2：（2010浙江高考）有4位学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”五个项目的测试，每位同学上、下午各测试一个项目，且不重复若上午不测“握力”项目，下午不测“台阶”项目，其余项目上、下午都各测试一人则不同的安排方式共有多少种（用数字作答）？解答：先安排4位同学参加上午的四项测试，共有A44种不同安排方式。接下来安排下午的“身高与体重”“立定跳远”“肺活量”“握力”测试。假设A、B、C同学上午分别安排的是“身高与体重”“立定跳远”“肺活量”测试，若D同学选择“握力”测试，安排A、B、C同学分别交叉测试，有2种；若D同学选择“身高与体重”“立定跳远”“肺活量”测试中的1种，有A31种方式，安排A、B、C同学进行测试有3种；所以总共有安排方式A44（2+ A313）=264种综上所述，组合计数问题包含内容很多而且十分有技巧性，它囊括了枚举法、加法原理与乘法原理、排列组合、容斥原理、抽屉原理、递推归纳、构造论证等一系列数学知识。我认为，题目万变不离其宗，我们需要掌握的核心除了常用的解题技巧和公式规律以外，最重要的是如何提升自己的逻辑思维能力和对于题目信息的分析处理能力。只有能力获得了提高，我们才会真正发现数学之美，解决题目也就不成问题了。
