组合数学课

先是在wiki上找了一下组合数学的词条. 发现涵盖的东西居然这么多. 有机会再看. 这篇只是用来总结课堂的一些知识.

鸽巢原理

定理: 把 n+1 个物体放在 n 个盒子里, 至少有一个盒子里有两个以上的物体.

定理: 鸽巢定理推广. $q_1, q_2, \ldots, q_n \in \mathbb{Z^+}$ , 把 $\sum_i q_i - n + 1$ 个物体放入 $n$ 个盒子, 第一个盒子至少 $q_1$ 个物体, 或者第二个盒子中至少有 $q_2$ 个物体, … , 或者第 n 个盒子中至少有 $q_n$ 个物体.

这两个定理用反证法很容易证明.

课本前半部分都是一些很古典的组合数学问题. 用物体, 盒子等定义不明的语言描述.

这里试着用集合论语言描述一下.

物体集合 O (object), 可数集合

盒子/标签 集合 T (type), 可数集合.

一个方案/安排 a (arrangement), 是一个映射 $a \in O \to C$, $O \to C$ 表示所有值域为 $O$, 定义域为 $C$ 的映射的集合.

所有方案$A = O \to C$, 许多问题问的就是 $|A|$.

鸽巢定理: $|O| = n+1$, $|T| = n$, 记 $A = O \to T$ $\forall a \in A$ , $\exists t_0 \in T$, $|a^{-1}(t_0)| > 1$

这里用映射的逆表示从值域映射到定义域集合的一个映射.

不得不说, 这么写的话, 定理的含义模糊了很多. 定理的成立也不那么明显了.

Ramsey 数

略

排列与组合

加法乘法原则

加法原则: 事件 A 有 m 种选取方式, 事件 B 有 n 种选取方式, 则选择 A 或 B, 有 m + n 中选取方式.

这有什么意义? 太显然了.. 一个事件A 有 m 种选取方式是什么意思? 这里并不涉及上面提到的 Object 和 Type. (因为一时想不到答案.. 走神看QQ去了..). 加法原则可以看做是单纯的集合相加. 看下面的乘法原则吧.

乘法原则: 事件 A 有 m 种选取方式, 事件 B 有 n 种选取方式, 选取 A 然后选取 B 有 mn 中选取方式

这不也仅仅是集合相乘吗..

减法原则, 除法原则

集合的排列

n 元集合 S 的一个 r 排列是指从 S 中选 r 个元素, 依次排列. 方案数记为 $P(n,r)$

$P(n, r) = \frac{n!}{(n-r)!}$

集合组合

n 元集合 S 的 r 组合是指从 S 中选取 r 个元素的无序选择. 方案数记为 $\binom{n}{r}$. or $C_n^r$

$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

这个是 S 集合的大小为 r 的子集的个数

多重集合的排列

多重集合里面可能会有相同元素, 比如 $M = \{a,a,a,b,c,c,d,d,d,d\}$ = $\{3\cdot a, 1\cdot b, 2 \cdot c, 4 \cdot d\}$

一般把多重集合记为 $M = \{k_1\cdot a_1, k_2\cdot a_2, \ldots, k_n \cdot a_n\}$,

定理 多重集合 $M = \{\infty\cdot a_1, \infty\cdot a_2, \ldots, \infty \cdot a_k\}$ 的 r 排列数为 $k ^ r$

这个..勉勉强强吧

定理 多重集合$M = \{k_1\cdot a_1, k_2\cdot a_2, \ldots, k_n \cdot a_n\}$ 的全排列数为

$\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n! }$

多重集合的组合

定理 多重集合 $M = \{\infty\cdot a_1, \infty\cdot a_2, \ldots, \infty \cdot a_k\}$ 的 r 组合数为 $\binom{k+r-1}{r}$, 另一种描述 将 r 个相同的求放入 k 个不同的盒中.

定理 多重集合 $M = \{\infty\cdot a_1, \infty\cdot a_2, \ldots, \infty \cdot a_k\}$ 要求 $a_1, \ldots, a_k$ 至少出现一次的 $r$ 组合数为 $\binom{r-1}{k-1}$

高中时的”隔板法”

二项式定理

