组合数学提高
二项式定理
内容
嗯，这个东西就是杨辉三角的公式版
$(x+y)^n=\sum\limits_{k=0}^{n}C_n^kx^{n-k}y^k$
将这个公式拆开，得到了这样一个玄学公式：
$(x+y)^n=C_n^0x^n+C_n^1x^{n-1}y+C_n^2x^{n-2}y^2+……+C_n^{n-1}xy^{n-1}+C_n^ny^n$
你看这个公式他又大又圆是不是很像某个小学数奥的东西呢？
没错，这玩意和杨辉三角几乎一毛一样，所以实际上是杨辉三角的一种实现方式。
等价形式
$(x+y)^n=\sum\limits_{k=0}^{n}C_n^{n-k}x^{n-k}y^k$
$(x+y)^n=\sum\limits_{k=0}^{n}C_n^{n-k}x^{k}y^{n-k}$
$(x+y)^n=\sum\limits_{k=0}^{n}C_n^{k}x^{k}y^{n-k}$
$(1+x)^n=\sum\limits_{k=0}^nC_n^kx^k$
我也不知道叫什么定理1
$C_n^0-C_n^1+C_n^2-C_n^3+……+(-1)^nC_n^n=0$
即$C_n^0+C_n^2+……=C_n^1+ C_n^3+……=2^{n-1}$
证明：上面那个我也不知道怎么证，反正它就是对的。。。
下面那个，根据二项式定理$C_n^0+C_n^1+C_n^2+C_n^3+……+C_n^n=(1+1)^n=2^n$
又由于$C_n^0+C_n^2+……=C_n^1+ C_n^3+……$,所以其任意一项等于$2^n\div 2=2^{n-1}$
证毕(确信)
我也不知道叫什么定理2
$kC_n^k=nC_{n-1}^{k-1}$
证明:左式=$k\frac{n!}{(n-k)!k!}=\frac{n!}{(n-k)!k!\div k}$
右式=$n\frac{n!\div n}{(n-k)!k!\div k}=\frac{n!}{(n-k)!k!}$
左式等于右式，证毕。
我也不知道叫什么定理3
$C_n^1+2C_n^2+……+nC_n^n=n2^{n-1}$
既$\sum\limits_{i=1}^niC_n^i=n2^{n-1}$
证明：使用我也不知道什么定理2 得到$1C_n^1 = nC_{n-1}^0$,$2 C_n^2 = nC_{n-1}^1$
这样就得到了原式$=n C_{n-1}^0+nC_{n-1}^{1}+……+nC_{n-1}^{n-1}$
$=n(C_{n-1}^0+C_{n-2}^1+……+C_{n-1}^{m-1})$
$=n2^{n-1}$
我也不知道叫什么定理4
$1C_n^1+4C_n^2+9C_n^3+……n^2C_n^n=n(n+1)2^{n-2}$
换而言之就是 $\sum\limits_{i=1}^{n}i^2C_n^i=n(n+1)2^{n-2}$
证明(这个证明可能会用到前面的很多性质，最好把前面的都看懂了在证明)
$\sum\limits_{i=1}^{n}i^2C_n^i$
=$\sum\limits_{i=1}^ni\times n \times C_{n-1}^{i-1}$
$=\sum\limits_{i=0}^{n-1}C_{n-1}^{i} \times(i+1) \times n$
$=(\sum\limits_{i=0}^{n-1}C_{n-1}^i\times i+\sum\limits_{i=0}^{n-1}C_{n-1}^i)\times n$
这里我们将这个式子拆开来，不然实在有点难理解：
$\sum\limits_{i=0}^{n-1}C_{n-1}^i\times i=\sum\limits_{i=1}^{n-1}iC_{n-1}^i=(n-1)2^{n-2}$
$\sum\limits_{i=0}^{n-1}C_{n-1}^i=2^{n-1}$
原式$=((n-1)2^{n-2}+2^{n-1}) \times n$
=$(n+1)2^{n-1}\times n$
证毕。
我也不知道叫什么定理5
$\sum\limits_{i=0}^{n}{C_n^i}^2=C_{2n}^n$
这个性质我们用感性理解的方式，用例子来说明：
两个班，每个班有n个妹子，gyf要从两个班中选择n个妹子来上，那么他的选择总方案是$C_{ 2n}^n$,这非常明显，不必多说了。同时我们可以让gyf从一个班中选择i个妹子($0\le i \le n$ ),另一个班中选择(n-i)个妹子，这样的方案数是$C_{n}^iC_{n}^{n-i}$,同时枚举i，就得到总方案数为$\sum\limits_{i=0}^n C_{n}^iC_{n}^{n-i}$,应为$C_{n}^i=C_{n}^{n-i}$,所以总方案数为$\sum\limits_{i=0}^{n}{C_n^i}^2$,很明显两种选择方法是等价的，故性质成立。
康拓展开
问题描述
给你一个数列，求这个数列在所有与其相同的数列中的字典序排名(相同的定义是，长度相同且组成元素相同)
内容
$ans=\sum\limits_{i=1}^{n-1}a_i \times (n-i)!$
$a_i$表示排名在i之后且字典序小于i的元素。
举例
数列为{$3,1,4,5,2$},求其排名
对于3来说，后面有两个数比它小，所以啊a[1]=2;
对于1来说，后面没有数比它小，所以a[2]=0;
对于4来说，后面有一个数比它小，所以a[3]=1;
对于5来说，后面有一个数比它小，所以a[4]=1;
所以答案就是$4! \times 2+3! \times 0 +2! \times 1 +1! \times 1$
康拓逆展开
问题
一个长度为5的序列有1至5组成，其字典序排名为107，问这个序列。
解法
用和康拓展开相同的思维：在第一位，$107 \div 4!=4 $余$10$,所以第一位之后有4位比它大，故第一位为5
这样类推下去 就得到了答案。
第一类斯特林数
嗯，看到这个标题是不是觉得无比高大上，但是实际上，只要不涉及到更高层次，这种数比其他很多数简单很多。。。
问题
将n个数分为k个环，求方案数。
解法
$s_n^k$表示将n个数分为k个环的方案数
有以下转移方程：$s_n^k=(n-1)s_{n-1}^k+s_{n-1}^{k-1}$
证明
将新进来的数分成两种，既放入已有的圆中或新开一个圆，在旧圆中共有n-1个位置，所以就有了上面的公式。
第二类斯特林数
问题
将n个数分成k个集合，求方案数
解法
$S_n^k$表示将n个数分成k个集合的方案数。
$S_n^k=kS_{n-1}^k+S_{n-1}^{k-1}$
证明
将新进来的数分为两类，在已有集合中的方案数为$kS_{n-1}^k$,另一种为$S_{n-1}^{k-1}$
卡特兰数
问题
有一张n*n的图，求从左下角走到右上角且不经过中线的方案。
解法
如图，我们发现，任意一条经过中线的路径(下文称为非法路径)，都会经过对角线上面的一条线，也就是图中的绿线，而将过绿线之后的路径关于绿线对称，就发现每一条非法路径的终点都是点(n+1,n-1)，所以可以看成每条非法路径都可以变成一条从(0,0)到点(n+1,n-1)的路径。
我们考虑用组合数来表示总路径数：每一条路径都可以看成是由n次向上和n次向右组成的，所以我们只要找出2n次行动中n次向上的可能，就是方案数了，既$C_{2n}^n$,所以一张n*n的图，方案数为$C_{2n}^n-C_{2n}^{n+1}$,化简得$Catalan(n)=\frac{1}{n+1}C_{2n}^n$
其他形式：
$Catalan(n)=\frac{1}{n+1}\sum\limits_{i=0}^n{C_n^i}^2$
$Catalan(n)=\sum\limits_{i=0}^nCatalan(i)Caltalan(n-i),Catalan(0)=1$
$Catalan(n+1)=\frac{2(2n+1)}{n+2}Catalan(n),Catalan(0)=1$
卢卡斯定理
$C_n^m \% p=C_{n/p}^{m/p} \times C_{n\%p}^{m\%p}$
具体证明很复杂，很复杂，建议先去用起来，等到数论成熟了再去用。