递推关系与母函数

『组合数学』2 递推关系与母函数

2.1 递推与递归关系

• 递归
• 汉诺塔
• Fib

2.2母函数

• 母函数

  $G(x) = h(1)x+h(2)x+\cdots+h(n)x^n$

G(x)是序列h的母函数

Hanoi 应用:

$G(x) = 2xG(x) + \frac{x}{1-x}:(x<1)\\ \\G(x) = \frac{x}{(1-2x)(1-x)} = \frac 1{1-2x} -\frac 1{1-x} = \sum^n_{i=0}2^{i}x^i -\sum^n_{i=0}x^i\\h(n) = 2^n - 1$

• 组合数的证明

  $C(n,0)C(m,0)+……+C(n,m)C(m,m) = C(n+m,m)\to (1+x)^n\times (1+(\frac 1x) ^m) =\frac {1}{x^m}(1+x)^{m+n}$

• $2^n$

• 求导函数

2.3 Fibonacci

对Fibonacci等式两边相加易得

$G(x) = x+x^2 + xG(x)-x^2+x^2G(x)\\ G(x) =\frac{x}{1-x-x^2}\\ \alpha = \frac{1+\sqrt 5}{2} , \ \ \beta = \frac{1-\sqrt 5} 2\\ h_n = \frac {\alpha^n-\beta^n}{\sqrt 5} \\lim_{n\to +\infty}= \frac 1{\sqrt 5 }(\frac{1+\sqrt 5}{2})^n$

常见等式：

• $F_1+F_2 +……+F_n = F_{n+2}-1$

• $F_1+F_3 +……+F_{2n-1} = F_{2n}$

• $F^2_1+……+F^2_n = F_nF_{n+1}$

  前两个直接列式即可，第三个变换：$F^2(n) = F(n)(F(n+1)-F(n-1))$累加即可

2.4 母函数的性质

• 现推型：

  $b_k = \begin{cases} 0,\quad \quad \qquad k<l \\ a_{k-l} \qquad k\ge l \end{cases}$ 有$B(x)= x^lA(x)$

  $b_k = a_{k+l}$ 则$B(x) = [A(x)-\sum^{l-1}_{k=0}a_kx^k]/x_l$

  $b_k = \sum^k_{i=0}a_i$ 则$B(x) = \frac{A(x)}{1-x}$

  $b_k = \sum^\infty_{i=k} a_i$ 则$B(x) = \frac{A(1)-xA(x)}{1-x}$

  $b_k = ka_k$则$B(x)=xA^\prime(x)$

  $b_k = \frac{a_k}{1+k}$ 则 $B(x) = \frac{1}{x} \int^x_0A(x)dx$

  $c_k =\sum^k_{i=0}a_ib_{k-i}$则$C(x) = A(x)B(x)$

基本列出式子累加即可，（好像最后一个还是记忆一下。。）

2.5 线性常系数齐次递推关系

• 一般性的线性常系数齐次

  特征多项式：$C(x) = x^k+ c_1 x^{k-1}+....+c_k = 0$

  求得特征方程$C(x) = 0$

  由此得到的确定序列的$G(x) = a_0 + a_1x  +a_2 x^2 + ...$的母函数为

  相加有$G(x) = \frac{P(x)}{R(x)}$

  且有$R(x) =x^kC(\frac 1x)$

且C(x) 复数域中分解为n个根    由此将

$R(x) = (1-\alpha_1 x)^{k_1}(1-\alpha_2 x)^{k_2}...(1-\alpha_n x)^{k_n}$

定理2-1

有理分式$\frac{P(x)}{R(x)}$有P(x)<R(x)，则可化为唯一的部分分式表示

• 有k重根

  • 数学归纳法，n次时变为更小次项得证

• 一般化：

  • 特征方程没有重根

    • 可直接求得G( x )
    • 证明：
      • 范德蒙行列式不为零，$\because$无重根$\to$唯一
    • 特征方程的根有复数
      • 对于共轭复根，特殊表示形式：
    • 特征方程有重根：
    • 对每一次的n次项各项求和得：

    $a_n =\sum_{j=1}^kA_jC(n+j-1,j-1)a^n\\$

