《排列组合56633.doc》由会员分享，可在线阅读，更多相关《排列组合56633.doc（3页珍藏版）》请在金锄头文库上搜索。
1、排列组合奇偶定义对组合数C(n,k) (n=k)：将n,k分别化为二进制，若某二进制位对应的n为0，而k为1 ，则C(n,k)为偶数；否则为奇数。 判定方法组合数的奇偶性判定方法为： 结论： 对于C(n,k),若n&k = k 则c(n,k)为奇数，否则为偶数。 证明： 利用数学归纳法： 由C(n,k) = C(n-1,k) + C(n-1,k-1); 对应于杨辉三角： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 可以验证前面几层及k = 0时满足结论，下面证明在C(n-1,k)和C(n-1,k-1) (k 0) 满足结论的情况下， C(n,k)满足结论。 1).假设C(n-1
2、,k)和C(n-1,k-1)为奇数： 则有：(n-1)&k = k; (n-1)&(k-1) = k-1; 由于k和k-1的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，所以n-1的最后一位必然是1 。 现假设n&k = k。 则同样因为n-1和n的最后一位不同推出k的最后一位是1。 因为n-1的最后一位是1，则n的最后一位是0，所以n&k != k，与假设矛盾。 所以得n&k != k。 2).假设C(n-1,k)和C(n-1,k-1)为偶数： 则有：(n-1)&k != k; (n-1)&(k-1) != k-1; 现假设n&k = k. 则对于k最后一位为1的情况： 此时n最
3、后一位也为1，所以有(n-1)&(k-1) = k-1，与假设矛盾。 而对于k最后一位为0的情况： 则k的末尾必有一部分形如：10; 代表任意个0。 相应的，n对应的部分为： 1*; *代表0或1。 而若n对应的*中只要有一个为1，则(n-1)&k = k成立，所以n对应部分也应该是10。 则相应的，k-1和n-1的末尾部分均为01,所以(n-1)&(k-1) = k-1 成立，与假设矛盾。 所以得n&k != k。 由1)和2)得出当C(n,k)是偶数时，n&k != k。 3).假设C(n-1,k)为奇数而C(n-1,k-1)为偶数： 则有：(n-1)&k = k; (n-1)&(k-1)
4、 != k-1; 显然，k的最后一位只能是0，否则由(n-1)&k = k即可推出(n-1)&(k-1) = k-1。 所以k的末尾必有一部分形如：10; 相应的，n-1的对应部分为： 1*; 相应的，k-1的对应部分为： 01; 则若要使得(n-1)&(k-1) != k-1 则要求n-1对应的*中至少有一个是0. 所以n的对应部分也就为 ： 1*; (不会因为进位变1为0) 所以 n&k = k。 4).假设C(n-1,k)为偶数而C(n-1,k-1)为奇数： 则有：(n-1)&k != k; (n-1)&(k-1) = k-1; 分两种情况： 当k-1的最后一位为0时: 则k-1的末尾必
5、有一部分形如： 10; 相应的，k的对应部分为 : 11; 相应的，n-1的对应部分为 : 1*0; (若为1*1,则(n-1)&k = k) 相应的，n的对应部分为 : 1*1; 所以n&k = k。 当k-1的最后一位为1时： 则k-1的末尾必有一部分形如: 01; (前面的0可以是附加上去的) 相应的，k的对应部分为 : 10; 相应的，n-1的对应部分为 : 01; (若为11，则(n-1)&k = k) 相应的，n的对应部分为 : 10; 所以n&k = k。 由3),4)得出当C(n,k)为奇数时，n&k = k。 综上，结论得证基本理论和公式排列与元素的顺序有关，组合与顺序无关如
6、231与213是两个排列，2+3+1的和与2+1+3的和是一个组合 (一)两个基本原理是排列和组合的基础(1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+mn种不同方法 (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有N=m1m2m3mn种不同的方法 这里要注意区分两个原理，要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加
7、法原理；做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理 这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来 (二)排列和排列数(1)排列：从n个不同元素中，任取m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列 从排列的意义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法 (2)排列数公式：从n个不同元素中取出m(mn)个元素的所有排列 当m=n时，为全排列Pnn=n(n1)(n2
8、)321=n！ (三)组合和组合数(1)组合：从n个不同元素中，任取m(mn)个元素并成一组，叫做从 n个不同元素中取出m个元素的一个组合 从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合 (2)组合数：从n个不同元素中取出m(mn)个元素的所有组合的个 这里要注意排列和组合的区别和联系，从n个不同元素中，任取m(mn)个元素，“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的 一、排列组合部分是中学数学中的难点之一原因在于 (1)从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽
9、象思维能力； (2)限制条件有时比较隐晦，需要我们对问题中的关键性词(特别是逻辑关联词和量词)准确理解； (3)计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大； (4)计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。 二、两个基本计数原理及应用(1)加法原理和分类计数法 1加法原理 2加法原理的集合形式 3分类的要求 每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏) (2)乘法原理和分步计数法 1乘法原理 2合理分步的要求 任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同
