为什么每次想编程的时候总是不能坚持编下去呢？好吧！我承认刚才本来想编程的，结果编不下去了… 今天我想说说 “戴维斯的街道和生成函数” （以下内容可能引起非数学专业的童鞋们的不适，请回避…）。
当我刚来戴维斯不久时，我就发现这里的街道很有意思，首先都是棋盘形的，横平竖直。其次，街道的命名方法很直接：南北方向的以英文字母 A, B, C, D … 命名，东西方向的以 1, 2, 3, 4, … 命名（后来去过其它城市才发现这是命名的通用规则）。我住在 J street 和 Covell Blvd 的交叉口 （Covell 大概到了14街吧），每天骑车总会想想有什么新鲜的路线可以尝试。
[caption id=“attachment_514” align=“aligncenter” width=“600”]
戴维斯城区地图，大体上呈田字形的街道[/caption]
这一天突然想到一个问题：如果我每天尝试一条路线去学校，一年时间能不能把所有路线都试一遍呢？ 在纸上画了画，觉得这个问题似乎很复杂（小学奥数没学好，记得有这样的计数问题，可是却忘了怎么做），路线可以多种多样，在每个交叉路口都有 2 或者 4 种选择。要保证最后的路线不形成圈，而且能从固定起点（例如家）到固定终点（例如学校）。 但是，作为受过多年数学专业训练的人，我怎么能随便放弃一个数学问题呢？于是从简单的问题着手：如果大街围成一个 1×1，1×2，2×1 …. 的小方格，路线应该如何计算？
[caption id=“attachment_517” align=“aligncenter” width=“600”]
手绘简图和思路[/caption]
很快发现，应该对走的方式加以限制：假定从田字格的左下角出发，目的地是右上角，我们可以给节点以坐标，例如让左下角节点为原点 (0, 0)，所有节点都用整数数组 (i, j) 来标记。那么，我们应只考虑那些往东或北方向行进的路线：因为这样才能更接近目的地。 于是我们的问题变为：从 (0, 0) 点出发，到 (n,m) 点，如果每次都让横坐标或者纵坐标加 1 的话，这样的路线会有多少条？ 假设我们的棋盘大小为 n×m，假设从 (0, 0) 点出发，到 (n,m) 的路线总数为 $W_{(n,m)}$，那么向东或北前进后，从新起点到 (n,m) 的路线应该分别为 $W_{(n-1, m)}$ 和 $W_{(n,m-1)}$。于是我们就有了一个递推公式： $$W_{(n,m)} = W_{(n-1,m)} + W_{(n, m-1)}.$$ 初始条件自然是 $W_{(0,m)} = W_{(n,0)} = 1$。因此，从数学上说，这个问题已经解决了！ 但是，显然如果这就算是问题的答案，大家一定不满意！好吧，那我们来算具体的例子：我之前说过，我公寓的位置大概是 J st 和 14th st 的交汇处，假设学校的位置是 A st 和 1st 的交汇处，也就是原点 (0, 0)，那么我的公寓坐标就是 (10, 14)。用我最喜欢的一个小众数学软件 FriCAS 实现递推公式是最容易的，代码如下：
[cc lang=“Haskell”]
W(n,0)==1
W(0,m)==1
W(n,m)==W(n,m-1)+W(n-1,m)
[/cc]
要求具体值时，只要输入 [cciN_haskell]W(10,14)[/cciN_haskell] 就可以得到结果。最后计算出道路的数目约一百九十六万（1,961,256)。如果我每天选不同的路线的话，要走五千多年才能走完。
更进一步
作为学数学的重脑力工作者，到这一步自然不会结束。有没有一种方法可以不用电脑解决问题呢？我们可以使用数学中常见的技巧：所谓生成函数（generating functions）的方法，将所有 $W_{(n,m)}$ 组合在一起，给每组 (n,m) 配以不同的权重，加以区分。权重是用未定元的不同次数实现的。在有了权重以后，我们可以把所有 $W_{(n,m)}$ 组合起来，这就是生成函数，我们记其为 $ \Phi $:
$$ \Phi(x,y) := \sum_{n,m\in\mathbb{N}} W_{(n,m)} x^n y^m.$$
这个公式，对于学过微分方程的人其实并不陌生，它就是著名的 Laplace 变换！因此，我们实际上对 $W_{(n,m)}$ 做了这个变换。
下面，我们自然要问，既然 $W_{(n,m)}$ 可以变换，那么 $W_{n,m}$ 所满足的等式可不可以变换呢？当然可以！这正是我们关心的问题！如果对 $W_{(n,m)}$ 的递推公式两边都作用 $\sum_{n,m\in\mathbb{N}} x^n y^m$ 的话，我们会得到如下关系
$$ \Phi(x,y) = (x+y) \Phi(x,y) + \frac{x}{1-x} + \frac{y}{1-y}.$$
注意到右边最后两项使用了初始条件。所以 $$ \Phi(x,y) = \frac{x+y-2 x y}{(1-x) (1-y) (1-x-y)}.$$
也就是说，所有关于路径数目的信息完全隐藏在函数 $ \Phi(x,y)$ 里了！如果想求到任何位置 (n,m) 的不同路径数目，只要算算 $ \Phi(x,y)$ 的展开式 $x^n y^m$ 项的系数就好了！