组合学笔记

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

第1章 引论

第2章 生成函数

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

给定一无穷数列a0,a1,a2,…其生成函数为以下级数A⁡(x)=a0+a1⁢x+a2⁢x2+⋯

生成函数这种技术的想法在于关于序列的知识→向前转换关于A⁡(x)的知识↓各种操作更多关于序列的知识←向后转换更多关于A⁡(x)的知识这有点像是Laplace积分F⁡(x)=∫0∞ex⁢t⁢f⁡(t)dt其想法在于关于f的微分方程→Laplace变换关于F的代数方程↓求解代数方程关于f的微分方程的解←向后转换关于F的代数方程的解

记号. 为了避免可能的歧义, 我们定义ℕ0={0,1,2,…}以及ℕ1={1,2,3,…}
例子. Fibonacci数列定义如下a0=1;a1=1;an+1=an+an−1,n∈ℕ1Fibonacci数列的生成函数为A⁡(x)=1+1⁢x+2⁢x2+3⁢x3+5⁢x4+8⁢x5+13⁢x6+⋯基于其系数的递推关系, 我们发现x⁢(x+1)⁢A⁡(x)=A⁡(x)−1于是A⁡(x)=−1−1+x+x2将该分式拆分可以得到A⁡(x)=(1x−α1−1x−α2)⁢−1α1−α2其中α1和α2是−1+x+x2的两根.
若是我们将这些分式再写成幂级数的形式, 然后合并同类项, 就可以得到an=15⁢[(1+52)n+1−(1−52)n+1]

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

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

形式幂级数的理论概览.

我们将给出复系数幂级数的理论, 虽然仅需很少的调整其也可以对于环成立. 你应该将形式幂级数看成是具有无限次数的多项式. 或者说, 实际上你应该将确定了形式幂级数的序列当成是形式幂级数自身. 也就是说, 我们的形式幂级数不过就是一个映射ℕ0→ℂ,n↦an加法被定义为逐项之和. 令A⁡(x)=a0+a1⁢x+a2⁢x2+⋯B⁡(x)=b0+b1⁢x+b2⁢x2+⋯那么(A+B)⁡(x)=(a0+b0)+(a1+b1)⁢x+(a2+b2)⁢x2+⋯乘法被定义为所谓的Cauchy乘积(A⁢B)⁡(x)=(a0⁢b0)+(a0⁢b1+a1⁢b0)⁢x+(a0⁢b2+a1⁢b1+a2⁢b0)⁢x2+⋯xn的系数为∑j=0naj⁢bn−j. 如果b0≠0, 那么(A/B)⁡(x)也是有定义的. 如果b0=0, 那么(A∘B)⁡(x)也是有定义的, 甚至我们可以确定一个C⁡(x)使得(C∘B)⁡(x)=x. 我们可以形式化地对于幂级数进行微分. 在特定条件下, 我们可以定义幂级数的无穷级数和无穷乘积.

评注. 我们的一个重要想法在于, 如果一个操作对于每个系数的计算只涉及有限多的非平凡步骤, 那么其也应该是可行的, 哪怕这个操作实际上是无穷的. 什么是平凡的呢, 比如说加上0, 乘上0, 乘上1这种.
让我们考虑一个例子(A∘B)⁡(x)=a0+a1⁢B⁡(x)+a2⁢B⁡(x)2+a3⁢B⁡(x)3+⋯当b0≠0时, 每一项an⁢B⁡(x)n都包含一个非零的常数项, 将其合并就得到a0+a1⁢b0+a2⁢b02+⋯这是我们所不允许的无限形式的操作.
再看另外一个例子. 对于k∈ℕ0, 我们将Ak⁡(x)定义为从ak⁢xk开始的幂级数. 那么, 我们可以定义∑k≥0Ak⁡(x): 对于第k项, 我们仅需加起k+1个项.

第2.1节 零钱问题

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

解法.

刚才我们并不成系统. 实际上, 答案是(1+x+x2+x3+⋯)×(1+x5+x10+x15+⋯)×(1+x10+x20+x30+⋯)×(1+x25+x50+x75+⋯)中x67的系数, 即87.

如果我们用CE代表"E的系数", 那么问题的答案可以记为Cx67⁡1(1−x)⁢(1−x5)⁢(1−x10)⁢(1−x25)以这种方式, 我们可以找出其他系数, 或者研究n→∞时Cxn的渐近性质.

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

第2.2节 一个求和公式

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

定理. 令K是一个含幺交换环, D和R是集合. 对于映射ϕ:D×R→K, 我们有∑f∈RD∏d∈Dϕ⁡(d,f⁡(d))=∏d∈D∑r∈Rϕ⁡(d,r)
证明. 显然, 或许唯一值得注意的是边角情况. 若D=∅, 那么左右皆为1. 若D≠∅且R=∅, 那么左右皆为0.
◻

作为定理的应用, 令K是ℤ上的形式幂级数环, D={1,5,10,25}, R=ℕ0, ϕ⁡(d,r)=xd⁢r, 那么∏d∈Dϕ⁡(d,f⁡(d))=x(f的总值)