二项式定理 $(x + y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y ^r$

二项式定理 $,(1+x)^{\alpha} = \sum_{r=0}^{\infty}\binom{\alpha}{r} x^r$ for all $\alpha \in \mathbb{R}$ , $\binom{\alpha}{r} = \frac{\alpha(\alpha -1)\ldots(\alpha-r+1)}{r!}$

(1) 当 $\alpha= - n$,

\begin{align} \binom{\alpha}{r} & = \binom{-n}{r} \\ &= \frac{(-n)(-n-1)\ldots(-n-r-1)}{r!} \\ &= (-1)^r\binom{n+r-1}{r} \end{align}

so, $(1+x)^{-n} = \sum_{r=0}^{\infty}(-1)^r \binom{n+r-1}{r} x^r$

(2) 当 $\alpha = \frac{1}{2}$,

\begin{align}\binom{\alpha}{r} &= \binom{\frac{1}{2}}{r} \\ &=\frac{\frac{1}{2}(\frac{1}{2}-1)\ldots(\frac{1}{2}-r+1)}{r!}\\&=(-1)^{r-1}\cdot\frac{1}{r2^{2r-1}}\binom{2r-2}{r-1} \end{align}

so, $(1+x)^\frac{1}{2} = \sum_{r=0}^{\infty}(-1)^{r-1}\frac{1}{r2^{2r-1}}\binom{2r-2}{r-1}x^r$

$\binom{n}{r}$ 的一些基本性质:

1. 对称
2. 递推关系
3. 单峰(中间最大)
4. 可以看做在杨辉三角中, 从顶点走到$\binom{n}{r}$ 点的所有路径数.

恒等式:

1. $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n} = 2^n$
2. $\binom{n}{i}$ 所有偶数项求和等于所有奇数项
3. $1\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \ldots + n\binom{n}{n} = n2^{n-1}$, 证明: $(1+x)^n$ 在 $x=1$ 处求导.
4. $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$
5. $\binom{0}{k}+\binom{1}{k} + \ldots + \binom{n}{k} = \binom{n+1}{k+1}$, 组合意义,
6. $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \ldots + \binom{n}{n}\binom{n}{0}= \binom{2n}{n}$, 组合意义
7. $\sum_{i=0}^{r}\binom{m}{i}\binom{n}{r-i} = \binom{m+n}{r}$ , Vandermonde 恒等式, 上式的推广
8. $\sum_{i=0}^{m}\binom{m}{i}\binom{n}{r+i} = \binom{m+n}{m+r}$,

多项式定理

$(x_1+ x_2+ \ldots + x_t)^n = \sum\binom{n}{n_1n_2\ldots n_t}x_1^{n_1}x_2^{n_2}\ldots x_t^{n_t}$

多项式系数 $\binom{n}{n_1n_2\ldots n_t} = \frac{n!}{n_1!n_2!\ldots n_t!}$

容斥定理

$S$ 是有限集合, $P_1 ,P_2,\ldots,P_m$ 是有关 $S$ 元素的性质, $A_i$ 是 $S$ 中具有 $P_i$ 性质的元素组成的集合, 则 $S$ 中不具有性质 $P_1,\ldots,P_m$ 的元素个数为:

$|\overline{A_1} \cap \overline{A_2} \cap \ldots \cap \overline{A_m}| = |S| - \sum|A_i| + \sum|A_i\cap A_j| - \sum|A_i\cap A_j \cap A_k| + \ldots + (-1)^m |A_1\cap A_2 \cap \ldots \cap A_m|$

错排问题

1,2,…,n, 的一个错排指满足每个数不在原位置的全排列.

错排数$D_n = n!(1 - \frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\ldots+(-1)^n\frac{1}{n!})$

证明方法1. 容斥定理 $P_i$ 为 i 在原位置上. 2. 递推公式

有禁止模式的排列问题

容斥原理, $P_i$ 为有某个禁止模式的排列

生成函数

定义

$A(x) = a_0 + a_1x + a_2x^2 + \ldots$ 为序列 $a_0, a_1, a_2, \ldots$ 的生成函数.

加法, 对应项相加 $A(x)+B(x) \equiv \sum_{k=0}^\infty (a_k + b_k)x^k$

乘法, 相乘后合并同次项 $A(x)B(x) \equiv \sum_{k=0}^{\infty} (a_kb_0+a_{k-1}b_1+ \ldots + a_0b_k)x^k$

加法零元: 0, 0, 0, …

乘法单位元: 1, 0, 0, …

形式多项式集合 $R[[x]]$ 构成一个整环.

求导

生成函数的性质

一些计算规则和例子

$b_k = \sum_{i=0}^k a_i$ $\iff$ $B(x) = \frac{A(x)}{1-x}$

$b_k=\sum_{i=k}^\infty a_i \iff B(x) = \frac{A(1)-xA(x)}{1-x}$

$b_k = ka_k \iff B(x) = xA'(x)$

$b_k=\frac{a_k}{k+1} \iff B(x) = \frac{1}{x}\int_0^xA(t)\,\mathrm{d}t$

