期末复习

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 - 生成函数

普通生成函数:\( 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.