導數與積分
%%YCB%%
排列與組合
加法法則與乘法法則
基礎思想：分類計數使用加法，分步計數使用乘法
Cayley定理
\(n\)個有标号頂點的樹的個數為\(n^{n-2}\)
證明：定義一個消去序列，序列與樹一一對應（略）。
\(n\)元\(r\)排列：\(\frac{n!}{(n-r)!}\)
\(n\)元\(r\)組合：組合數（naive）
\(n\)元\(r\)可重排列：\(n^r\)（naive）
\(n\)元\(r\)可重組合：\(\binom{n+r-1}{r}\)
多重集\(S=\{(a_1,k_1),(a_2,k_2),...,(a_n,k_n)\}\)
多重集的全排列：\(\frac{n!}{k_1!k_2!...k_n!}\)
多重集的\(r\)組合：\(\binom{n+r-1}{r}(\forall k\ge r)\)
隔闆法、放縮法是解釋組合意義的利器
組合問題與二項式系數、格路問題的聯系
不經過對角線的格路問題方案數求解
Wallis公式與Stirling公式
Stirling公式：\(n!\backsim \sqrt{2n\pi}(\frac n e)^n\)
貌似OI不怎麼用得上？
遞推關系與母函數
母函數
對一個數列\(a_0,a_1,a_2...\)構造函數
\[G(x)=a_0+a_1x+a_2x^2+...
\]
稱為母函數，其長度可以是無窮大。
母函數的表示及求解
大部分無窮大的母函數可以寫成若幹個無窮等比數列的和
無窮等比數列求和公式：\(S=\frac{a_1}{1-q}\)（不失一般性地設\(0<q<1\)，由有窮等比數列求和\(S_n=\frac{a_1(1-q^n)}{1-q}\)将\(q^n\)看作無窮小可以推導出）
求解的一般步驟
一、寫出遞推式（形如\(a_i=f(a_{i-1})\)，記為遞推式的第\(i\)項）
二、遞推式的第\(i\)項兩邊乘上\(x^i\)，最後所有等式左右兩邊分别求和，形如
\[a_1x+a_2x^2+a_3x^3+...=f(a_0)x+f(a_1)x^2+f(a_2)x^3+...
三、通過移項、無窮等比數列求和、因式分解等變換，把上面的大等式大概寫成這樣（分子是任意一個多項式\(P(x)\)，不用在意）
\[G(x)=\frac{P(x)}{(1-q_1x)(1-q_2x)...}
四、上式可以裂項成若幹等比數列的和
\[G(x)=\frac{A_1}{(1-q_1x)}+\frac{A_2}{(1-q_2x)}+...
待定系數法，将上式通分以後，根據合并後的分子與上面的\(P(x)\)對應項的系數相等，聯立方程組解出\(A_1,A_2,...\)。
母函數的應用
寫出數列的母函數後，我們可以寫出數列的通項公式，進而快速求出數列指定項\(a_n\)的值。
既然我們可以把大部分母函數寫成等比數列和的形式，那麼我們就對于每一個等比數列，算出它的\(x^n\)的系數，最後相加即可得到\(a_n\)。
優選法
就是三分求單峰函數的極值，隻不過在區間的\(0.382\)和\(0.618\)等分點求值，這樣有一個值在下一次的時候還能用上。
利用Fibonacci數列後一項比上前一項接近\(0.618\)的性質，可以使優選法取到整點。
線性常系數齊次遞推關系
對于數列\(\{a_n\}\)有遞推式
\(a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}=0(a_0=d_0,a_1=d_1,...a_{k-1}=d_{k-1})\)
若\(\forall c,d\)都是常數，則稱上式為\(k\)階線性常系數齊次遞推關系
\(C(x)=x^k+c_1x^{k-1}+c_2x^{k-2}+...+c_{k-1}x+c_k\)稱為特征多項式。
求解
經過複雜的變換，數列的母函數一定可以寫成
\[G(x)=\frac{P(x)}{1+c_1x+c_2x^2+...+c_kx^k}
其中\(P(x)\)為一個極其複雜的最高次項不超過\(k-1\)的多項式。
分母顯然等價于\(x^kC(\frac 1 x)\)，于是考慮解方程
\[C(x)=(x-α_1)^{k_1}(x-α_2)^{k_2}...(x-α_t)^{k_t}
\(α_1,α_2,...α_t\)為\(C(x)\)在複數域内的\(t\)個根，稱為特征根。顯然可能有重根，\(k_i\)即為\(α_i\)的重複次數，于是有\(\sum\limits_{i=1}^t k_i=k\)
于是将\(k\)個\(x\)乘進分母中得出
\[G(x)=\frac{P(x)}{(1-α_1x)^{k_1}(1-α_2x)^{k_2}...(1-α_tx)^{k_t}}
開始求\(x^n\)系數\(a_n\)，三種情況隻好死記硬背
單根
設有若幹單根\(α_1,α_2,...α_k\)
直接待定系數\(A_1α_1^n+A_2α_2^n+...+A_kα_k^n\)
複根
如果出現複根，肯定是一對一對的共轭複根\(ρ(\cosθ\pm i\sinθ)\)
待定系數\(Aρ^n\cos nθ+Bρ^n\sin nθ\)
多重根
有一個\(k\)重根\(α\)
待定系數\((A_0+A_1n+A_2n^2+...+A_{k-1}n^{k-1})α^n\)
貌似也适用于單根\((k=1)\)
三種情況的待定系數式相加即為\(a_n\)的表達式
将初始值\(a_0=d_0,a_1=d_1,...a_{k-1}=d_{k-1}\)帶入\(a_n\)的表達式中，得到一個\(k\)元方程組，求解即可。
系數都求出來了，\(a_n\)當然求出來啦！
整數的拆分
運用母函數解釋
設有\(n\)個數的多重集\(\{(d_1,k_1),(d_2,k_2),...(d_n,k_n)\}\)，每個數可以任意選，那麼可以構造一母函數
\[G(x)=(1+x^{d_1}+x^{2d_1}+...+x^{k_1d_1})...(1+x^{d_n}+x^{2d_n}+...+x^{k_nd_n})
展開可得
\[G(x)=1+a_1x+a_2x^2+a_3x^3+...+a_{(\sum kd)-1}x^{(\sum kd)-1}+x^{\sum kd}
其中\(x^i\)項系數\(a_i\)為将\(i\)拆成若幹數的和的方案數。
上面讨論的是可以任意選的情況。根據題目對選擇數的限制，可以對母函數進行修改，\(x^{Ad_i}\)不存在即表示數\(d_i\)不能選\(A\)個。
Ferrers圖像
懶得解釋圖像，百度百科
利用圖像可以得到的重要性質：整數\(n\)拆分成最多不超過\(m\)個數的和的拆分數，和\(n\)拆分成最大不超過\(m\)的拆分數相等。
指數型母函數
\[G_e(x)=a_0+\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+...
稱為指數型母函數。
這個名字是怎麼來的呢？
求\(e^x\)的麥克勞林級數\(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...\)，跟指數型母函數的定義式很像
反過來說，序列\(\{1,1,1,...\}\)的指數型母函數顯然為\(e^x\)。
如果需要進行組合意義的計數，常使用指數型母函數。
常用變換
\[e^{kx}\Leftrightarrow1+kx+\frac{k^2}{2!}x^2+\frac{k^3}{3!}x^3+...
\[e^{-x}\Leftrightarrow1-x+\frac{k^2}{2!}x^2-\frac{k^3}{3!}x^3+...
\[\frac{e^x+e^{-x}}2\Leftrightarrow1+\frac{k^2}{2!}x^2+\frac{k^4}{4!}x^4+\frac{k^6}{6!}x^6...
第一類Stirling數
%%litble%%
定義為\(n\)個有差別的球劃分成\(m\)個環的方案數。用\(s(n,m)\)表示。
\[s(n,m)=(n-1)s(n-1,m)+s(n-1,m-1)
\[s(n,m)=[x^m](\prod\limits_{i=0}^{n-1}(i+x))
第二類Stirling數
%%GZY%%
定義為\(n\)個有差別的球放進\(m\)個相同的盒子中，盒子不允許為空。另一種通俗的稱呼是集合劃分數。用\(S(n,m)\)表示。
\[S(n,m)=mS(n-1,m)+S(n-1,m-1)
\[S(n,m)=\frac{1}{m!}\sum\limits_{k=0}^{m-1}(-1)^k\binom{m}{k}(m-k)^n
Catalan數
定義為通過\(n-2\)條對角線把一個凸\(n\)邊形分割的方案數。
\[C_{n+1}=\frac 1 n\binom{2n-2}{n-1}
\[C_n=\frac{(2n)!}{n!(n+1)!}
容斥原理與鴿巢原理
德摩根定理
符号約定：記\(\overline A\)為\(A\)的補集，\(|A|\)為\(A\)的元素個數。
\(\overline{A\cup B}=\overline A\cap\overline B,\overline{A\cap B}=\overline A\cup\overline B\)(naive)
容斥原理
先來直覺的
\(|A\cup B|=|A|+|B|-|A\cap B|\)
\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\)
推廣到求\(|A_1\cup A_2\cup ...\cup A_n|\)即\(|\bigcup\limits_{i=1}^nA_i|\)
設一個集合的集合\(S=\{A_1,A_2,...,A_n\}\)
那麼枚舉\(S\)的子集求并，如果這個子集大小為奇，那麼容斥系數為\(1\)，否則為\(-1\)，總的式子長這樣
\[|\bigcup\limits_{i=1}^nA_i|=\sum\limits_{i=1}^{n}|A_i|-\sum\limits_{i\neq j}|A_i\cap A_j|+\sum\limits_{i\neq j\neq k,i\neq k}|A_i\cap A_j\cap A_k|-...
類似地，還可以反過來求\(|\overline{A_1}\cap \overline{A_2}\cap ...\cap\overline{ A_n}|\)即\(|\bigcap\limits_{i=1}^n\overline{A_i}|\)
\[|\bigcap\limits_{i=1}^n\overline{A_i}|=|S|-\sum\limits_{i=1}^{n}|\overline{A_i}|+\sum\limits_{i\neq j}|\overline{A_i}\cup\overline{A_j}|-\sum\limits_{i\neq j\neq k,i\neq k}|\overline{A_i}\cup\overline{A_j}\cup\overline{A_k}|+...
莫比烏斯反演
定義一個容斥系數\(\mu(d)\)
\[\mu(d)=\begin{cases}\quad1\quad,d=1\\(-1)^k,d=p_1p_2...p_k(p是互不相同的質數)\\\quad0\quad,otherwise\end{cases}
若\(f(n),g(n)\)是定義在正整數上的個函數，滿足
\[f(n)=\sum\limits_{d|n}g(d)
則
\[g(n)=\sum\limits_{d|n}\mu(d)f(\frac n d)
鴿巢原理/抽屜原理
\(n\)個抽屜裡有\(n+1\)個蘋果，則至少有一個抽屜裡有兩個蘋果（naive）
群論
跳過群的基本概念吧，反正計數又用不着。
置換群
所有的有限群都可以用置換群表示。
置換的定義：一個\(n\)元置換是一個排列二進制組，一般寫成
\[p=\begin{pmatrix}1&2&3&...&n\\a_1&a_2&a_3&...&a_n\end{pmatrix}
表示把序列中的\(i\)号元素替換為\(a_i\)号元素。
第一行不一定要寫成\(1-n\)，将列任意交換得到的仍是原來的置換。
Burnside引理
\(L=\frac{1}{|G|}\sum\limits_{p\in G}不動點個數(p)\)
Pólya定理
定義\(k\)階循環為一個序列\((b_1,b_2,...b_k)\)，滿足在置換中\(a_{b_1}=b_2,a_{b_2}=b_3,...a_{b_k}=a_1\)
于是一個置換可以寫成若幹個循環的組合，比如
\[p=\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}
可以寫成兩個循環\((1,2,4)(3,5)\)的形式。
如果\((b_1,b_2,...b_{k-1},b_k)\)與\((b_2,b_3,...b_k,b_1)\)視為等價的話，那麼可以說每一個置換都有唯一的一個循環表示。
記\(c_p\)為置換\(p\)循環表示下循環的總數。在置換群\(G\)的意義下用\(m\)種顔色染物品，其方案數為\(\frac{1}{|G|}\sum\limits_{p\in G}m^{c_p}\)。
![51Nod-1742-開心的小Q[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)