排列组合

• 排列组合
  • 排列数
    • 线排列
    • 圆排列：
    • 可重排列（其中一种）
    • 重集全排列：
    • 错位排列：
  • 组合数
    • 无重组合
    • 可重组合
    • 不相邻组合
    • 二项式定理
  • 恒等式（简化复杂度）
    • 常用：

前言： 第一次尝试边上课边记录笔记…可能思路会有一点小乱，

排列数

线排列

公式：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导数