资源描述：
《高老数学基础.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、排列组合百科名片排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。排列组合公式定义 公式P是排列公式，从N个元素取R个进行排列（即排序）. （P是旧用法，现在教材上多用A，即Arrangement） 公式C是组合公式，从N个元素取R个，不进行排列（即不排序）。符号 常见的一道题目 C-组合数 P-排列数（现在教材为A） N-元素的总个数 R-参与选择的
2、元素个数 !-阶乘，如5！=5×4×3×2×1=120 C-Combination组合 P-Permutation排列(现在教材为A-Arrangement) 一些组合恒等式 组合恒等式 排列组合常见公式 排列组合常见公式[编辑本段]历史 1772年，旺德蒙德以[n]p表示由n个不同的元素中每次取p个的排列数。而欧拉则于1771年以及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年，埃汀肖森引入了以表相同之意，这组合符号（SignsofCombinations）一直沿用至今。 1830年，皮科克引入符号Cr以表示由n个元素
3、中每次取出r个元素的组合数；1869年或稍早些，剑桥的古德文以符号nPr表示由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当於现在的n!。 1880年，鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数；六年后，惠特渥斯以及表示相同之意，而且，他还以表示可重复的组合数。至1899年，克里斯托尔以nPr及nCr分别表示由n个不同元素中每次取出r个不重复之元素的排列数与组合数，并以nHr表示相同意义下之可重复的排列数，这三种符号也通用至今。 1904年，内托为一本百科辞典所写的辞条中，以表示上述nPr之意，以表示上述nCr之意
4、，后者亦同时采用了。这些符号也一直用到现代。[编辑本段]组合数的奇偶 对组合数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 11 121 1331 14641 ……………… 可以验证前面几层及k=0时满足结论，下面证明在C(n-1,k)和C(n-1,k-
5、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的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，所以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)&
6、k!=k; (n-1)&(k-1)!=k-1; 现假设n&k==k. 则对于k最后一位为1的情况： 此时n最后一位也为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
7、,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，否则由(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).
8、假设C(n
