组合计数问题研究.doc

组合计数问题研究 高一c班 张天豪组合计数就是计算集合元素的个数，它是组合数学的重要组成部分。合计数理论是组合数学中一个最基本的研究方向，主要研究满足一定条件的安排方式的数目及其计数问题。一、常用计数方法：1、基本方法和公式：枚举法加法原理：做一件事情，有几种方式，在第一种方式中m种不同的方法，在第二种方式中有n种不同的方法，在最后一种方式中有r种不同的方法，那么完成这件事情共有m+n+r种不同的方法。乘法原理：做一件事情，有几个步骤，在第一步中m种不同的方法，在第二步中有n种不同的方法，在最后一步中有r种不同的方法，那么完成这件事情共有mnr种不同的方法。递推方法：寻求递推公式如果一个数列的第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，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种放法，这样共有101=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=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)。生成函数的优势在于，某些生成函数可以化简为一个很简单的函数。比如：从 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+.)(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、3251的情况，共有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种综上所述，组合计数问题包含内容很多而且十分有技巧性，它囊括了枚举法、加法原理与乘法原理、排列组合、容斥