《排列组合精讲》word版

《《排列组合精讲》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、排列组合百科名片排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。目录[隐藏]定义1.排列2.组合3.符号4.历史组合数的奇偶1.奇偶定义2.判定方法排列组合的基本理论和公式1.(一)两个基本原理是排列和组合的基础2.(二)排列和排列数3.(三)组合和组合数4.一、排列组合部分是中学数学中的难点之一5.二

2、、两个基本计数原理及应用[例题分析]1.1．首先明确任务的意义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.二、两个基本计数原理及应

3、用[例题分析]1.1．首先明确任务的意义2.2．分析是分类还是分步，是排列还是组合3.3．特殊优先4.4．捆绑与插空5.5．间接计数法6.6．挡板的使用7.7．注意排列组合的区别与联系：8.8．分组问题音乐专辑1.专辑介绍2.专辑曲目　　排列组合公式[编辑本段]定义排列　　公式P是排列公式，从N个元素取R个进行排列（即排序）.　　（P是旧用法，现在教材上多用A，即Arrangement）组合　　公式C是组合公式，从N个元素取R个，不进行排列（即不排序）。符号　　常见的一道题目C-组合数　　P-排列数（

4、现在教材为A）　　N-元素的总个数　　R-参与选择的元素个数!-阶乘，如5！=5×4×3×2×1=120　　C-Combination组合　　P-Permutation排列(现在教材为A-Arrangement)　　一些组合恒等式　　组合恒等式排列组合常见公式　　排列组合常见公式历史　　1772年，旺德蒙德以[n]p表示由n个不同的元素中每次取p个的排列数。而欧拉则于1771年以及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年，埃汀肖森引入了以表相同之意，这组合符号（Sign

5、sofCombinations）一直沿用至今。　　1830年，皮科克引入符号Cr以表示由n个元素中每次取出r个元素的组合数；1869年或稍早些，剑桥的古德文以符号nPr表示由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当於现在的n!。　　1880年，鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数；六年后，惠特渥斯以及表示相同之意，而且，他还以表示可重复的组合数。至1899年，克里斯托尔以nPr及nCr分别表示由n个不同元素中每次取出r个不重复之元素的排列数与组

6、合数，并以nHr表示相同意义下之可重复的排列数，这三种符号也通用至今。　　1904年，内托为一本百科辞典所写的辞条中，以表示上述nPr之意，以表示上述nCr之意，后者亦同时采用了。这些符号也一直用到现代。[编辑本段]组合数的奇偶奇偶定义　　对组合数C(n,k)(n>=k)：将n,k分别化为二进制，若某二进制位对应的n为0，而k为1，则C(n,k)为偶数；否则为奇数。判定方法　　组合数的奇偶性判定方法为:　　结论：　　对于C(n,k),若n&k==k则c(n,k)为奇数，否则为偶数。　　证明：　　利用数

7、学归纳法：　　由C(n,k)=C(n-1,k)+C(n-1,k-1);　　对应于杨辉三角：　　1　　11　　121　　1331　　14641　　………………　　可以验证前面几层及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-1)&k==k;　　(n-1)&(k-1)==k-1;　　由于k和k-1的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，

8、所以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-