部分初赛数学知识点整理

tty实在是太菜了，他需要把自己学到的各种东西整理一下/kk

1.主定理

原文，整理的有自己的理解，不保证严格符合原定义

对于一个递归式 $T(n)=aT(\frac{n}{b})+f(n)$
令$c=log_ba$,$f(n)=O(n^k)$或$O(n^klog)$（例如在$f(n)=nlogn$时，$k=1$）

1.当$c>k$时，$T(n)=O(n^c)$
2.当$c=k$，且$T(n)=aT(\frac{n}{b})+f(n^klog^pn)$($log^pn$即$logn$的$p$次方)时，$T(n)=O(n^clog^{p+1}n)$
3.当$c<k$时，$T(n)=O(f(n))$

2.各种数

等比数列通项公式：$a_n=a_1*q^{n-1}$

卡特兰数：$h_n=\frac{C^n_{2n}}{n+1}$

错位排列：
通项式：$D(n)=\frac{1}{n!}(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n*\frac{1}{n!})$

递推式：$D_n=(n-1)*(D_{n-1}+D_{n-2}),D_1=0,D_2=1$

各种组合：
1.从$n$个数中选取$k$个数，每个数可被重复选取的方案个数：$C_{n+k-1}^k$

2.$a_1+a_2+...+a_n=m$的正整数解的个数（将$m$件物品分给$n$个人，不允许有人为空的方案数）：$C_{m-1}^{n-1}$

3.$a_1+a_2+...+a_n=m$的非负整数解的个数（将$m$件物品分给$n$个人，允许有人为空的方案数）：$C_{n+m-1}^{m-1}$