高级计数技巧

最后一次小测要来了，从计数技巧的基础重新复习这两个单元计数和高级计数方法

Chapter6.计数

基础的计数方法设计的重点有

• 计数中的加法，乘法，减法原理
• 鸽笼原理及其相关的证明题
• 二项式定理
• 重复的排列和组合

6.1基础计数规则

乘法原则

如果一个问题可以按照流程被分为几个部分执行，那么解决这个问题的方法数量就等于每一部分方法数量的乘积。可以理解成一个程序，主程序由三个函数按顺序组成，其中每个函数都各自有几种不同的实现方法，那么这个主程序的实现方法就等于这几个函数实现方法的乘积。也可以抽象地和离线算法的性质类比。

例子

从一个含有m个元素的集合映射到一个含有n个元素的集合，有多少个映射函数？

solution:

每一个元素都有n种选择，所以是$n^m$个函数

加法原则

加法原则就是完成一个问题可以用$n_1$种方法，同时也可以用另外$n_2$种方法，那么总的方法数就是$n_1+n_2$,可以把加法原则运用到上述乘法原则的某一个部分中来理解。加法原则就是我们分类讨论可能会有多少种情况。

例子

如果我们假定一个程序里变量的命名方式只能为单个小写字母或者单个小写字母后跟一个数字，那么有多少种变量命名方法

solution：

$$26+26*10$$

减法原则(subtraction rule)

如果完成一项任务的不同方法间有重合，那么减去重合部分，才能得到总方法数。具体地例子就是求两个集合并集后的元素个数，那么我们在加上两个集合的元素个数后，还要减去两个集合的交集个数。所以减法原则也就是容斥原理

除法原则

如果我们对一个问题得到了n种答案，其中每一种答案都有其他d-1种答案与之等价，那么实际上我们找到的答案是$n/d$

例子

我们有一个有四个位置的圆桌，四个不同的人有几种不同的坐法（当两种坐法中，一个人的左侧和右侧的人对应一样，那么我们认为这两种坐法一样）

solution:

$$\frac{4!}{4}$$

每一种坐法顺时针转一个人都会得到相同的坐法，所以重复次数是4

鸽笼原理

如果k+1个物品放到k个盒子里面去，那么至少有一个盒子放的物品数量大于等于1

从函数的角度来看就是，一个定义域有n+1个元素，值域有n个元素的函数一定不是一个一一映射的函数

广义的鸽笼原理

如果N个物品被放进了k个盒子里，那么至少有一个盒子包含的物品个数大于等于$\lceil \frac{N}{k}\rceil$

例子

一百个人里至少有多少人的生日是在同一个月

至少有$\lceil\frac{100}{12}\rceil=9$个

例子

在30天里，一个棒球队，每天都至少打一场比赛，但是一个月总的比赛场数不超过45场，证明有一段连续的日子，这个棒球队在这段时间里打的比赛的数目正好是14场

solution：

我们用$a_i$表示第i天打的比赛数目，$bi=\sum_{i=1}^{i=j}a_i$,$b_i$表示前i天一共打的比赛数目。$c_i=b_i+14$,那么$15\leq c_i\leq 59$,$b_i$和$c_i$总共是60个数字，那么60个数字放入59个盒子里，肯定有两个数字相等，也就是$b_i=c_j=b_j+14$,得证。

二项式定理

一些性质

帕斯卡定理

$$C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1}$$

重复的排列组合

排列

$$A_n^r=\frac{n!}{(n-r)!}$$

允许重复的排列

$$n^r$$

组合

$$\frac{n!}{r!(n-r)!}$$

允许重复的组合

$$C(n+r-1,r)=C(n+r-1,n-1)=\frac{(n+r-1)!}{r!(n-1)!}$$

允许重复的组合也就是在一个含有n个元素的集合里，选出r个元素，每次选出的元素可以相同也可以不同

例子

假如有4种饼干，现在要从这四种饼干里选出6个，请问有多少种选法

solution：

4是集合元素的个数(n)，6是要选出的个数(r),故

$$C_{n+r-1}^{r}=C_9^6=84$$

例子

$x_1+x_2+x_3=11$有多少组解

solution：

假设每选一次$x_i$就代表$x_i$加一，那么元素个数为3，选的次数为11，所以