组合型分配问题的生成函数

$\{\infty a_1, \infty a_2, \ldots, \infty a_n\}$, 的 $k$ 组合数

其生成函数 $A(x) = (\sum_{i=0}^\infty x^i )^n$ , 每个因子 $\sum_{i=0}^\infty x^i$ 表示一个 a_i 可取的个数, 生成函数的 $k$ 次项就是 $k$ 组合数.

$A(x) = \frac{1}{(1-x)^n}$, $a_k = \binom{n-1+k}{k}$

排列型分配问题的指数型生成函数

指数型生成函数.

数列 $a_i$, 的指数型生成函数为 $\sum_{k=0}^\infty a_k \frac{x^k}{k!}$

正整数拆分

递推关系

常系数线性齐次递推关系

常系数线性非齐次

迭代归纳法

生成函数求解递推关系

特殊计数序列

fibonacci

catalan

集合划分 stirling

分配问题

Polya 计数

群

非空集合$G$ 以及在上面的二元运算 $\cdot$, 满足以下条件

1. 运算封闭
2. 结合律成立
3. 存在单位元
4. 每个元素都存在逆元

则称 $\langle G, \cdot \rangle$ 为群.

由以上几条,可以证明的一些性质:

设$\langle G, \cdot \rangle$ is a group, $e$ is the identity element. then:

1. $e^{-1} = e$
2. $e$ is unique
3. 消去律成立, if $a \cdot b = a \cdot c$ or $b \cdot a = c \cdot a$ then $b = c​$
4. $(a \cdot b)^{-1} =b^{-1} \cdot a^{-1}$

定义子群, 设 $\langle G, \cdot \rangle$ is a group, and $H$ is a non-empty subset of $G$, if $\langle H, \cdot \rangle$ is a group, we call it $G$‘s subgroup

一些性质包括, 只要 $H$ 中运算封闭, $\langle H, \cdot \rangle$ 就是子群.

置换群

有限集合$D$ 上的 一一映射 成为 $D$ 上的置换. 不失一般性, $D=\{1,2,\ldots, n\}$

一个置换

$\sigma = \left ( \begin{array}{cccc}1&2 &\ldots & n\\ \sigma(1) &\sigma(2) &\ldots & \sigma(n)\end{array} \right )$

将1 映射到 $\sigma(1)$, 以此类推.

$D = \{1, 2,\ldots, n\}$ 的所有置换构成一个群, 记为$S_n$, $\big|S_n\big| = n!$

$(1,4,6)$ 这种叫轮换, $1\to4, 4\to 6, 6 \to 1$, 其他不变. 举个例子, 轮换的复合运算: $(1234)(1234) = (13)(24)$

任意置换都可以表示为不相交的轮换之积.

$D$ and $R$ are two finite sets, $F = D \to R$, $G$ is a Permutation Group on D, for some $f1_1, f_2 \in F$, if there exists $\sigma \in G$, s.t. forall $d \in D$, $f_1(d) = f_2(\sigma(d))$ We call $f_1$ and $f_2$ are $G$ equal ($G$ 等价)

两个映射 $f_1$, $f_2$ 在 置换群$G$ 上等价, 如果存在一个定义域上的一一映射, 把定 义域的元素用这个映射换一下 $f_1$ 就是 $f_2$.

显然这个关系是$F$ 上的一个等价关系 (和 $G$ 好像并没有什么关系)?

并不是和$G$ 没有关系哟. 如果给定一个置换群G, 那么就能把 $F, (F = D \to R)$ 划分成 多个等价类.

对应到组合问题中, 比如一个着色方案, 一个分配方案, 实际上就是一个$F = D \to R$, 着色方案的话, $D$ 是定点, $R$ 是颜色. 分配方案的话, $D$ 是小球, $R$ 是盒子.

给定一个置换群$G$, 等价类的个数就是实际的组合方案数.

Burnside 引理

定义两个置换的共轭:

$G$ is subgroup of $S_n$, two elements $s, t \in S_n$, if there exists a $g \in G$, s.t. $s = g^{-1} t g$, then we say $s$ is a conjugate of $t$, and that viceversa, or $s$ and $t$ of $G$ are conjugate.

G-conjugate, G共轭是 $S_n$ 上的一个等价关系. G共轭当且仅当, 两个置换是同型的.

定义同型:

映射的等价类

Burnside引理 可以解决用m色对n个物体着色的方案计数问题, 但是计算量太大, 经过 Polya 改进形成 Polya 计数定理后才得到广泛应用.

组合设计