资源描述：
《排列与组合53335》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、排列与组合53335[编辑本段]符号 常见的一道题目 C-组合数 P-排列数（现在教材为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年，埃汀肖森引入了以表相同之意，这
2、组合符号（SignsofCombinations）一直沿用至今。 1830年，皮科克引入符号Cr以表示由n个元素中每次取出r个元素的组合数；1869年或稍早些，剑桥的古德文以符号nPr表示由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当於现在的n!。 1880年，鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数；六年后，惠特渥斯以及表示相同之意，而且，他还以表示可重复的组合数。至1899年，克里斯托尔以nPr及nCr分别表示由n个不同元素中每次取出r个不重复之元素的排列数与组合数，并以nHr表示相同意义下之可重复的排列数，这三种符号也通用至今
3、。 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)为奇数，否则为偶数。 证明： 利用数学归纳法： 由C(n,k)=C(n-1,k)+C(n-1,k-1); 对应于杨辉三角： 1 11 121 1331 14641 ……………… 可以验证前
4、面几层及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的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，所以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
5、(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)==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。
6、 由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，否则由(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
7、).假设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的对应部分为:11; 相应的，n-1的对应部分为:1{*}0;(若为1{*}1,则(n-1)&k==k) 相应的，n的对应部分为:1{*}1; 所以n&k=k。 当k-1的最后一位为1时: 则k-1的末尾必有