$$C_{3+11-1}^{11}=C_{3+11-1}^{3-1}=C_{13}^2=78$$

例子

$x_1+x_2+x_3+x_4+x_5=21$在满足条件$0\leq x_1\leq 10$的前提下有多少组解

solution:

用没有限制的解的个数减去在$10<x_1$的条件下解的个数。

本章总结：

1. 递归关系在计数中的运用
2. 求解线性递归关系
   • 齐次递归关系
   • 非齐次递归关系
3. 生成函数在计数中的运用

递归关系的运用

• 斐波那契数
• 汉诺塔问题
• 计数问题

斐波那契数

在一座小岛上放一对刚出生兔子。每一对兔子直到出生两个月后才开始繁衍，当他们两个月大的时候，以后每一个月他们都会产生一对兔子，找到兔子数量与月数的递归关系。

$$a_n = a_{n-1}+a_{n-1}(a_1=1,a_2=1)$$ $$a_1=1$$ $$a_2=1$$

汉诺塔问题

在每次只能移动一个圆盘，同时，大圆盘不能放在小圆盘之上的条件下，求把一堆圆盘从一根柱子移到另一根柱子上所需要的步数的递推关系。

$$a_n=2a_{n-1}+1$$ $$a_1 = 1$$

比特串计数

找出长度为n且没有两个连续的0的比特串的数目的递推关系。

问题的关键是找到一个方法能描述出长度为n的所有满足条件的比特串，我们通过最后一位是0还是1来列举，因为所有满足条件的比特串最后一位要么是0要么是1。如果最后一位是1，那么比特串的数量就等于n-1个长度的比特串的数量，如果最后一位是0，那么比特串的数量就等于最后一位是1且长度为n-1的比特串数量，也就是长度为n-2的比特串数量。

$$a_n = a_{n-1}+a_{n-2}$$ $$a_0 = 0$$ $$a_1 = 1$$

作业题：

1.找出至少含有两个连续的0的长度为n比特串数量的递推关系

SOLUTION:

如果最后一位是1，那么就是$a_{n-1}$个串

如果最后一位是0：

​ 如果倒数第二位是0：$2^{n-2}$个

​ 如果倒数第二位是1：$a_{n-2}$个

故

$$a_n=a_{n-1}+a_{n-2}+2^{n-2}$$

找出不含连续相同数字的三元串的数量（三元串是指由012三个数字组成的字符串）

SOLUTION:

每一个长度为n-1的串都对应两个长度为n的串，故

$$a_n = 2a_{n-1}$$

求解线性递归关系

• 线性齐次

求解线性齐次的递归方程我们是通过求解特征方程的根来解决问题的，对于如下的递归关系

$$a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}$$

满足c1到ck都是常数，且最后一项ck不等于零，我们就称为线性齐次递归关系，可以用特征根法求解。

我们以特征方程有两个不同根的情况为例，数列的通项可以如下表示

$$a_n = α_1r_1^n + \alpha_2r_2^n$$

如果特征方程存在等根，那么$a_n$的一般表示方法如下

$$a_n=\sum_{i=1}^t(\sum_{j=0}^{m_i-1}\alpha_{i,j}n^j)r_i^n$$

其中$m_i$是每个根的重复度，$t$是不等根的个数，比如2,2,2,5,5,9这一组解中，2的重复度就为3，$m_2=3$,$t=3$

• 线性不齐次

对于下面这种形式的递推关系

$$a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}+F(n)$$

其中$F(n)$是只与n有关的函数式，这种形式就不能简单地用特征方程求解。

我们通过$F(n)$的形式得出$f(n)$的一般方程，通过待定系数法求解

我们将该方程分为两部分：一部分是齐次递推关系的通解，通过忽略非齐次项得到，另一部分是非齐次递推关系的特解，特解的形式通常依赖于非齐次项的形式，最终解的形式即为特解和通解的形式相加得到。

在s不等于特征方程的根的情况下，如果非齐次项的形式如下

$$F(n)=(b_tn^t+b_{t-1}n^{t-1}+....+b_1n+b_0)S^n$$

那么特解的形式就应该是

$$f(n)=(p_tn^t+p_{t-1}n_{t-1}+.....p_1n+p_0)s^n$$

如果s是一个根的话，那么

