首页 > 代码库 > 学习排列组合总结

学习排列组合总结

刚看了 一点点排列组合的书,写点总结:

首先最基本的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的个数就是这种颜色的球取的个数;

分割线可以挨在一起,夹在中间的那部分没有0(分割线可以画在第一个0的前面也可以画在最后一个0的后面,这点书上没说明白害我搞了一节自习课。),表示这种颜色的球不取; 那么问题就转化为在r个0之间划n-1条分割线,有多少种方案。 可以把分割线看成1,那么方案数不就是 n-1个1和r个0的组合数么?n-1个1和r个0组成一个n+r-1的二进制数,把0的位置定下来了,1的位置自然也就确定了,所以又转化成n+r-1个位置上放r个0的方案数,答案就是C(n+r-1,r);这就是重复组合的公式;
小应用:
1.求方程x1+x2+x3+。。。。xr=n的非负整数解的个数; 这个不就是上面讲的 重复组合么。。(把x1,x2这些x看成上面讲的0个个数)
2. 求方程x1+x2+x3+。。。。xr=n的正整数解的个数; 这个万变不离其宗,就是2个分割线不能挨到一起了;r个0之间共有r-1个位置,在这些位置上放n-1个1;所以答案就是C(r-1,n-1);