鸽巢原理
将\(n+1\)个球放入\(n\)个盒子，至少有一个盒子里有两个球
\(\large\mathrm{Ext.}\) 将\(\sum_{1\le k \le n}q_k-n+1\)个球放入n个盒子
- 要么第一个盒子有至少\(q_1\)个
- 要么第二个盒子有至少\(q_2\)个
- 要么第三个盒子有至少\(q_3\)个
- ...
- 要么第\(n\)个盒子有至少\(q_n\)个
- （上述条件至少满足一个）
平均值原理
对于\(n\)个变量\(x_1,x_2,...,x_n\)，最小值小于等于平均值，最大值大于等于平均值，当且仅当\(x_1=x_2=x_3=..=x_n\)取等
\(\text{Ramsey}\) 定理
\(6\)个人中，要么有\(3\)个人互相认识，要么有\(3\)个人互相不认识。
一般地，有：对于\(\forall n,m \in \mathbf{N^*}\)，存在一个\(N\),使得给\(K_N\)的边任意染色后，要么存在全为蓝色的\(K_m\)，要么存在全为红色的\(K_n\)。此\(N\)记为\(\mathrm{R}(n,m)\)。如\(\mathrm{R}(3,3)=6\)。
另外，该定理也可以推广到高维，但是好像没什么用。
二项式系数
组合恒等式
一行的和：
\[\sum_k \dbinom{n}{k}=2^n\]
分奇偶
\[\sum_k (-1)^n\dbinom{n}{k}=(1-1)^n=[n=0]\]
提取/吸收恒等式
\[\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1} \Rightarrow m\dbinom{n}{m}=n\dbinom{n-1}{m-1}\]
组合意义：考虑每个元素被选出一次贡献为\(1\)，则大小为\(m\)的集合贡献为\(m\)。单独考虑每个元素，总的贡献为\(n\dbinom{n-1}{m-1}\)；考虑每个选出的集合，总的贡献为\(m\dbinom{n}{m}\)。二者应该相等。
上指标求和
\[\sum_{i\le n}\dbinom{i}{a}=\sum_{i\le n}\dbinom{i+1}{a+1}-\dbinom{i}{a+1}\]
平行求和法
\[\sum_{k\le n}\dbinom{r+k}{k}=\sum_{k\le n}\dbinom{r+k}{r}=\dbinom{r+n+1}{r+1}=\dbinom{r+n+1}{n}\]