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

请利用上面的定理证明下图中的7,8

4 Counting with Generating Functions

Example

【1】从n个元素里选r个，允许重复，有多少种可能
根据之前学的知识，这属于可重复的组合问题，比如A元素可以被选1次，或2次…
看成n个盒子，一共放r个球，如果A盒子放了3个球，意味着被选3次
n-1个bar，r个star
故答案为

我们使用生成函数来做这道题，一个元素可以被选0次，1次……
对应着x的0次方，1次方……

n个元素，每个元素有它被选的次数（每个括号贡献的指数），一共选r个，每一种选择乘起来就是，所以最后结果中的系数就是答案
根据之前的常见数列的生成函数，答案是

不过，我对这个方法的可靠性有一定的怀疑，但说不出来，目前先接受，如果你看到这句话的话，说明我还没说服自己（

【2】请找出的所有非负整数解的个数，其中
这是带限制的相同球放不同盒子问题，一般方法还是比较难做的，但用生成函数可以很好地解决

这三个括号分别代表
找出这个式子中的系数就是答案
这个方法还是没有疑问的，与原问题直接对应
找系数就只能慢慢找了，所以其实这道题直接枚举应该也可以（

【3】Suppose that there are 2r red balls, 2r blue balls, and 2r white balls. How many ways to select 3r balls from these balls?

注意这里找系数的方法，其实如果是无穷项的话大概也是这个方法，只不过减会变成减去x的无穷大的次方，即之前【1】中应为，所以分子只用1就行，x的无穷大次方哪怕一次方也不用考虑了，这也许可以作为一个解释，当然还是要依赖于可以展开成无穷级数

【4】Determine the number of ways to insert tokens worth $1,$2 and $5 into a vending machine to pay for an item that costs r dollars in both the cases when the order in which the tokens are inserted does not matter and when the order does matter.
先考虑次序不重要的情况，同样地，这道题也是1元、2元、5元可以被选多次，只不过要注意它们的数值
生成函数为找到的系数即可

如果不使用生成函数，那么我们就按5元的个数分类讨论即可，例如r=10的情况，5元可以选0、1、2个，比如5元为1的情况，剩下5元又2元1元组成，2元可以选0、1、2个，就有三种。

如果考虑次序，那么每次我们可以选择1、2、5元，如果一共选了个硬币，那么就是
其中的系数就是符合的情况，但是，我们又不知道一共会选多少个硬币，所以应该是下面这个式子中的系数

如果不用生成函数，这也是个不太简单的问题
假设有种方法
如果最后选的是1元，那么前面有种
2元，前面有种
5元，前面有种，得到递推式
如果我们把看作，恰好代表r=k时的答案，右边分母乘过来
比较系数，也可以得到相同的递推式

Extra

GPT对于生成函数计数的解释，也许可以参考

5 Using Generating Functions to Solve Recurrence Relations

最后是靠的系数对应

6 Proving Identities via Generating Functions

例如证明

7 Inclusion-Exclusion

Example

【1】不超过1000的正整数中，不被5、6、8整除的数有多少个
总数减去被5或6或8整除的数即可
被5或6或8整除的数等于
200+166+125-33-25-41+8=400
故答案为600

【2】26个字母的排列，不包含字符串fish、rat、bird的有多少
一共有26!种
包含fish的：把fish看作整体，然后全排列，有23!个
既包含fish又包含rat的，分别看作整体，21!个
而fish和bird不能同时出现，rat和bird不会同时出现（都有r），这三个也不会同时出现
所以答案为26!-(23!+24!+23!-21!-0-0+0)