部分初赛数学知识点整理

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

1.主定理

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

对于一个递归式 T(n)=aT(nb)+f(n)T(n)=aT(\frac{n}{b})+f(n)
c=logbac=log_ba,f(n)=O(nk)f(n)=O(n^k)O(nklog)O(n^klog)(例如在f(n)=nlognf(n)=nlogn时,k=1k=1

1.当c>kc>k时,T(n)=O(nc)T(n)=O(n^c)
2.当c=kc=k,且T(n)=aT(nb)+f(nklogpn)T(n)=aT(\frac{n}{b})+f(n^klog^pn)(logpnlog^pnlognlognpp次方)时,T(n)=O(nclogp+1n)T(n)=O(n^clog^{p+1}n)
3.当c<kc<k时,T(n)=O(f(n))T(n)=O(f(n))

2.各种数

等比数列通项公式:an=a1qn1a_n=a_1*q^{n-1}

卡特兰数:hn=C2nnn+1h_n=\frac{C^n_{2n}}{n+1}

错位排列:
通项式:D(n)=1n!(111!+12!13!+...+(1)n1n!)D(n)=\frac{1}{n!}(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n*\frac{1}{n!})

递推式:Dn=(n1)(Dn1+Dn2),D1=0,D2=1D_n=(n-1)*(D_{n-1}+D_{n-2}),D_1=0,D_2=1

各种组合:
1.从nn个数中选取kk个数,每个数可被重复选取的方案个数:Cn+k1kC_{n+k-1}^k

2.a1+a2+...+an=ma_1+a_2+...+a_n=m的正整数解的个数(将mm件物品分给nn个人,不允许有人为空的方案数):Cm1n1C_{m-1}^{n-1}

3.a1+a2+...+an=ma_1+a_2+...+a_n=m的非负整数解的个数(将mm件物品分给nn个人,允许有人为空的方案数):Cn+m1m1C_{n+m-1}^{m-1}