刚看了 一点点排列组合的书，写点总结：
首先最基本的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的个数就是这种颜色的球取的个数；
原文：http://www.cnblogs.com/vb4896/p/3874624.html
