水表
Tony102
andysj
wangrx
xxbbkk
YZHX
CJzjy
凉城無愛
Lumos壹玖贰壹
Lead in
组合数学（Combinatorial mathematics），又称为离散数学。广义的组合数学就是离散数学，狭义的组合数学是离散数学除图论、代数结构、数理逻辑等的部分。
狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等。
核心内容：用算法处理离散对象。
基础
加法原理，乘法原理。
排列：\(A_n^m=\frac{n!}{(n-m)!}\)
（从\(n\)个元素中选\(m\)个元素排列）
组合：\(C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\)
常用\(\binom{n}{m}\)表示。
二项式定理：
\[(a+b)^n=\sum\limits^{n}_{i=0}\binom{n}{i}a^{n-i}b_i \]基础式子
好吧其实一点也不基础
斯特林数
第二类斯特林数
\[\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix} \] \[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} \]第一类斯特林数
\[\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix} \]上升幂，下降幂与普通幂
\[x^{\overline{n}}=\sum_{k=0}^n \begin{bmatrix}n\\ k\end{bmatrix} x^k \] \[x^n=\sum_{k=0}^n \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} \] \[x^n=\sum_{k=0}^n \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}} \] \[x^{\underline{n}}=\sum_{k=0}^n \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k \]好像是用数学归纳法证明。
不会整
贝尔数
\[B_n=\sum_{k=0}^n \begin{Bmatrix}n\\ k\end{Bmatrix} \]还有贝尔三角形，在平常可以看数字猜结论
一点容斥
不会细讲，来几个模型。
不定方程非负整数解计数
给定方程\(\sum\limits_{i=1}^nx^i=m\)和\(n\)个限制条件\(x^i\leq b_i\) ，求解的个数。
Easy:去掉限制
\[ans=C^{n-1}_{m+n-1} \]插板法。
加入\(n-1\)个球，问题变为在\(m+n-1\)个球中选\(n-1\)个球，这\(n-1\)个球把序列分为\(n\)份，每份对应一个\(x^i\) 。
Hard:\(x^i\leq b^i\)
正难则反。
\[ans=\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right| \]把上界限制转化为下界限制，把下界减掉，就可以啦。
枚举限制条件的子集\(a\) 。
求解
\[\sum_{i=1}^nx_i=m-\sum_{i=1}^k(b_{a_i}+1) \]最后减掉。
例题：[HAOI2008 硬币购物]。
经典错排
递推：
\[d_i=(i-1)(d_{i-1}+d_{i-2}) \]容斥：
\[d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!} \]Min-max容斥
\[\max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}} \] \[\min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}} \]最为难得的是，它在期望意义下成立。
\[E\left(\max_{i\in S}{x_i}\right)=\sum_{T\subseteq S}{(-1)^{|T|-1}E\left(\min_{j\in T}{x_j} \right)} \] \[E\left(\min_{i\in S}{x_i}\right)=\sum_{T\subseteq S}{(-1)^{|T|-1}E\left(\max_{j\in T}{x_j} \right)} \] \[\underset{i\in S}{\operatorname{lcm}}{x_i}=\prod_{T\subseteq S}{\left(\gcd_{j\in T}{x_j} \right)^{(-1)^{|T|-1}}} \]没了
”欧拉数“
在计算组合中，欧拉数（Eulerian Number）是从\(1\)到\(n\)中正好满足\(m\)个元素大于前一个元素（具有 \(m\)个“上升”的排列）条件的排列 个数。定义为：
\[A(n, m) = \langle \begin{aligned} & n \\ & m - 1 \\ \end{aligned} \rangle \]本来以为是个很有意思的的东西的，直到我看到他的难度。。。
CF Easy3100，CF Hard3500，UOJ的题AC代码不超过十个而且长度都在11k以上。。。劝退。
题目
热身题
求：
\[(\sum\limits_{i=0}^n\sum\limits_{j=0}^i(C_n^m\%2))\% P \]