# 期末复习

## 1 - 基本计数

balls per binany$$\leqslant 1$$$$\geqslant 1$$
$$n$$ distinct balls, $$m$$ distinct bins$$m^n$$$$(m)_n$$$$m!{n \brace m}$$
$$n$$ identical balls, $$m$$ distinct bins$$\left({m \choose n}\right)$$$${m \choose n}$$$${n-1 \choose m-1}$$
$$n$$ distinct balls, $$m$$ identical bins$$\sum\limits_{k=1}^{m} {n \brace k}$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$${n \brace m}$$
$$n$$ identical balls, $$m$$ identical bins$$\sum\limits_{k=1}^m p_k(n)$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$$p_m(n)$$

• 二项式系数 ${n \choose k} = \dfrac{n!}{k!(n-k)!}$
• $$n$$个不同的篮子放$$k$$个不同的球，每个篮子最多一个（单射、$$n$$的$$k$$个元素的排列）： $(n)_k = \begin{cases} \dfrac{n!}{(n-k)!} & k \leqslant n, \\ 0, & k > n. \end{cases}$
• $$n$$个不同的篮子放$$k$$个相同的球（$$n$$大小集合的$$k$$-multiset，一个球代表对应的元素出现一次；插板法）： $\left({n \choose k}\right) = {n+k-1 \choose n-1} = {n+k-1 \choose k}$
• $$n$$个相同的篮子放$$k$$个不同的球，每个篮子至少一个球（集合划分成恰好$$k$$份，考虑最后一个元素加入前$$k$$个子集或者单独成一个子集）： ${n \brace m} = k{n-1 \brace k} + {n-1 \brace k-1}$
• $$n$$个相同的篮子放$$k$$个相同的球，每个篮子至少一个球（整数划分成恰好$$k$$份）：
• $$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$$（考虑所有项都大于1或者把1去掉）
• $$p_k(n) = \sum\limits_{j=1}^k p_j(n-k)$$（把整数$$n$$划分成$$k$$份等价于划分成若干份，其中最大值为$$k$$）

## 2 - 生成函数

• 写出$$a_n$$的递归定义（如$$a_n = a_{n-1} + a_{n-2}$$）
• 两边同时乘以$$x^n$$，左边即为生成函数$$G(x)$$，并将右边化为$$G(x)$$的形式
• 求解$$G(x)$$，得到关于$$x$$的函数
• 对$$G(x)$$进行级数展开，得到$$a_n$$
• 泰勒展开：$$G(x) = \sum\limits_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n$$
• 几何级数展开：$$\dfrac{1}{1-z} = \sum\limits_{n \geqslant 0} z^n$$
• Newton's Formula：$$(1+x)^\alpha = \sum\limits_{n \geqslant 0} {\alpha \choose n} x^n$$

• shift：$$x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n$$
• addition：$$F(x) + G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n$$
• convolution：$$F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{n=0}^k f_k g_{n-k} x^n$$
• differentiation：$$G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n$$

## 3 - 筛法

$|A_1 \cup \dots \cup A_2| = - S_0 + S_1 - S_2 + S_3 + \dots + (-1)^{n-1} S_n$ $|\bar{A_1} \cap \dots \cap \bar{A_2}| = S_0 - S_1 + S_2 - S_3 + \dots + (-1)^{n} S_n$

$$[n]$$到$$[m]$$的满射的数量：

• 定义坏事件$$A_i$$为$$[m]$$中的$$i$$不在值域中，有$$|A_i| = (m-1)^{n}$$个映射满足条件，
• 定义坏事件$$A_I$$为$$[m]$$中的子集$$I$$不在值域中，$$|A_i| = (m-|I|)^{n}$$，
• 带入筛法得到满射的数量是$$\sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n$$。

${n \brace m} = \dfrac{1}{m!}\sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n$

• 定义坏事件$$A_I$$为在新排列中$$I$$中元素的位置没变，有$$(n-|I|)!$$种排列
• 带入求得错排的个数约为$$\dfrac{n!}{e}$$

• 将排列转换为一组二维坐标
• 假设$$B$$是一个不符合条件的位置的集合
• $$r_k$$表示在$$B$$中选$$k$$个不同的位置的方法
• 则满足条件的$$n$$排列的个数为$$N_0 = \sum\limits_{k=0}^n (-1)^k r_k (n-k)!$$

Polya计数法不考

## 5 - Cayley公式