• TODO： 回去证明下

非齐次递推关系

基础做法：

1. 可解的情况非齐次为$b_ns^n$, 依次代入原方程中得到一特解

2. 非齐次为$r^n b(n)$则有特解的形式为：

   $r^n(k_0n^m+k_1n^{m+1}+...+ k_pn^{m+p})$

   1. 其中r为方程的m重根，
   2. b（n）是n的p次多项式，
   3. 若r不是根，令m = 0
   4. 练习
      • $1+2+……+n = S_n$

则有$S_n -3S_{n-1}+3S_{n-2}-1= 0$

• 不断降阶有$特征方程为(x-1)^4 = 0的方程$

• 由此方法求得

• 例题：

  求$G(x) = \frac 1{(1-x)(1-x^2)(1-x^3)}$中$中x^n$的系数$a_n$

  • $G(x) = \frac{1}{(1-x)^3\times(1+x)\times(1+x+x^2)}$

2.7 整数的拆分

• 整数分解为若干整数的和

  以一题为例更好说明：一克的砝码$3$枚，$2$克的砝码$4$枚，$4$克的砝码$2$枚，试问能称出多少种重量，各有多少种称法

  $G(x) = (1+x+x^2+x^3)(1+x^2+x^4+x^6+x^8)(1+x^4+x^8) = \\ \qquad \qquad \qquad = 1+x+2x^3+.....+5x^{11}+...+x^{19}$

  其中$5x^{11}$表示组合成11共有五种方法

2.8 指数型母函数

仍是以例题为例更好说明：$8$个元素中$a_1$重复了$3$次，$a_2$重复了$2$次，$a_3$重复了$3$次，从中取$r$个组合，其组合数为$c_r$.

若求母函数时将$x$分为$x_1,x_2,x_3$则可知道对应的四次项(取四个组合)中的来源，从而根据去重原理计算。但是目前有更好的方法：

有$G_e(x) = (1+\frac 1x + \frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac 1x + \frac{x^2}{2!})(1+\frac 1x + \frac{x^2}{2!}+\frac{x^3}{3!}) = 1+...+\frac{70}{4!}x^4...$

而取$4$个球的组合数正是系数。巧妙的解决了问题

2.9.1 Ferrers 图像

共轭Ferrers图：

• def：
  • 将行列互换，关于 y = -x 对称的一对图形成为一对共轭Ferrers图形

推出结论：

• 整数$n$拆分为$k$个数的和的拆分 $=$ 数$n$差分成最大数为k的拆分数相等。

• 整数$n$拆分成最多不超过$m$个数的和的拆分数，和$n$拆分成最大不超过$m$的拆分数相等

  并且有正好拆分成$m$个数的母函数为：

  $\frac{x^m}{(1-x)(1-x^2)…(1-x^m)} \qquad \qquad \qquad (1)$

• 整数$n$拆分成互不相同的若干奇数的和的拆分书，和$n$拆分成自共轭的Ferrers图像的拆分数相等

2.9.2 错排

• 递推关系：$D_n = (n-1) (D_{n-1}+D_{n-2})$

  基本解释：$(n-1) D_{n-1}=$ 先将$n-1$元素错排，选一交换

  $(n-1) D_{n-2}=$ 先选一交换，再对剩余$n-2$元素错排

  更进一步有：

  $D_n-nD_{n-1} = -(D_{n-1}-(n-1)D_{n-2}) \\D_n-nD_{n-1} = (-1)^n$

  其幂次母函数：$G_e(x) = D_0+\frac{D_1x}{1!}+……+\frac{D_nx}{n!}$

  并且由$D_n-nD_{n-1} = (-1)^n$

  即$G_e(x)-xG_e(x) = e^{-x}\\\quad G_e(x) = \frac{e^{-x}}{1-x}$

2.9.3 广义二项式定理

