搜索
组合数学1.组合与组合数(1)组合①1组合的定义：一般地，从n个不同元素中取出m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。②对“取出”的正确理解：从n个不同元素中取出m(m≤n)个元素，是指一次取出m个具体的元素构成的一个组合。③组合的实质：所谓组合是把几个事物放在一起，不计顺序，而且事物之间两两不同，当做一个组。组合的概念与集合类似，一个组合和一个集合都由其元素惟一确定。④排列与组合的区别：二者的共同点是都要“从n个不同元素中，（转载自中国教育文摘，请保留此标记。）任取m个元素”；不同点是组合与顺序无关，排列与顺序有关。⑤注意：如果两个组合中的元素完全相同，那么不管它们的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，即使只有一个元素不同，就是不同的组合。(2)组合数①组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符号Cmn表示。②“组合”与“组合数”是两个不同的概念，一个组合不是一个数，而是具体的一件事，而组合数是一个数。③组合数公式(应掌握推导方法)1.排列的定义包含两个基本内容：一是“取出元素”；二是“按照一定顺序”。“一定顺序”表示与位置有密切关系，这里的位置应该视具体问题的性质和条件来决定。如，从1，2，3三个数中每次取出两个不同的数相乘，问有多少个不同的积；如果相除，问有多少个不同的商。在这里，前者就不需要考虑“顺序”，这里由乘法的交换律所得，而后者必须考虑谁作分子、分母的“顺序”问题。2.排列定义中指出的是一个排列，而不是所有的排列。对于两个排列来讲，只有当元素完全相同且元素排列顺序也完全相同时，才是相同的一个排列。元素不完全相同或元素完全相同而排列顺序不完全相同的排列，都不是同一个排列。3.在排列定义中，如果mn(每次只取出一部分元素)，这样的一个排列叫做选排列。如果m=n(每次取出全部元素，这样的一个排列叫做全排列。4.排列数概念可以从集合的角度进行理解。例如，从a，b，c这3个不同元素中任取2个的排列数的问题，就是集合A={ab，ba，ac，ca，bc，cb}的元素个数问题，显然card(A)=6。这里，由排列的定义知，集合A中的元素ab和ba应视为不同元素。5.对于排列数公式，应注意以下几个方面：(1)m，n∈N*且m≤n；(2)公式右边第一个因数为n，后面每个因数都比前面一个因数少1，最后一个因数是n-m+l，共m个因数相乘；(3)教材中公式的推导采用不完全归纳法，由特殊到一般，每一种情形都是以分步计数原理为依据，采用了分步解决的思想方法。另外，在推导公式时，为了使问题更直观，建立了“一个排列”与“一种填法”的一一对应关系，这种模型化方法解排列应用问题时经常用到；(4)对于排列数公式的另一种形式。.要分清“排列”和“排列数”这两个不同概念，一个排列是指从n个不同元素中，任取m个元素，按照一定顺序排成一列的一种具体排法，它是具体的形式，而不是数；而排列数是从n个不同元素中取出m个元素的所有排列的个数，即排列共有多少个不同的形式，它是一个数，其公式为=n(n-1)(n-2)·…·(n-m+1)，其中m，n∈N。2.排列定义规定给出的n个元素各不相同，并且取出m个元素也各不相同。即教材研究的是相异元素不可重复的排列。如果每个元素可重复选取，就成了相异元素可重复的排列，这种排列只需用分步记数原理就可得排列数是nm，因为在一个排列的每个位置上都有n种选取元素的方法。我国著名数学家吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。计算机程序是计算机的大脑思维，而程序的本质就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。组合数学的产生恰好满足了编写计算机程序的需求。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，需要很深的数学素养，逐渐成为了数学的主流分支。本世纪公认的伟大数学家盖尔芳德预言组合数学和几何学将是下一世纪数学研究的前沿阵地。这一观点得到了世界各界的广泛认可。甚至可以说，没有组合数学就没有计算机软件。世界上著名的计算机科学家很多都是组合数学出身。在欧洲，美国，组合数学的研究被很多大公司，大学所重视，而在中国，在中国的软件业还十分落后的今天，我们对组合数学的重视程度远远不够。Gian-CarloRota教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。组合数学涉及将一个集合的物体排列成满足一些指定规则的格式。以下两种问题反复出现：排列的存在性，排列的计数和分类。虽然对任何组合数学问题都可以考虑其存在性和计数问题，但在实际问题中如果存在性问题需要广泛的研究那么计数问题则是非常困难的。与上述问题同时出现的另外两种组合数学问题是：研究一个已知的数列。当人们建立起满足某些指定条件的一个排列以后，可能要考察这个排列的性质和结构。这样的可能会涉及分类问题，也许还涉及一些分类问题，也许还涉及一些潜在的应用。另外一个问题是构造一个最优的排列。如果有可能存在多于一个的排列，即找出某种规定意义下的“最好的”或“最优的”排列。组合数学可以一般描述为：组合数学是研究离散结构的存在，计数，分析，和优化等问题的一门学科。经验证发现的组合数学最有力的工具之一为数学归纳法。归纳是一个强有力的过程，在组合数学中尤其是如此。用数学归纳法证明一个结果常常比证明一个弱结果更容易。许多组合问题的解决常常需要某些特别的例证，而且有时需要结合使用一般的理论。我们必须学会建立数学模型，研究模型，抓住问题的要害，灵活的应用智慧来解决问题。作为计算机专业的学生，我们必须把组合数学的学习放在一个重要的位置上来，掌握基本的组合数学原理，培养专业的数学思维，这样才能在以后的工作学习中掌握主动和先机。才能在将来为中国的计算机软件事业做出自己的贡献。