《排列组合71459.doc》由会员分享，可在线阅读，更多相关《排列组合71459.doc（13页珍藏版）》请在金锄头文库上搜索。
1、排列组合百科名片排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。目录定义 1. 排列 2. 组合 3. 符号 4. 历史组合数的奇偶 1. 奇偶定义 2. 判定方法排列组合的基本理论和公式 1. (一)两个基本原理是排列和组合的基础 2. (二)排列和排列数 3. (三)组合和组合数 4. 一、排列组合部分是中学数学中的难点之一 5. 二、两个基本计数原理及应用例题分析 1. 1首先明确任务的
2、意义 2. 2分析是分类还是分步，是排列还是组合 3. 3特殊优先 4. 4捆绑与插空 5. 5间接计数法 6. 6挡板的使用 7. 7注意排列组合的区别与联系： 8. 8分组问题音乐专辑 1. 专辑介绍 2. 专辑曲目定义 1. 排列 2. 组合 3. 符号 4. 历史组合数的奇偶 1. 奇偶定义 2. 判定方法排列组合的基本理论和公式 1. (一)两个基本原理是排列和组合的基础 2. (二)排列和排列数 3. (三)组合和组合数 4. 一、排列组合部分是中学数学中的难点之一 5. 二、两个基本计数原理及应用例题分析 1. 1首先明确任务的意义 2. 2分析是分类还是分步，是排列还是组合 3
3、. 3特殊优先 4. 4捆绑与插空 5. 5间接计数法 6. 6挡板的使用 7. 7注意排列组合的区别与联系： 8. 8分组问题音乐专辑 1. 专辑介绍 2. 专辑曲目展开 排列组合公式编辑本段定义排列公式P是排列公式，从N个元素取M个进行排列（即排序）. （P是旧用法，现在教材上多用A，即Arrangement） 组合公式C是组合公式，从N个元素取R个，不进行排列（即不排序）。 符号 常见的一道题目C-组合数 A-排列数 （旧在教材为P） N-元素的总个数 R-参与选择的元素个数 !-阶乘 ，如5！=54321=120 C-Combination 组合 P-Permutation排列 (现在
4、教材为A-Arrangement) 一些组合恒等式 组合恒等式排列组合常见公式 kCn/k=nCn-1/k-1(a/b,a在下，b在上) Cn/rCr/m=Cn/mCn-m/r-m 排列组合常见公式历史1772年，旺德蒙德以np表示由n个不同的元素中每次取p个的排列数。而欧拉则于1771年以 及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年，埃汀肖森引入了 以表相同之意，这组合符号（Signs of Combinations）一直 沿用至今。 1830年，皮科克引入符号Cr以表示由n个元素中每次取出 r个元素的组合数；1869年或稍早些，剑桥的古德文以符号nPr 表示
5、由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当於现在的n!。 1880年，鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数；六年后，惠特渥斯以及表示相同之意，而且，他还以表示可重复的组合数。至1899年，克里斯托尔以nPr及nCr分别表示由n个不同元素中 每次取出r个不重复之元素的排列数与组合数，并以nHr表示相同意义下之可重复的排列数，这三种符号也通用至今。 1904年，内托为一本百科辞典所写的辞条中，以 表示上述nPr之意，以表示上述nCr之意，后者亦同时采用了。这些符号也一直用到现代。 编辑本段组合数的奇偶奇偶定义对组合数C(n,k) (n=k)
6、：将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,k)和C(n-1,k-1)为奇数： 则有：(n
7、-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最后一位也为1，所以有(n-1)&(k-1) =
8、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) != k-1; 显然，k的最后一位只能是0，否
9、则由(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的末尾必有一部分形如: 10; 相应的，k的对应部分为
10、: 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。 综上，结论得证! 编辑本段排列组合的基本理论和公式排列与元素的顺序有关，组合与顺序无关如231与213是两个排列，
11、231的和与213的和是一个组合 (一)两个基本原理是排列和组合的基础(1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有Nm1m2m3mn种不同方法 (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有Nm1m2m3mn种不同的方法 这里要注意区分两个原理，要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加法原理；做一件事，需要分n个步骤，步与步之间
12、是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理 这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来 (二)排列和排列数(1)排列：从n个不同元素中，任取m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列 从排列的意义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法 (2)排列数公式：从n个不同元素中取出m(mn)个元素的所有排列 当mn时，为全排列Pnn=n(n1)(n2)321n！ (三)组合和组合数(1)组合：从
13、n个不同元素中，任取m(mn)个元素并成一组，叫做从 n个不同元素中取出m个元素的一个组合 从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合 (2)组合数：从n个不同元素中取出m(mn)个元素的所有组合的个 这里要注意排列和组合的区别和联系，从n个不同元素中，任取m(mn)个元素，“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的 一、排列组合部分是中学数学中的难点之一原因在于 (1)从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽象思维能力； (2)限制条件有时比较隐晦，需要我
14、们对问题中的关键性词(特别是逻辑关联词和量词)准确理解； (3)计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大； (4)计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。 二、两个基本计数原理及应用(1)加法原理和分类计数法 1加法原理 2加法原理的集合形式 3分类的要求 每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏) (2)乘法原理和分步计数法 1乘法原理 2合理分步的要求 任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，
