组合数学

期末复习

2020-01-03 19:40 CST
2020-01-04 14:52 CST
CC BY-NC 4.0

1 - 基本计数

balls per bin any $\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 - 生成函数

普通生成函数:$G(x) = \sum\limits_{n \geqslant 0} a_n x^n$

求解生成函数的四步方法:

  • 写出$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$

卡特兰数:$C_0 = 1$,$C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} = \dfrac{1}{n+1} {2n \choose n}$

3 - 筛法

集合求并:$\left\vert \bigcup\limits_{i=1}^n A_i \right\vert = \sum\limits_{I \subseteq [n]} (-1)^{|I|-1} \left\vert \bigcap\limits_{i \in I} A_i \right\vert$

记$S_k = \sum\limits_{|I|=k} |A_I|$,则有

$$|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 - 存在性问题

鸽笼原理:将$mn$个物体分到$n$个类别中,有些类别有多于$m$个物体。

  • 组合中存在两个数可以互相整除(考虑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.

证明某些事件都(不)发生的概率$> 0$,从而证明存在。

  • 设计事件
    • 边的方向以$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 - 极值集合论

Sunflower Lemma (Erdos-Rado 1960):

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$.

Erdos-Ko-Rado Theorem:

$$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.