$$n$$个不同的点组成的树的个数为$$n^{n-2}$$。

Repeatedly remove $$u_i$$ from tree $$T_i$$ to get $$T_{i+1}$$, where $$u_i$$ is the smallest leaf in $$T_i$$. $$u_i$$ has only one edge $$(u_i, v_i)$$, we get Prufer code for $$T$$ with all $$v_i$$s.

2       5
|      /
4--3--1
|   \
6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7


E.g. the tree above has prufer code $$(4,3,1,3,1,7)$$.

For each $$i$$, the edge $$(u_i, v_i)$$ can be determined because $$u_i$$ is the smallest number not in $$\lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace$$.

• 双重计数（数两遍）
• 编码与解码（将一棵树转换为一个编码）
• 构造双射求出个数

## 6 - 存在性问题

• 组合中存在两个数可以互相整除（考虑2的幂次）
• 单调增/减序列（将最长增/减序列的长度转换为二维坐标）
• Dirichlet's approximation：将$$[0, 1]$$划分为$$n$$个区间，填入$$n+1$$个数

## 7 - 概率法

Theorem: Let $$G(V, E)$$ be a graph on $$n$$ vertices with $$m$$ edges. Then $$G$$ has an independent set with at least $$\dfrac{n^2}{4m}$$ vertices.

• 设计事件
• 边的方向以$$1 / 2$$的概率随机
• 点/边以$$p$$为概率被选入集合中（此后求解使期望最小/大的$$p$$值）
• 求解概率
• 直接计算概率，可能会用到$$(1-p)^x = e^{-px}$$
• 利用$$E \left[ \sum\limits_{i=1}^n a_i X_i \right] = \sum\limits_{i=1}^n a_i \cdot E[X_i]$$求随机变量的期望

Lovasz Local Lemma：

• 条件1：对任意的$$i$$，$$Pr[A_i] \leqslant p$$
• 条件2：事件的依赖图中的最大度数为$$p$$，且$$ep(d+1) \leqslant 1$$
• 则$$Pr\left[ \bigwedge\limits_{i=1}^n \bar{A_i} \right] > 0$$

## 8 - 极值图论

Mantel's Theorem: Suppose $$G(V, E)$$ is a graph on $$n$$ vertices without triangles, then $$|E| \leqslant \dfrac{n^2}{4}$$.

Turan's Theorem: Let $$G(V, E)$$ be a graph with $$|V| = n$$. If $$G$$ has no $$r$$-clique, $$r \geqslant 2$$, then $$|E| \leqslant \dfrac{r-2}{2(r-1)} n^2$$.

## 9 - 极值集合论

If $$\mathcal{F} \subseteq {[n] \choose k}$$ and $$|\mathcal{F}| > k!(r-1)^k$$, then there exists a sunflower $$\mathcal{G} \subseteq \mathcal{F}$$ such that $$|\mathcal{G}| = r$$.

$n \geqslant 2k \ \Longrightarrow \ |\mathcal{F}| \leqslant {n-1 \choose k-1}$

Theorem (Sperner 1928): For any antichain $$\mathcal{F}$$,

$|\mathcal{F}| \leqslant {n \choose \lfloor n/2 \rfloor}.$

## 10 - Ramsey理论

Define $$R(k, l)$$ as the smallest integer satisfying: if $$n \geqslant R(k, l)$$, for any 2-coloring of $$K_n$$ there exists a red $$K_k$$ or a blue $$K_l$$.

Ramsey Theorem:

• $$R(k, l)$$ is finite.
• $$R(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k)$$ is finite.

Theorem (Erdos-Szekeres 1935): $$\forall m \geqslant 3$$, $$\exists N(m)$$ such that any set of $$n \geqslant N(m)$$ points in the plane with no three on a line, contains $$m$$ points that are the vertices of a convex $$m$$-gon. （凸$$m$$边形）

$N(m) = R_3(2; m, m)$

## 11 - 匹配论

System of distince representatives (SDR) for a sequence of sets $$S_1, S_2, \dots, S_m$$ is a sequence of distince elements $$x_1, x_2, \dots, x_m$$ such that $$x_i \in S_i$$.

Hall's Theorem: The sets $$S_1, S_2, \dots, S_m$$ have a system of distince representatives (SDR) if and only if $$\left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I|$$ for all $$I \subseteq [m]$$.

The condition $$\left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I|$$ is called the Hall's condition.