Concrete mathematics, 逝去岁月的追忆

Reference
Concrete Mathematics a foundation for computer science
Kursus ITT9130: "Konkreetne matemaatika" Tallinn University of Technology 关于CM的课件，不错。塔林(爱沙尼亚共和国首都)


The Thought of Problem-Sloving
1.The best way to tackle a question like this(recurrent problem) is to generalize it a bit.
2.LOOK AT SMALL.宏观整体的学习方法
1。看不懂，不要硬看；上网找点资料。
2.遇到证明不用怕，自己跟着写一遍就可以了。


1 Recurrent Problems
1.1 The tower of hanoi —— 汉诺塔 递归解题思路
【1】LOOK AT SMALL:解决小规模问题，其中规模为0，1，2。。。的称为Basic case，他们的解只需要一次逻辑思考就可以得到；另外一些小规模问题是完整问题的浓缩版，不像Basic case 那样小，我称为Elite case。 为什么要研究解决小规模问题有三： 1、简单容易解决，可以增强自信心，有点打酱油。。。更为重要的是在我们确定了递归关系后，可以用小规模的解来检测我们发现的递归关系是错误的，但是不能保证这个递归关系一定正确，why？ 2、揭示一些更为本质关系，为我们解决大规模问题提供线索、参考，通常是从Elite case 中寻找到蛛丝马迹。 3、递归问题的求解是Top-down，而Basic case就是我们的“底”，也就是问题停止向下求解的地方，并不是所有Basic case 都可作为Terminate Condition终止条件 ，这要根据你的递归关系进行确定。
【2】NAME AND CONQUER：选取合适的表示符号，表示什么要非常明确，这很重要哦！Then，用符号表示Terminate Condition 和通用的递归关系，其实这个递归关系是非常好确定的，你只要记住递归关系是这漫长之旅的一个恒定的剪影而已。就像写一个递归函数一样，没什么难的。 我们来解决n个盘子3个柱子的汉诺塔问题： Let's look at small ，Basic case：0个盘子需要移动0步，1个盘子需要1步。Elite case：2个盘子需要3步，3个盘子需要7步。ok，done！ Name and conquer，Tn表示n个盘子时需要移动的步数，是步数： 首先你学要将Top-down的哲学牢记在心——骗自己除了最大规模的情况之外，所有规模问题都解决了！让我们看看n等于2和3时： 2个盘子时，我们先把小的盘子扔到一边（第三个柱子），之后直接把大盘子移动到目的地(第二个柱子），再把小盘子放到大盘子上，ok完成了。 3个盘子时，我们先要把上面的两个盘子想办法移动不碍事的地方（第三柱子），之后吧第三个大盘子直接移动到目的地（第二个盘子）就行了，在把那两个移过来。 那么这个永恒而美丽的剪影（递归关系）是什么呢？当把n盘子都移到第二个柱子（目的地）这个过程中(需要Tn步)，很显然我们需要做的就是先把最低下的那个大盘子移动过去(需要1步)之后再是其他稍小的，所以在这之前你需要把其他稍小的盘子(需要T(n-1)步)都移动到第三个柱子上（骗自己这些移动没有问题，我们已经解决了,事实他真的将会被解决），好让我们能完成移动大盘子到第二个柱子（目的地）。最后需要对在第三个柱子上的n-1盘子动手了需要多少步？我想你已经能描绘出这个美丽的剪影了。 Tn=2Tn-1 + 1; 还有一个问题，我们的Terminate Condition还没确定呢？显然她一定在Basic case中:T0=0;T1=1;都是吗？有一个简单的方法就是利用上面的递归关系，排除法：能用其他Basic case表示的Basic case一定不是Terminate Condition，这下你能选出来了吧： T0=0; 让我们梳理下思考的过程： 1.找出Basic case
2.通过Elite case 推到出递归关系，需要一定的抽象能力，发现问题中不变的地方（移动底下的盘子前，要先把其他小牌子扔到一遍去，别碍事：-））。 3.由递归关系确定Terminate Condition Tn=2Tn-1 + 1;T0=0; 这是我们最终确定的汉诺塔的完整递归关系等式，怎么计算呢？你可以一个一个代值求，对于n非常大时（其实不用太大10就够你受的）我想有点理智的都不会这么做的。答案就是Closed form （我们学校wiki访问不了一个月了~~学校的新防火墙），就是将递归关系等式转换为Closed form。 Concrete Mathematics 中Closed form 的定义 : An expression for a quantity f(n) is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of n. 有两种方法能转换为Closed form： 1。根据小规模数据的解值，推测Closed form，就是有根据的“猜”；之后用数学归纳法证明猜想。汉诺塔中T=0；T1=1；T2=2*1+1=3；T3=2*3+1=7；T4=2*7+1=15。。。Tn=2的n次幂-1。closed form :-)证明略。 2。答案就在具体数学这本书里。对于汉诺塔来说：T0 + 1= 1；Tn + 1= 2T(n-1) + 2 ;if n > 0.用Un = Tn + 1；替换得：U0 = 1；Un = 2U(n-1); if n > 0.Un=2的n次幂。--->Tn = 2的n次幂 -1. 很迷人，我怎么就想不到呢？Knuth是怎么想到的呢？
1.2 Lines in the plane —— 面中线
一个平面最多能被n条直线分成多少个部分呢？让我们继续用我们上面使用的思路，来攻克这个问题：-）。 Let‘s look at small。这部分很重要，可以说能否得到最终的答案全在这部分了，所以你现在最好拿张纸，安静把他们画出来：-） Basic case：0条直线，就一部分，平面本身；1条直线，2部分；2条直线，4部分。Ok，done！ Elite case：3条直线，7部分。4条直线，11；5条直线，16条。over！接下去，在画已经没有必要了，我想你已经发现点什么了，要想分的越多，就要保证和越多的线交叉；换句话，平面被分割成最多时，这条新加的直线得和所有已经存在的直线相交，且交点不能重合。 Name and conquer,Ln表示n条直线平面被分割成的部分的数量： Top-down的哲学忘了吗？我们来揭示面中线这个迷题的递归关系，如果你细心地画了那些直线，你已经发现她了： 当画第3条线我们发现，做多在原有基础L2增加了3部分，共有L3=4+3=7部分， 当画第4条线我们发现，做多在原有基础L3增加了4部分，共有L5=7+5=11部分；我们都应该能发现每当新增一条直线，平面上就增加和边数数量相当的部分，你看多简单我们找到了她： Ln=L(n-1) + n; 还差什么，Terminate Condition，对我想你没有忘记，怎么找到他——递归关系等式+排除法：L0 = 1； Terminate Condition 递归关系等式完整形式如下： Ln = L(n-1) + n; L0 = 1； 是的，计算递归关系等式是一个，很有意思的挑战，他又来了。 1.1、2、4、7、11、16.。。。猜，推测，貌似行不通 2.递归展开recurrence unfolding Ln = L(n-1) + n = L(n-2) + (n-1) + n = L(n-3) + (n-2) + (n-1) + n =...= L(1) + 2 + 3 + 4 + ... + (n-1) + n = L(0) + 1 + 2 + 3 + ... + (n-1) + n'1 + 2 + 3 +...+ (n-1) + n.Ln = n(n+1)/2 +1; Closed form
Bent lines in plane —— a variation of the lines-in-the-plane problem.
Bent line 和锐角表示一样：两条射线源于同一点。我们用Zn表示n条bent line时 平面被分割的成的部分数量。 Look at small, Basic case:Z0 = 1；Z1 = 2 ;Elite case :Z2 = 7,Z3 = 15,Z4 = 29，但是我没看出来思路。。。。这道题想了很长时间没想出来，所以并不是每道递归题的递归关系都那么好确定，但是我们的解题思路是正确的。出问题的是我们其他方面的知识，就这道题而言就是，我们没有灵活运用直线分割二分一个平面这个概念！！ Concrete Mathematics 给出的不是基于递归思想的解,这里同时给出周济民同学(数学帝，北大数学系的高材生，10年奥数功底)给出递归等式，大概只用1分钟就作出来了，Orz，膜拜大神～～～ Zn = n(2n-1) +1;Zn = (2(n-1) + 1 )*2 -1 + Z(n-1) 解释下周济民的等式：2(n-1) + 1表示新加入的Bent line 中一条射线边被原有的边分成的段数。乘以2表示这个Bent line中两条射线边被分成的总段数，你要理解的是每一个段将这个段所在的面分成了2两份，也就是说(2(n-1) + 1 )*2表示的就是所有段增加的面数，而最后的减1是由于两个靠近射线端点的段重复了。核心思想就是一个段将面分成了两个（实际增加了1个！）。
1.3 The Josephus Problem —— 约瑟夫问题
我们用J(n),表示当有n个人时，最终从这个血腥的游戏中幸存的那个幸运儿的编号（所有人的编号有1到n）。 Look at small, Basic case :J(1) = 1; J(2) = 1; Elite case:J(3) = 3;J(4) = 1; J(5) = 3;J(6) = 5; Name and conquer 当n=3 时，被干掉的顺序是 第一轮：2->1剩下编号为3号的人。 当n=4 时，被干掉的顺序是 第一轮：2->4，第二轮：3.剩下编号为1号的人。 当n=5 时，被干掉的顺序是 第一轮：2->4->1，第二轮：5.剩下编号为3号的人。 当n=6 时，被干掉的顺序是 第一轮：2->4->6，第二轮：3,1.剩下编号为5号的人。 最后剩下的人必然是奇数编号的，很显然偶数编号的在第一轮就被干掉了，我们同时也可得出那个幸运的人必定在每一轮里的编号也是奇数，不过这些都不痛不痒对解题没有多大的帮助 我们再想想，还有什么东西，每一轮这个幸运的家伙都有一个Lucky number。这些幸运的编号之间有什么关联呢？ 以n=5为例，J(5)=3,即命中注定这个幸运而是3号，第一轮是在她旁边的人纷纷倒下倒在血泊里之时，她依然魁然不动闯进了第二轮那么这第二轮的编号怎么计算的，她前面的1和2号都挂了。她的新编号就是1呗。再看看还有几分钟活头的5号的编号变成了2，我们不难发现原来的5个人减了一半+1（这里向下取整）即3个，所人的编号都减小了原来的一半+1，即3/2-1=1；5/2-1=2. 那么这个幸运的人的编号（编号为3的人）的在这一轮之后怎么表述呢？J(2)= J(5)/2 -1；等价于J(5)=2J(2)+1; 以n=6为例，J(6)=5,第一轮之后，剩下了1、3、5，这三个人了，他们的编号分别编程了1，2，3.你能找到他们之间的对应关系吗？前者是奇数集，后者是整数集，我想你高中应该学过怎么加一个整数集映射到奇数集，ok，奇数=2整数-1.当然你也不一定非得 这么找关系，只要找到就好，不要管他具体的形式，所以幸运的人的在这轮和下轮之间的关系我们就有了J(6)=2J(3)-1.推广下我们就能得到n个人的递归关系，这里我们有意识的分开讨论了总人数是奇数和偶数时的不同情况，但是当我们做题时，一般都不会有意识去分开讨论的；不用担心 ，你会分开讨论的，因为，只有一个计算公式，你比然会遇到半个人的情况； 那么我们的递归关系是什么呢？J(1)=1;J(2n) = 2J(n) - 1; n>=1J(2n+1) = 2J(n) + 1; Generalization for Josephus Problem —— 约瑟夫问题推广 这里，作者介绍了Repertoire method ,（这是讲Repertoire method最好的文章了，看完就懂了！！！这个资源好难找呀，国外的原始链接无效了，找了一下午最后在百度文库找到~~现在犯恶心了~~） 首先，Repertoire method 是由作者经验性（seat of the pants）的总结出来的方法； 其次，Repertoire method 在递归等式是线性的时候（就像约瑟夫问题那种，常数乘以f(n)），最为适用！ Repertoire method 好难理解呀，去年第一次看的时候就没看懂；网上的资料也不多，这个方法貌似高中或者是大一高数课讲过记不清了，好像和直线族挺像，用一个函数表达式表示经过某一个定点的所有直线；让我们来揭开她的面纱，从最开始的地方，Knuth，为什么要介绍Repertoire method呢？而且还是讲述主题为递归的章节的末尾，我可以告诉你，高德纳老爷爷用心良苦，这个Repertoire method 方法 ，威力无比，简直就是求解“线性”递归的终极武器，什么是终极武器——无坚不摧！！关于“线性”递归这个概念，Concrete mathematics 给出的描述：The method (Repertoire method) works best with recurrences that are "linear",in the sense that the solutions can be expressed as a sum of arbitrary parameters multiplied by functions of n, as in f(n) = A(n)a + B(n)b + C(n)c + 。。。; 也就是说，你的推广递归关系等式必须满足：能把她写成f(n) = A(n)a + B(n)b + C(n)c + 。。。这种类似的形式。 置于满足什么要求的推广递归等式，可以写成这样还需要探索。所有这种递归等式，你都可以用Repertoire method来求出具体的Closed form，这就是原因，这对进行算法分析非常有用。 如果细心看了上面连接的资料，我想你肯定掌握了Repertoire method。Concrete mathematics说的，有点不清楚，我们系统地总结下。 我在求解约瑟夫问题的Closed form形式时，通过观察获救的幸运儿编号J(n)和参加这个血腥游戏人总数n之间的关系，直接得出了Closed form的形式。 J(2的m次幂 + L) = 2L + 1; 但是，我们能快速，直接得到约瑟夫问题的Closed form，根本原因是我的到的约瑟夫的递归关系简单，规律性强！反之，遇到拥有约瑟夫问题同样递归关系形式，而最后加减的常项不是1，比如是13、7或者是n，规律就没那么简单了～～所以为了我们今后，遇到这样的问题，可以快速的解决掉她，所以Knuth为我们带来了Repertoire method。 我们下面演示约瑟夫问题的求解并严格区分Special case、Generalized case、Genearl case、Closed form！！J(1)=1; Terminate ConditionJ(2n) = 2J(n) - 1;J(2n+1) = 2J(n) + 1;n>=1 由约瑟夫问题 推广得到的更通用的Generalized case，a、b、c 为常量，在具体应用中确定下来 约瑟夫问题中为 1、-1 、1f(1) = a;f(2n) = 2f(n) + b;f(2n+1) = 2f(n) + c; for n>=3 通过带入f(n)=A(n);f(n)=1;f(n)=n;（也可以代入合适的a、b、c的值如a=1、b=0、c=0 ）进Generalized case，我们发现可以把上面三个等式用下面的更简单，一致的General case形式，也就是说我们可以把A(n) 、B(n)、C(n)的关于n的表达式。 很显然她并不表示所有的递归情况，而是当你的递归式满足上面的特征Generalized case才行 ！有一个疑问为什么可以通过带入f(n)=1;f(n)=n;f(n)=n*n，求出General case呢？f(n) = A(n)a + B(n)b + C(n)c;A(n) = 2的m次幂;B(n) = 2的m次幂 -1 -l;C(n) = l;n = 2 的m次幂 +l and 0<=l<2的m次幂，n>=1 如果你现在把约瑟夫问题中a，b，c的值（1，-1，1）代入这个统一的公式，你就能的到约瑟夫问题的Closed form形式，这要比去观察那些ever-changing的数字要快速的多，不是吗？更为重要的是Repertoire method很有效！ 让我们来总结下Repertoire method： 【1】递归关系等式的Special case推广为Generalized case(常数系数和常数项，全部代数化） 【2】通过带入符合Generalized case的函数，求解具体的General case(一个确定的f(n)，必然有确定a、b、c，所以在求A(n) 、B(n)、C(n)，你可以分别代入 f(n)和A(n) 、B(n)、C(n)来考虑比如类似f(n)=n或a=1、b=0、c=0 ) 【3】求解Special case(代入a,b,c对应的值，可得Closed form） Wonderful！！值得注意的是Generalized case等价与General case，why？只是后者是Closed form形式，前者则不是！ 另外，我想你对Repertoire(节目表) method应有所了解：General case就是这张节目表，而Special case就是这张节目表上的节目。 最后Concrete Mathemaics 给我们带来一个小甜点： 如果你发现的你的递归等式满足一下形式，其中d和c是已知的常数：


你就可以用这个直接计算：


2 Sums
2.1 Notation —— 符号
Iverson bracket：[ P(k)]
求和的原始通用形式：a1 + a2 +...+ak
求和的Delimited form 定界形式，书写简单明了，多用于表示结果：


求和的General form 通用形式，表达内容丰富灵活，特别适用于计算过程：


2.2 Sums and recurrences —— 求和与递归
开篇，在很多情况下，递归与求和可以相互转换，即等价！这很重要解决递归的Repertoire method就可以解决Sums，而解决Sums的方法也可以解决递归了。总之，打开了一条Sums and recurrences 的通道！
符合下面的形式的Recurrences ：


可通过乘以一个summation factor(求和因子)转化为Sums；
2.3 Manipulation of Sums —— 操控求和
Perturbation method
2.4 Multiple Sums —— 多重求和


2.5 General methods


2.6 Finite and infinite calculus


2.7 Infinite sums






5 Binomial Coefficients
5.1 Basic identities —— 基本性质
1.从排列的角度，本质的理解组合公式，。
2.对组合公式进行推广上索引可为任意实数，下索引可为任意整数。其实这就是牛顿二项式理论！！
2.1.推广的组合公式可以看成k次r多项式。
2.2.推广版的组合公式中的C(n,n)=1值得注意
3.Pascal's triangle
3.1.It's worthwhile to memorize formulas for the first three columns
3.2.It's also a good idea to memorize the first five rows or so of Pascal's triangle
3.3.hexagon property,
4.Factorial 组合公式就是组合数学中的定义的
5.symmetry identity，absorption identity,
6.polynomial argument，没看懂。。。
6.1.Ken Ward's Mathematics Pages
6.2.Method NO. 4 : The polynomial argument 这个正好就是我们正在学的。
7.the addition formula in Pascal's triangle ，this is widely used formula。
7.1.一个坏鸡蛋的故事
7.2.plus two absorption
7.3factorial expansion
7.4.A formula expresses one binomial coe cient as the sum of others whose upper and lower indices stay the same distance apart.——expansion latter
7.5.summation on the upper index——expansion former。
7.6.C(r,0)=C(r+1,0)=C(r+200343444005498,0).
7.7.Certain sums that we did in Chapters 1 and 2 were actually special cases of (5.10), or disguised versions of this identity.——足见高德纳的深厚功力。
7.8.This equation tells us that row n of Pascal's triangle sums to 2n .
7.9. Taylor series


sum_{n=0} ^ {infin } frac {f^{(n)}(a)}{n!} , (x-a)^{n}
=


f(a)+frac {f'(a)}{1!} (x-a)+ frac{f''(a)}{2!} (x-a)^2+frac{f^{(3)}(a)}{3!}(x-a)^3+ cdots.


5.2 Basic practice
By tackling many such sums in this section and the next, we will hone our binomial coe cient tools.这关是用来练习的。
Problem 1: A sum of ratios.
Problem 2: From the literature of sorting.
Problem 3: From an old exam.
Problem 4: A sum involving two binomial coefficients.
Problem 5: A sum with three factors.
Problem 6: A sum with menacing characteristics.
Problem 7: A new obstacle.
Problem 8: A different obstacle.
5.3 Tricks of the trade
Trick 1: Going halves.
1.duplication formula
Trick 2: High-order differences.
such coefficients are intimately associated with the difference operator ? defined
Trick 3: Inversion.
5.4 Generating functions
We come now to the most important idea in this whole book, the notion of a generating function.—— Gelivable！！！
1.重要的概念Analytic function，Holomorphic function，power series，数学基础不够，理解不了~~
2.卷积，由(a0 + a1*z + a2*z^2 + · · · )(b0 + b1*z + b2*z^2 + · · · )= a0*b0 + (a0*b1 + a1*b0 )z + (a0*b2 + a1*b1 + a2*b0 )z^2 + · · ·;
我们可以得到the coefficient of z^n in this product is a0*bn + a1*bn?1 + · · · + an*b0
2.1convolution of sequences corresponds to multiplication of their generating functions.——c^n = [zn ] A(z)B(z) .
2.2.Vandermonde convolution
推导得出，真是美不胜收呀！
2.3.推导得出
5.5. Hypergeometric functions
1. 理解这个定义，The general hypergeometric series is a power series in z with m + n parameters, and it is de ned as follows in terms of rising factorial powers:


2.Gaussian hypergeometric，数学王子高斯做了很多细致的研究。
3.a hypergeometric series always has the value 1 when z = 0.这是超几何级数的重要特征。
4.Hypergeometric functions 之于我们的最大用处是对二项式系数函数进行系统的归类划分。
5.208页的练习中的表示符tk不要和前面定义中tk混淆了，不是一回事！




5.6 Hypergeometric transformations
1.worm on the rubber band




6 Special Numbers


6.1 Stiring numbers
1.Every permutation is equivalent to a set of cycles.重点理解。
1.1.the permutation 384729156 is equivalent to the cycle arrangement [1, 3, 4, 7] [2, 8, 5] [6, 9] .
1.2.every permutation defines a cycle arrangement.
1.3. permutations and cycle arrangements are essentially the same thing.
2.Stirling subset numbers are the coe cients of factorial powers that yield ordinary powers.
6.2 Eulerian numbers


6.3 Harmonic numbers




6.4 Harmonic summation


6.5 Bernoulli numbers
1.the perturbation method








7 Generating Functions —— 母函数
THE MOST POWERFUL WAY to deal with sequences of numbers, as far as anybody knows, is to manipulate infnite series that "generate" those sequences.
There is one way to partition the empty set into zero nonempty subsets, but there are no such ways to partition a nonempty set;
7.1 Domino Theory and Change —— 多米诺理论和零钱问题
So let's start this chapter with some fun and games as we try to develop our intuitions about generating functions.正如作者所说，这一节通过一些funny的小游戏，给我们关于Generating function的一些直观感觉。
谜题1，用2*1大小的dominos 去完全覆盖2*n大小的矩形，一共有多少中方法Tn。
重点理解这句：There is one way to partition the empty set into zero nonempty subsets, but there are no such ways to partition a nonempty set;
另外我们最终想要的是多米诺摆放的方式综合，记住这一点。Tn代表的是方法总数。
通过look at small我们的到了Tn=（Tn-1）+（Tn-2），你看其实没什么难的，我之前遇到这样的问题，先是心里没信心，以为做不出来，其实只要静心的从小列子观察，就能找到规律。因为这样的问题的最小组成单位，是有规律的：首先，最小单位是有限的。另外，子问题具有分形的特性，即，递归性。
在看完7.1之前，你一定要深刻的体会到母函数的幂级数展开式中z^n的含义：参与组合问题object的个数！
7.2 Basic maneuvers
Now a few words about perspective. The generating function G(z) appears to be two diferent entities, depending on how we view it. Sometimes it is a function of a complex variable z, satisfying all the standard properties proved in calculus books. And sometimes it is simply a formal power series,with z acting as a placeholder. In the previous section, for example, we used the second interpretation; we saw several examples in which z was substituted for some feature of a combinatorial object in a "sum" of such objects.The coefficient of z^n was then the number of combinatorial objects having n occurrences of that feature！上面这段话，可以说是母函数的本质，特别是最后一句。


7.3 Solving recurrences
首先，理解记忆四个步骤。340页看不懂的，看这里
下面是基础的概念：
1.Partial fraction
2.所有的有理函数都可以部分分式展开成如下形式：


现在让我们，再回到母函数的证明中去吧，有些没理解透，另外母函数是个powerful tools， we need to continue。
让我们来总结下Generating functions的应用过程，只是想加深记忆吧了，我问以Fibonacci numbers为例。ok，上。
第一步，写一个针对虽有整数的线性关系gn = gn?1 + gn?2 + [n = 1] ;
第二步，乘z^n，从0~n加和所有递归关


第三步，整理加和的递归关系得出Generating function！！我们要的是gn的系数，而母函数只是个副产品。


第四步，展开母函数成power series，read off gn的cofficient。这步最难，这个系数就是我们想要的，That's all。
这步实在是太难，也可以这么说这步就是求解的关键！
首先我们想直接展开这个母函数太难了，但是我们可以进行归纳，总结（人的另外一种理性思维是演绎）：
所有的母函数都是有理函数。所以可以推广所有的母函数通用形式：
R(z)=P(z)/Q(z),(对比上面的菲波纳齐数列的母函数P(z)=z,Q(z)=1-z-z^2),还不错~~
在所有的的有理函数中，下面这种形式的有理函数最容易展开的，也就是最容易确定展开系数的：


我一直对这个函数的的收敛性有疑问，在一个ppt上看到可以忽略不考虑收敛性的问题。
所有的有理函数R(z)都可以表示成上面的的容易展开的有理函数的加和形式。


其中
如果我们找到了S(z) 和T(z)的具体形式，我们就找到了R(z)的partial fraction expansion 即部分分式展开 ，继续。
接下来，作者给出了z^n的系数：


为什么是这种形式呢？其中Q'是求导。
接下来证明T(z)为0.
再接下来证明R(z)=S(z)用的是极限求导公式，如下：


大一学的极限公式都，忘了。。。。惭愧，当年没有好好学。看看这里。
让我们喜欢第四步：
首先，整个过程的是逆向的证明。先假定z^n的系数公式成立：


之后，再证明上面的公式和下面的公式等价。




我们知道S(z)形式的展开式的z^n的系数非常好求，就是这个：


有点乱。上面这个公式，到底干什么用的，可恶。。。和


有什么关系？其实是没有关系的，[z^n]S(z)只是个演示。
Finally，我们最后一次总结一下这个第四步的求解过程。首先我们要直接找到有理函数R(z)的z^n的系数非常难找。可是我们知道一类有理函数S(z)形式的z^n的系数非常好找。我们能把S(z)的power series展开式用通项的形式表示出来。而其中的z^n的系数就是我们要找的。
我们通过证明得到了任何的有理函R(z)数都可以通过转换表示成S(z)形式。这个S(z)只是个副产品，这个


是我们通过直接


得到的最终答案。
而，我们转换R(z)到S(z)的不的而知，但是通过证明，我们知道这个转换是千真万确的。没错！不过我们可以尝试找一下这个转换过程。
R(z)-->S(z)-->[z^n]R(z):这是整个流程的关系，做题时，直接从R(z)和p得到[z^n]R(z)，就行了。
General Expansion Theorem for Rational Generating Functions.
将我们得到大母函数的公式进行Generalization推广，得到的formula更加通用！但是这个不是7.6节将的那个。
Example 2: A more-or-less random recurrence.
这道例题是对上面刚讲的推广母函数的应用。安静的看一边，母函数的推广版就明白了。
Example 3: Mutually recursive sequences.
Example 4: A closed form for change.
Example 5: A divergent series.
Example 6: A recurrence that goes all the way back.
这些例题都不简单，看了半天就前两个看懂了。
7.4 Special generating functions
关于特殊序列的母函数。
7.5 Convolutions——卷积
卷积的定义，简单而完美


Example 1: A Fibonacci convolution.
Example 2: Harmonic convolutions.
Example 3: Convolutions of convolutions
Example 4: A convoluted recurrence.
Example 5: A recurrence with m-fold convolution.
先跳过~~
7.6 Exponential gf's
Sometimes a sequence gn has a generating function whose properties are quite complicated, while the related sequence gn /n! has a generating function that's quite simple. In such cases we naturally prefer to work with gn /n! and then multiply by n! at the end.这就是指数母函数的由来。
7.7 Dirichlet generating functions


8 Discrete Probability