首页 > 代码库 > 学习排列组合总结
学习排列组合总结
刚看了 一点点排列组合的书,写点总结:
首先最基本的2个 公式(貌似数学选修2-几来着有的,还有个什么二项式定理,就是求(a+b)^n展开后的东东。):
1.排列数 A(n,r)=n*(n-1)*(n-2).......*(n-r+1)=n!/(n-r)!(可以理解为从n个颜色不相同的球里取r个且取的顺序不同就算是不同的方案的方案数),另外A(n,n)=n!,有的地方A用P来表示,习惯问题罢了;证明也比较容易(自己写的,可能和标准的思路不一样,下同。): 对于第一个球,有n种取法;第二个有n-1种,第i个就有(n-i+1)种,根据乘法原理相乘就是答案 ;
2.组合数C(n,r)=A(n,r)/r!=n!/【(n-r)!*r!】;(可以理解为从n个颜色不相同的球里取r个且取的顺序不同算同一种方案的方案数)。另外C(n,n)=1; 证明可以由排列数A推来,对于任意有r个元素的排列(也就是A(r,r)),共有r!种情况。组合数其实就是排列数减去重复的部分。。r!种情况对于组合数C只能算一种,所以C(n,r)=A(n,r); 根据数学推导 还有 C(n,r)=C(n,n-r); C(n,r)=C(n-1,r)+C(n-1,k-1);这些都是带入公式即可验证;第二个特别有用,可以将乘法除法转化为加法,这样对于大数据,就只要写一个高精度加法就好了; 第二个定理的证明 还可以抽象的想:对于C(n,r),分2种情况讨论。情况一:取第一个元素,那么有C(n-1,r-1)种方案;情况二: 不取第一个元素,那么有C(n-1,r)种方案:根据加法原理两种情况加起来就是C(n,r); 拓展开去 ; 如果要求从n个颜色不相同的球里取r个且取的顺序不同就算是不同的方案的方案数,每个球拿完之后又放回盒子怎么办呢? 类似推导排列数A,取r次,每次都有n种选择,所以方案数是r^n;这就是 重复排列的公式; 再如果顺序不同只能算一种方案呢? 首先想到能不能像推导组合数C一样从排列数推来,不过。。。能不能做出来就不晓得了。。想了一节晚自习 没思路。。 百度了一下,结合紫书上的证明(哈工大出的书上坑爹的写着”证明略“),虽然方法不一样,但思想一样,下面是紫书上说的算法: 先在草稿纸上 写 r个0(同一行。。),先在第一个0前面以及最后一个0后面各划一条分割线,用n+1个条分割线将他们分成n个部分,每个部分里0的个数就是这种颜色的球取的个数;