Chapter 8 - Advanced Counting Techniques

定义

注意

补充、解释

其他

本章全程高能（

1 Applications of Recurrence Relations

“这种题找递推关系是最难的一步”

We distinguish them by the initial conditions, the values of a0 , a1 , a2 , … to uniquely identify a sequence.
例如
我们要定义C(n,0)和C(n,1) （和非法组合数为0）

【Example】A young pair of rabbits is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits on the island after n months, assuming that no rabbits ever die.

n个月后，原先有对，新出生的对，因为代表两个月前的兔子对数，这些对兔子现在都能生育了

【Example】Let denote the number of moves needed to solve The Tower of Hanoi problem with n disks H1 , H2 , … , Hn , …

汉诺塔的任务是三个杆，把n个盘从1号运到2号
先把n-1个盘运到3号，再把底下的盘运到2号，再把n-1个盘运回2号

，两边同时+1即可解得

这个算法看上去很简单易懂，其实没那么显然……

【Example】Find a recurrence relation for the number of bit strings of length n that don’t have two consecutive 0s.

如果这个长度为n的字符串最后一位是1，那么只有个
如果结尾是10，那么只有个

这已经涵盖了所有情况，因为末两位只能是11，10，01

2 Solving Linear Recurrence Relations

这让我想起我高中时的一位数学老师

2.1 Linear homogeneous recurrence relation of degree k with constant coefficients

把换成
得到characteristic equation

得到k个characteristic root

证明：
首先将这个形式代入递推式，再利用，是符合的
利用初始条件解出α，根据递推的唯一性（归纳法证明），若an是解，可以写成这种形式

2.2 Linear Nonhomogeneous Recurrence Relation With Constant Coefficients

怎么想到了线性代数？

特解的形式，注意s=1的情况

3 Generating Functions

期中考之前，我还挺喜欢级数的，好吧，现在也挺喜欢的

Definition

The generating function for the sequence of real numbers is the infinite series

例如，数列1,1,1,1,1,…的生成函数是

其中

Example

【1】What is the generating function for the sequence 0,1,2,3,4,…

【2】Suppose that the generating function of the sequence: is G(x). What is the generating function for the sequence

所以上一题也可以这么做：

【3】What is the generating function for the sequence

【4】What is the generating function for the sequence ?

【5】. Find the coefficient in the expansion

3.1 The extended binomial coefficient