组合学笔记

偶然间发现了所谓的de Bruijn的组合学的课堂笔记, 我有点好奇, 遂读之.

第1章 引论

第2章 生成函数

组合学中一个非常古老的想法是生成函数, 其可以追溯至Laplace.

给定一无穷数列 $$a_0,a_1,a_2,\dots$$ 其生成函数为以下级数 $$A(x)=a_0+a_{1}x+a_2{x}^2+\cdots$$

生成函数这种技术的想法在于 $$\begin{array}{ccc}\begin{array}{|c|}\hline \text{关于序列的知识}\\ \hline\end{array}& \stackrel{\text{向前转换}}{\to }& \begin{array}{|c|}\hline \text{关于}A(x)\text{的知识}\\ \hline\end{array}\\ & & \downarrow \text{各种操作}\\ \begin{array}{|c|}\hline \text{更多关于序列的知识}\\ \hline\end{array}& \underset{\text{向后转换}}{\leftarrow }& \begin{array}{|c|}\hline \text{更多关于}A(x)\text{的知识}\\ \hline\end{array}\end{array}$$ 这有点像是Laplace积分 $$F(x)={\int }_0^{\infty }{e}^{xt}f(t)dt$$ 其想法在于 $$\begin{array}{ccc}\begin{array}{|c|}\hline \text{关于}f\text{的微分方程}\\ \hline\end{array}& \stackrel{\text{Laplace变换}}{\to }& \begin{array}{|c|}\hline \text{关于}F\text{的代数方程}\\ \hline\end{array}\\ & & \downarrow \text{求解代数方程}\\ \begin{array}{|c|}\hline \text{关于}f\text{的微分方程的解}\\ \hline\end{array}& \underset{\text{向后转换}}{\leftarrow }& \begin{array}{|c|}\hline \text{关于}F\text{的代数方程的解}\\ \hline\end{array}\end{array}$$

我们可用三种方式为这把戏 (hocus-pocus) 进行辩护

1. 作为启发式 (heuristic). 反正我们得到了结果, 不论是怎么得到的. 之后我们可以验证其正确与否, 比如说这种情况下我们可以使用数学归纳法.
2. 通过收敛幂级数的理论. 我们可以将$A$视为一个定义在$ℂ$平面中的零点的某个小邻域上的解析函数. 这可以澄清我们对于$A$施行的计算. 问题在于我们需要检视其收敛性, 即其具有某个正的收敛半径, 虽然就这个例子而言并不是什么困难. 我们可以用归纳法轻易地验证 $$\forall n\in {\mathbb{N}}_0,|a_n|\le 2^n$$ 根据Cauchy–Hadamard定理, 我们知道收敛半径大于等于$1/2$.
3. 通过建立形式幂级数的理论. 这可以做得相当形式化, 就是非常无聊而已. 当然, 也不会有什么新东西.

形式幂级数的理论概览.

我们将给出复系数幂级数的理论, 虽然仅需很少的调整其也可以对于环成立. 你应该将形式幂级数看成是具有无限次数的多项式. 或者说, 实际上你应该将确定了形式幂级数的序列当成是形式幂级数自身. 也就是说, 我们的形式幂级数不过就是一个映射 $${\mathbb{N}}_0\to ℂ,n\mapsto a_n$$ 加法被定义为逐项之和. 令 $$\begin{array}{l}A(x)=a_0+a_{1}x+a_2{x}^2+\cdots \\ B(x)=b_0+b_{1}x+b_2{x}^2+\cdots \end{array}$$ 那么 $$(A+B)(x)=(a_0+b_0)+(a_1+b_1)x+(a_2+b_2)x^2+\cdots$$ 乘法被定义为所谓的Cauchy乘积 $$(AB)(x)=(a_0{b}_0)+(a_0{b}_1+a_1{b}_0)x+(a_0{b}_2+a_1{b}_1+a_2{b}_0)x^2+\cdots$$ $x^n$的系数为$\sum _{j=0}^n{a}_j{b}_{n-j}$. 如果$b_0\ne 0$, 那么$(A/B)(x)$也是有定义的. 如果$b_0=0$, 那么$(A\circ B)(x)$也是有定义的, 甚至我们可以确定一个$C(x)$使得$(C\circ B)(x)=x$. 我们可以形式化地对于幂级数进行微分. 在特定条件下, 我们可以定义幂级数的无穷级数和无穷乘积.

第2.1节 零钱问题

如果你需要付$67$分钱买一杯咖啡, 而只能以$1,5,10,25$分钱的硬币付款, 假定每种硬币的数量都是足够多的, 那么有多少种付款的方式呢? 我们可以先尝试枚举一些具体的方案. $$\begin{array}{cccc}(1)& (5)& (10)& (25)\\ 2& 2& 3& 1\\ 7& 2& 0& 2\\ 7& 0& 1& 2\end{array}$$ 换言之, 一种方案完全由其频率函数 $$f:\{1,5,10,25\}\to {\mathbb{N}}_0$$ 刻画. 我们的问题是存在多少个总值为$67$的这样的频率函数. 频率函数$f$的总值即 $$1\times f(1)+5\times f(5)+10\times f(10)+25\times f(25)$$

解法.

刚才我们并不成系统. 实际上, 答案是 $$\begin{array}{ll}(1+x+x^2+x^3+\cdots )& \times \\ (1+x^5+x^{10}+x^{15}+\cdots )& \times \\ (1+x^{10}+x^{20}+x^{30}+\cdots )& \times \\ (1+x^{25}+x^{50}+x^{75}+\cdots )\end{array}$$ 中$x^{67}$的系数, 即$87$.

如果我们用${\mathrm{C}}_E$代表"$E$的系数", 那么问题的答案可以记为 $${\mathrm{C}}_{x^{67}}\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}$$ 以这种方式, 我们可以找出其他系数, 或者研究$n\to \infty$时${\mathrm{C}}_{x^n}$的渐近性质.

这种方法的正确性是不言自明的. 在合并幂级数乘积的同类项之前, 每一项的系数都是$1$, 而且其都对应于从每一行的级数里各选出一个项来, 这就从概念上指出了一种挑选方式. 比如说, 项$x^2{x}^{10}{x}^{30}{x}^{25}$对应于使用$2$枚$1$分硬币, $2$枚$5$分硬币, $3$枚$10$分硬币, $1$枚$25$分硬币的方案. (译注: 当然, 更严格地说, 这里我们考虑的是项的内涵, 因为从外延看, 我们无法区分次数相同的项.) 在合并同类项之后, $x^n$的系数显然就等于付$n$分钱的方式数目.

第2.2节 一个求和公式

我们猜读者已经熟悉用$|S|$表示集合$S$的元素数目的记号了. 如果$R$和$D$是集合, 那么类型为$D\to R$的所有映射构成的集合, 我们记作$R^D$. 公式$|R^D|={|R|}^{|D|}$是很好的助记方法.

作为定理的应用, 令$K$是$\mathbb{Z}$上的形式幂级数环, $D=\{1,5,10,25\}$, $R={\mathbb{N}}_0$, $\varphi (d,r)=x^{dr}$, 那么 $$\prod _{d\in D}^{}\varphi (d,f(d))=x^{(f\text{的总值})}$$