• / 14
  • 下载费用:10 金币  

排列与组合59372.doc

关 键 词:
排列与组合59372.doc
资源描述:
排列与组合 59372[编辑本段]符号常见的一道题目C-组合数 P-排列数 (现在教材为 A)N-元素的总个数 R-参与选择的元素个数 !-阶乘 ,如 5!=5*4*3*2*1=120C-Combination 组合 P-Permutation 排列 (现在教材为 A-Arrangement)一些组合恒等式组合恒等式排列组合常见公式排列组合常见公式[编辑本段]历史1772 年,旺德蒙德以[n]p 表示由 n个不同的元素中每次取 p个的排列数。而欧拉则于 1771年以 及于 1778年以表示由 n个不同元素中每次取出 p个元素的组合数。至 1872年,埃汀肖森引入了 以表相同之意,这组合符号(Signs of Combinations)一直 沿用至今。 1830 年,皮科克引入符号 Cr以表示由 n个元素中每次取出 r个元素的组合数;1869 年或稍早些,剑桥的古德文以符号 nPr 表示由 n个元素中每次取 r个元素的排列数,这用法亦延用至今。按此法,nPn 便相当於现在的 n!。 1880 年,鲍茨以 nCr及 nPr分别表示由 n个元素取出 r个的组合数与排列数;六年后,惠特渥斯以及表示相同之意,而且,他还以表示可重复的组合数。至 1899年,克里斯托尔以 nPr及 nCr分别表示由 n个不同元素中 每次取出 r个不重复之元素的排列数与组合数,并以 nHr表示相同意义下之可重复的排列数,这三种符号也通用至今。 1904 年,内托为一本百科辞典所写的辞条中,以 表示上述 nPr之意,以表示上述 nCr之意,后者亦同时采用了。这些符号也一直用到现代。[编辑本段]组合数的奇偶对组合数 C(n,k) (n=k):将 n,k分别化为二进制,若某二进制位对应的 n为 0,而 k为 1 ,则 C(n,k)为偶数;否则为奇数。组合数的奇偶性判定方法为:结论:对于 C(n,k),若 n对应于杨辉三角:11 1 1 2 11 3 3 11 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-1)(n-1)由于 k和 k-1的最后一位(在这里的位指的是二进制的位,下同)必然是不同的,所以 n-1的最后一位必然是 1。现假设 n(n-1)现假设 n 代表任意个 0。相应的,n 对应的部分为: 1{*}*; *代表 0或 1。而若 n对应的{*}*中只要有一个为 1,则(n-1)(n-1)显然,k 的最后一位只能是 0,否则由(n-1)相应的,n-1 的对应部分为: 1{*}*;相应的,k-1 的对应部分为: 01;则若要使得(n-1) (不会因为进位变 1为 0)所以 n(n-1)分两种情况:当 k-1的最后一位为 0时:则 k-1的末尾必有一部分形如: 10;相应的,k 的对应部分为 : 11;相应的,n-1 的对应部分为 : 1{*}0; (若为 1{*}1,则(n-1)所以 n (前面的 0可以是附加上去的)相应的,k 的对应部分为 : 10;相应的,n-1 的对应部分为 : 01; (若为 11,则(n-1)所以 n&k = k。由 3),4)得出当 C(n,k)为奇数时,n&k = k。综上,结论得证![编辑本段]排列组合的基本理论和公式排列与元素的顺序有关,组合与顺序无关.如 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=m1×m2×m3×…×mn 种不同的方法. 这里要注意区分两个原理,要做一件事,完成它若是有 n类办法,是分类问题,第一类中的方法都是独立的,因此用加法原理;做一件事,需要分 n个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才算完成,因此用乘法原理. 这样完成一件事的分“类”和“步”是有本质区别的,因此也将两个原理区分开来. (二)排列和排列数 (1)排列:从 n个不同元素中,任取 m(m≤n)个元素,按照一定的顺序排成一列,叫做从 n个不同元素中取出 m个元素的一个排列. 从排列的意义可知,如果两个排列相同,不仅这两个排列的元
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:排列与组合59372.doc
链接地址:https://www.weizhuannet.com/p-8741663.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开