排列组合
前言： 第一次尝试边上课边记录笔记…可能思路会有一点小乱，
排列数
线排列
公式：p(n,m)=!n/!(n-m)
推论1:p(n,m)=n*p(n-1,m-1)
推论2:p(n,m)=m*p(n-1,m-1)+p(n-1,m)一般反着用，用于分类
圆排列：
例子：4571,5714是同一种（转了一圈）
可以证明：一个圆转出来的线排列肯定互不相同
方案数：p(n,m)/m
可重排列（其中一种）
取m次数字（1-n）,则方案数为n的m次方
重集全排列：
n个不同的数,每一种有ki个，每种数字之间没有区别，取出所有的数
!(ki的和)/（!ki）的乘积
错位排列：
将n个数排列，第i个数不能填到i上
D(n)=(n-1)* (D(n-1)+D(n-2)),和线排列的推论2有联系（想法上）
组合数
无重组合
C(n,m)=n!/(!(n-m)* m! )
推论1:C(n,m)=C(n,n-m)，常用于改柿子，例如C(n,i)改为C(n,n-i)
推论2:C(n,m)=c(n-1,m-1)+c(n-1,m);也是杨辉三角原理，也是帕斯卡公式
推论3:C(n,m)=C(n-1,m-1)+C(n-2,m-2)+..+C(n-m,0)就是对推论2扩展前一项
可重组合
n中选m个（选了可以放回），没有顺序（记录集合个数）
H(n,m)=C(m+n-1,n-1)使用隔板法证明
常用球和盒子来描述：
1.m相同球放入n种不同的盒子，盒子不能为空
2.不超m…………………………………，盒子可以为空
3.不超过m……………………………..,盒子不能为空
不相邻组合
就是说比如我选择了5就不能选4,6
答案：C(n-m+1,m)
假设选出来a[1]-a[m],设b[i]=a[i]-i+1
那么b[i+1]-b[i]=a[i+1]-a[i]-1>0,求合法的b的方案数
b的上限：b[m]=a[m]-m+1<=n-m+1(a[m]最多就是n,而且a[n]单调递增)
二项式定理
(a+b)的k次方=sigma C(k,i)*a的i次方 *b的k-i次方
推论：我可以互换i和k-i；也可以用上面的推论表示C
注意常用a=b=1和a=-1,b=1的情况来化简柿子
恒等式（简化复杂度）
常用：
1.C(n,m)=c(n-1,m-1)*(n/m)
2.（i*C(k,i)）求和=k *2的(k-1)次方，应用:k中选i个得i分，所有方案得分的和为左式
3.（（i）的-1次方*C(k,i)）,选择奇数扣分，偶数得分，k>=2
4.x的i次方求导=i*x的i-1次方
5.f(x)*g(x)，一个导 *另外一个不导+一个不导 *另外一个导
左导右不导，右导左不导
6.f(g(x))=f导数*g导数