二项式定理
\[(x+y)^{n}= \sum_{k=0}^{n} {n\choose k} x^{k} y^{n-k}
\]
二项式反演
\[f_{n}=\sum_{i=0}^{n} {n\choose i}g_{i} \Leftrightarrow g_{n}=\sum_{i=0}^{n} (-1)^{n-i} {n\choose i} f_{i}
\]
其中 \(f_i\) 为至多选 \(i\) 个的方案数,\(g_{i}\) 为恰好选 \(i\) 个的方案数。
\[f_{n}=\sum_{i=n}^{m} {i\choose n}g_{i} \Leftrightarrow g_{n}=\sum_{i=n}^{m} (-1)^{i-n} {i\choose n} f_{i}
\]
其中 \(f_i\) 为钦定选 \(i\) 个的方案数,\(g_{i}\) 为恰好选 \(i\) 个的方案数。
范德蒙德卷积
\[\sum_{i=0}^{k} {n\choose i} {m\choose k-i}={n+m\choose k}
\]
推论:
\[\sum_{i=0}^{n} {n\choose i}^{2}={2n\choose n-i}
\]
\[\sum_{i=0}^{n} {n\choose i}{n\choose i-1}={2n\choose n+1}
\]
\[\sum_{i=0}^{m} {n\choose i}{m\choose i}={n+m\choose m}
\]
第二类斯特林数
递推式:
\[{n\brace 0}=[n=0]
\]
\[{n\brace m}={n-1\brace m-1}+m{n-1\brace m}
\]
通项公式:
\[{n\brace m}=\sum_{i=0}^{m} \frac{(-1)^{m-i} \,i^n }{i!(m-i)!}
\]
k部分拆数
\[p(n,k)=\sum_{i=0}^{k} p(n-k,i) \Rightarrow p(n,k)=p(n-1,k-1)+p(n-k,k)
\]
(未完工...)