$(1-y)^\alpha = 1-\alpha y+\frac{\alpha(\alpha-1)}{2!}y^2-\frac{\alpha(\alpha -1)(\alpha-2)}{3!}y^3+……+(-1)^r\frac{\alpha(\alpha -1)(\alpha-2)……(\alpha -r+1)}{r!}y^r+……$

例题：序列$\left\{ 1,1\times3,1\times3\times5,…… \right\}$的母函数

2.10 非线性递推关系

• Stirling 数
• 双参数

引入：对$n$个有区别的球放到两个有区分的盒子里，若要求第一个盒子方$k$个球，第二个盒子放$n-k$个球$（k = 0,1,2,……,n）$则方案书应为$（x_1+x_2）^n$中$x_1^kx_2^{n-k}$的系数$C(n,k)$

若推广至$n$个不同的球放置在$m$个不同的盒子中，则不同的方案数为：

$\dbinom{n}{n_1n_2\cdots n_m} = \frac{n!}{n_1!n_2!\cdots n_m!}$

• 定理2-10-1$(x_1+x_2+\cdots+x_m)^n$展开式项数=$\dbinom {n+m-1}{n}$

• 证明：

  取m个允许重复的组合的全体，再去重

【定义1：】：$[x]_n = x(x-1)\cdots(x-n+1) = s(n,0)+s(n,1)x+s(n,2)x^2+\cdots+s(n,n)x^n$

称其中为第一类$Sritling$数

易知：$s(n+1,k) = s(n,k-1)-ns(n,k)$

【定义2：】n个有区别的球放到m个相同的盒子中，并要求无一空盒，其不同的方案用$S(n,m)$表示，成为第二类$Stirling$数

• 性质如下：
  • $S(n,0) = 0,S(n,1) = 1\\S(n,2) = 2^{n-1}-1,S(n,n-1) = C(n,2),S(n,n) = 1$
  • S(n,2)证明：排除掉全部在一个盒子的情况
• 【定理2-10-3】第二类$Stirling$数，满足如下递推公式
  • $S(n,m) = mS(n-1,m)+S(n-1,m-1),\qquad (n>1,m\ge 1)$

最后给出$Stirling$公式的计算公式

$S(n,m) = \frac 1{m!}\sum^{m-1}_{k=0} (-1)^k\dbinom mk(m-k)^n$

• $Catalan$数

  • def
    • 凸n变形，不相交于n变形内部的对角线，拆分为三角形
    • 其不同拆分数$C_n$为卡特兰数

  1. $Catalan$递推关系

     $C_{n+1} = C_2C_n+C_3C_{n-1}+……+C_nC_2$

     • 证明

       以$v_1 v_{n+1}$为固定边，$v_k$为另一顶点，分割成三角形+k边形与$n-k+2$边形 ，可知彼此间不重复

     $(n-3)C_n = \frac{n}{2} (C_3C_{n-1}+……+C_{n-1}C_3)$

     • 证明

       取$V_1 V_2 V_n$为四边形三个顶点，

       • 等式右侧：以某点的两边为邻边，选一个顶点作对角线，有$n-3$个，可重复执行$n$次，且对于无向直线划分的区域相同，$\div\ C^2_2$

       • 等式左侧：计算中，每次$n$边形进行剖分后都使用了$n-3$条对角线，也即是重复了$n-3$ 。（其实单看了好多遍这一句话不太理解。。）

         但是可以想到的是对于每次剖分需要$n-3$条边，每一次使用对角线划分成的两个区域中，剩余的$n-4$条连线早晚也会被用作“对角线”，因此算上原本的一次便是重复了$n-3$次

         自认为终于是理解了QAQ

  2. $Catalan$数计算公式

     $C_{n+1} = \frac 1n \dbinom{2n-2}{n-1}$

     • 证明：

       $(C_3C_{n-1}+……+C_{n-1}C_3) = C_{n+1}-2C_n\\ \Rightarrow (n-3)C_n = \frac n2(C_{n+1}-2C_n) \\ \Rightarrow nC_{n+1} = (4n-6)C_n$

       令$nC_{n+1} = H_{n+1}$