$$f(n)=n^m(p_tn^t+p_{t-1}n_{t-1}+.....p_1n+p_0)s^n$$

其中m是s的重复度。

让我们看一个更复杂的例子：

求解该递推方程

$$a_n=5a_{n-1}-6a_{n-2}+2^n+3n,a_0=0,a_1=1$$

我们将该方程视为两个递归关系的和，分别求解两个递归关系，然后将两个解相加即可

$$a_n=5a_{n-1}-6a_{n-2}+2^n$$ $$a_n=5a_{n-1}-6a_{n-2}+3n$$

最后得到

$$a_n=c_12^n+c_23^n+p_0n2^n+p_1n+p_2$$

带入n=1,n=0,解出系数即可。

生成函数

对于序列$a_n$,他的生成函数是

$$G(x)=a_0+a_1x+a_2x^2+...+a_kx^k+...=\sum_{k=0}^\infty a_kx^k$$

利用生成函数解决计数问题

找到下面这个方程解的个数

$$x_1+x_2+x_3=17$$

其中变量满足下列条件

$$2\leq x_1\leq 5,3\leq x-2\leq 6,4\leq x_3\leq7$$

解

我们把要求解的数字看作系数，那么

$$(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$$

所得到的$x^{17}$的系数就是解的个数。

如果我们有若干个1￥，2￥，5￥的硬币，我们想通过这些硬币的组合买一件r￥的商品，有多少种组合方式

解

• 不考虑组合顺序

$$(1+x+x^2+x^3+x^4+……)(1+x^2+x^4+x^6+……)(1+x^5+x^{10}+x^{15}+x^{20}+……)$$

• 考虑组合顺序

$$\sum_{n=0}^\infty(x+x^2+x^5)^n$$

用生成函数解决递归方程

用生成函数解下面这个递归方程

$$a_n=8a_{n-1}+10^{n-1},a_1=9,a_0=1$$

解

$$a_nx^n=8a_{n-1}x^{n}+10^{n-1}x^n$$ $$G(x)=\sum_{n=0}^\infty a_nx^n$$ $$G(x)-1=\sum_{n=1}^\infty a_nx^n=8\sum_{n=1}^\infty a_{n-1}x^n+\sum_{n=1}^\infty 10^{n-1}x^n$$ $$=8x\sum_{n=1}^\infty a_{n-1}x^{n-1}+x\sum_{n=1}^\infty10^{n-1}x^{n-1}$$ $$=8x\sum_{n=0}^\infty a_nx^n+x\sum_{n=0}^\infty10^nx^n$$ $$G(x)=\sum_{n=0}^\infty 1/2(8^n+10^n)x^n$$

对应可得到zh$a_n=1/2(8^n+10^n)$

下面这个多项式(广义二项式定理）

$$(1+x+x^2+x^3+x^4+……)^k$$

x次数为n时，其前面的系数为

$$a_n=C(n+k-1,n)$$

容斥原理

$$|A_1\cup A_2\cup A_3\cup……\cup A_n|=\\\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i\leq j\leq n}|A_i\cap A_j|……+(-1)^{n+1}|A_1\cap A_2\cap A_3\cap……\cap A_n|$$

语言描述，n个集合并集的模等于,n个集合的模的和，减去每一对集合交集的模，加上每三个集合交集的模，减去每四个集合交集的模……这样交替计算，直到算完n个集合交集的模

用容斥原理求满射函数的个数

定理：定义域有m个元素，值域有n个元素，建立在这样的集合上的满射函数的个数为

$$n^m - C(n,1)(n-1)^m+C(n,2)(n-2)^m-……+(-1)^{n-1}C(n,n-1)(n-(n-1))^m$$

例子

有3个小朋友，6个玩具，有多少种分配方法使得每个小朋友都至少拿到一个玩具呢

SOLUTION:

把小朋友看成值域，玩具看成定义域，小朋友拿到玩具看成玩具到小朋友的一个映射，那么此题即求从大小为6的定义域到大小为3的值域的满射函数的个数。

$$3^6-C(3,1)(3-1)^6+C(3,2)(3-2)^6=540$$

重排：排序后，原来的每一样物品都不在自己原来的位置上。

$$D_n=n!-C(n,1)(n-1)!+C(n,2)(n-2)!-……+(-1)^nC(n,n)(n-n)!$$