【组合数学：五】

• 线性齐次递推关系（下）
• 非齐次递推关系
• 求解卡特兰数的例子

线性齐次递推关系（下）

• 例子：递推关系
  h n = 4 h n − 1 − 4 h n − 2 h_n=4h_{n-1}-4h_{n-2} hn​=4hn−1​−4hn−2​
  有特征方程
  x 2 − 4 x + 4 = ( x − 2 ) 2 = 0 x^2-4x+4=(x-2)^2=0 x2−4x+4=(x−2)2=0
  于是 $2$ 是二重特征根。在这种情况下，变成
  h n = c 1 2 n + c 2 2 n = c 2 n h_{n}=c_12^n+c_22^n=c2^n hn​=c1​2n+c2​2n=c2n
  其中 c = c 1 + c 2 c=c_1+c_2 c=c1​+c2​ 是一个新常数。但这不总是可以做到的。假如初始值是 h 0 = 1 , h 1 = 3 h_0=1,h_1=3 h0​=1,h1​=3，那么容易得到 $c$ 是无解的。
  因此， h n = c 2 n h_n=c2^n hn​=c2n 不是给定递推关系的通解。
  某个特征根是重根，我们就需要寻找与这个根相关的其他解法。
  下面证明 n 2 n n2^n n2n 也是一个解。
  h n − 4 h n − 1 + 4 h n − 2 = n 2 n − 4 ( n − 1 ) 2 n − 1 + 4 ( n − 2 ) 2 n − 2 = 0 h_n-4h_{n-1}+4h_{n-2}=n2^n-4(n-1)2^{n-1}+4(n-2)2^{n-2}=0 hn​−4hn−1​+4hn−2​=n2n−4(n−1)2n−1+4(n−2)2n−2=0
  我们现在断言：
  h n = c 1 2 n + c 2 n 2 n h_n=c_12^n+c_2n2^n hn​=c1​2n+c2​n2n
  更一般的，如果 $q$ (可能是复数) 是常系数线性齐次递推关系的特征方程的 $s$ 重根，那么可以证明
  h n = c 1 q n + c 2 n q n + c 3 n 2 q n + ⋯ + c s n s − 1 q n h_n=c_1q^n+c_2nq^n+c_3n^2q^n+\cdots+c_sn^{s-1}q^n hn​=c1​qn+c2​nqn+c3​n2qn+⋯+cs​ns−1qn
  对常数 c 1 , ⋯ , c s c_1,\cdots,c_s c1​,⋯,cs​ 的每一种选择也是一个解
• 定理：设 q 1 , ⋯ , q t q_1,\cdots,q_t q1​,⋯,qt​ 为常系数线性齐次递推关系
  h n = a 1 h n − 1 + a 2 h n − 2 + ⋯ + a k h n − k , a k ≠ 0 ( n ≥ k ) h_n=a_1h_{n-1}+a_2h_{n-2}+\cdots+a_kh_{n-k},\quad a_k\ne 0\quad (n\ge k) hn​=a1​hn−1​+a2​hn−2​+⋯+ak​hn−k​,ak​​=0(n≥k)
  的特征方程的互不相同的根。如果 q i q_i qi​ 是特征方程的 s i s_i si​ 重根，那么这个递推关系中对应于 q i q_i qi​ 的部分是：
  H n ( i ) = ( c 1 + c 2 n + ⋯ + c s i n s i − 1 ) q i n H_{n}^{(i)}=(c_1+c_2n+\cdots+c_{s_i}n^{s_i-1})q_i^n Hn(i)​=(c1​+c2​n+⋯+csi​​nsi​−1)qin​
  这个递推关系的通解是：
  h n = H n ( 1 ) + H n ( 2 ) + ⋯ + H n ( t ) h_n=H_n^{(1)}+H_{n}^{(2)}+\cdots+H_n^{(t)} hn​=Hn(1)​+Hn(2)​+⋯+Hn(t)​
  但在实际应用上，我们很难求得多项式的所有根而受到限制。
  但是我们还是可以利用生成函数来求解（至少在理论上）任意 $k$ 阶常系数线性齐次递推关系。
  相应的生成函数是形如 $p(x)/q(x)$ 的函数，其中 $p(x)$ 是次数小于 $k$ 的多项式，而 $q(x)$ 是常数项等于 $1$ 的 $k$ 阶多项式。为了求数列项的生成函数，首先，我们用部分分式法把 $p(x)/q(x)$ 表示成如下形式的代数分式的和
  c ( 1 − r x ) t \frac{c}{(1-rx)^t} (1−rx)tc​
  其中 $t$ 是正整数，$r$ 是实数，$c$ 是常数。于是我们可以求出该分式的幂级数，把项加起来，就得到生成函数的幂级数。
• 例子：设 h 0 , h 1 , ⋯ , h n , ⋯ h_0,h_1,\cdots,h_n,\cdots h0​,h1​,⋯,hn​,⋯ 是满足下面递推关系的数列：
  h n + h n − 1 − 16 h n − 2 + 20 h n − 3 = 0 ( n ≥ 3 ) h_n+h_{n-1}-16h_{n-2}+20h_{n-3}=0\quad (n\ge 3) hn​+hn−1​−16hn−2​+20hn−3​=0(n≥3)
  其中 h 0 = 0 , h 1 = 1 , h 2 = − 1 h_0=0,h_1=1,h_2=-1 h0​=0,h1​=1,h2​=−1 。求 h n h_n hn​ 的通项公式。
  设 g ( x ) = ∑ i = 0 ∞ h i x i g(x)=\sum_{i=0}^\infin h_ix^i g(x)=∑i=0∞​hi​xi 是上述数列的生成函数。把下面四个方程
  g ( x ) = h 0 + h 1 x + h 2 x 2 + ⋯ + h n x n + ⋯ x g ( x ) = h 0 x + h 1 x 2 + ⋯ + h n − 1 x n + ⋯ − 16 x 2 g ( x ) = − 16 h 0 x 2 − ⋯ − 16 h n − 2 x n − ⋯ 20 x 3 g ( x ) = 20 h 0 x 3 + ⋯ + 20 h n − 3 x n + ⋯ \begin{aligned} g(x)&=h_0+h_1x+h_2x^2+\cdots+h_nx^n+\cdots\\ xg(x)&=h_0x+h_1x^2+\cdots+h_{n-1}x^n+\cdots\\ -16x^2g(x)&=-16h_0x^2-\cdots-16h_{n-2}x^n-\cdots\\ 20x^3g(x)&=20h_0x^3+\cdots+20h_{n-3}x^n+\cdots \end{aligned} g(x)xg(x)−16x2g(x)20x3g(x)​=h0​+h1​x+h2​x2+⋯+hn​xn+⋯=h0​x+h1​x2+⋯+hn−1​xn+⋯=−16h0​x2−⋯−16hn−2​xn−⋯=20h0​x3+⋯+20hn−3​xn+⋯​
  加起来，我们得到
  ( 1 + x − 16 x 2 + 20 x 3 ) g ( x ) = h 0 + ( h 1 + h 0 ) x + ( h 2 + h 1 − 16 h 0 ) x 2 (1+x-16x^2+20x^3)g(x)=h_0+(h_1+h_0)x+(h_2+h_1-16h_0)x^2 (1+x−16x2+20x3)g(x)=h0​+(h1​+h0​)x+(h2​+h1​−16h0​)x2
  带入 h 0 , h 1 , h 2 h_0,h_1,h_2 h0​,h1​,h2​，我们得到
  g ( x ) = x 1 + x − 16 x 2 + 20 x 3 g(x)=\frac{x}{1+x-16x^2+20x^3} g(x)=1+x−16x2+20x3x​
  我们看到分子 = ( 1 − 2 x ) 2 ( 1 + 5 x ) =(1-2x)^2(1+5x) =(1−2x)2(1+5x)。因此我们能得到：
  g ( x ) = x 1 + x − 16 x 2 + 20 x 3 = c 1 1 − 2 x + c 2 ( 1 − 2 x ) 2 + c 3 1 + 5 x = − 2 / 49 1 − 2 x + 7 / 49 ( 1 − 2 x ) 2 + − 5 / 49 1 + 5 x g(x)=\frac{x}{1+x-16x^2+20x^3}=\frac{c_1}{1-2x}+\frac{c_2}{(1-2x)^2}+\frac{c_3}{1+5x}=\frac{-2/49}{1-2x}+\frac{7/49}{(1-2x)^2}+\frac{-5/49}{1+5x} g(x)=1+x−16x2+20x3x​=1−2xc1​​+(1−2x)2c2​​+1+5xc3​​=1−2x−2/49​+(1−2x)27/49​+1+5x−5/49​
  然后，展开幂级数项，我们直接能得到：
  g ( x ) = ∑ k = 0 ∞ ( − 2 49 2 k + 7 49 ( k + 1 ) 2 k − 5 49 ( − 5 ) k ) x k g(x)=\sum_{k=0}^\infin \Big( -\frac{2}{49}2^k + \frac{7}{49}(k+1)2^k -\frac{5}{49}(-5)^k \Big) x^k g(x)=k=0∑∞​(−492​2k+497​(k+1)2k−495​(−5)k)xk
  所以我们就得到了：
  h n = − 2 49 2 n + 7 49 ( n + 1 ) 2 n − 5 49 ( − 5 ) n h_n=-\frac{2}{49}2^n + \frac{7}{49}(n+1)2^n -\frac{5}{49}(-5)^n hn​=−492​2n+497​(n+1)2n−495​(−5)n

非齐次递推关系

• 通常情况下，非齐次递推关系更难求解，而且通常需要依赖于其非齐次部分。
• 例子：(汉诺塔问题)
  设 h n h_n hn​ 是转移 $n$ 个圆盘所需的移动次数。可以验证 h 0 = 0 , h 1 = 1 , h 2 = 3 h_0=0,h_1=1,h_2=3 h0​=0,h1​=1,h2​=3
  为了把 $n$ 个圆盘转移到另一根柱子上，我们必须首先把一根珠子上顶部 $n-1$ 个盘子转移到穿有最大圆盘的那根珠子上。因此
  h n = 2 h n − 1 + 1 ( n ≥ 1 ) h_n=2h_{n-1}+1\quad(n\ge 1) hn​=2hn−1​+1(n≥1)
  通过反复递推带入，我们可以得到 h n = 2 n − 1 h_n=2^n-1 hn​=2n−1
• 例子：(汉诺塔的生成函数解法)
  首先我们有
  h n = 2 h n − 1 + 1 ( n ≥ 1 ) , h 0 = 0 h_n=2h_{n-1}+1(n\ge 1),h_0=0 hn​=2hn−1​+1(n≥1),h0​=0
  设
  g ( x ) = ∑ n = 0 ∞ h n x n g(x)=\sum_{n=0}^\infin h_nx^n g(x)=n=0∑∞​hn​xn
  于是我们有：
  g ( x ) = h 0 + h 1 x + h 2 x 2 + ⋯ + h n x n + ⋯ − 2 x g ( x ) = 2 h 0 x + ⋯ + 2 h n − 1 x n + ⋯ g(x)=h_0+h_1x+h_2x^2+\cdots+h_nx^n+\cdots\\ -2xg(x)=2h_0x+\cdots+2h_{n-1}x^n+\cdots g(x)=h0​+h1​x+h2​x2+⋯+hn​xn+⋯−2xg(x)=2h0​x+⋯+2hn−1​xn+⋯
  把上面两个方程相加，得到
  ( 1 − 2 x ) g ( x ) = x + x 2 + ⋯ + x n + ⋯ = 1 1 − x (1-2x)g(x)=x+x^2+\cdots+x^n+\cdots=\frac{1}{1-x} (1−2x)g(x)=x+x2+⋯+xn+⋯=1−x1​
  因此
  g ( x ) = x ( 1 − x ) ( 1 − 2 x ) = 1 1 − 2 x − 1 1 − x = ∑ n = 0 ∞ ( 2 n − 1 ) x n g(x)=\frac{x}{(1-x)(1-2x)}=\frac{1}{1-2x}-\frac{1}{1-x}=\sum_{n=0}^\infin (2^n-1)x^n g(x)=(1−x)(1−2x)x​=1−2x1​−1−x1​=n=0∑∞​(2n−1)xn

• 例子：求解：
  h n = 3 h n − 1 − 4 n ( n ≥ 4 ) , h 0 = 2 h_n=3h_{n-1}-4n\quad(n\ge4),h_0=2 hn​=3hn−1​−4n(n≥4),h0​=2
  首先我们考虑相应的齐次递推关系 h n = 3 h n − 1 h_n=3h_{n-1} hn​=3hn−1​，它的通解是 h n = c 3 n ( n ≥ 1 ) h_n=c3^n\quad(n\ge 1) hn​=c3n(n≥1)
  下面我们要求原来的非齐次递推关系的一个特殊的解。对于适当的 $r,s$，我们尝试着寻找下面形式的一个解
  h n = r n + s h_n=rn+s hn​=rn+s
  首先我们必须有
  $$\begin{gathered} rn+s=3(r(n-1)+s)-4n \\ rn+s=(3r-4)n+(-3r+3s) \end{gathered}$$
  我们得到
  $$\begin{gathered} r=3r-4 \\ s=-3r+3s \end{gathered}$$
  因此得到 $r=2,s=3$，且 h n = 2 n + 3 h_n=2n+3 hn​=2n+3 满足。现在将齐次关系的通解与费其次关系的特殊解合成，得到
  h n = c 3 n + 2 n + 3 h_n=c3^n+2n+3 hn​=c3n+2n+3
  根据初始条件 h 0 = 2 h_0=2 h0​=2 得到 $c=-1$，因此
  h n = − 3 n + 2 n + 3 h_n=-3^n+2n+3 hn​=−3n+2n+3
  是原来问题的解。

• 上述解法是求解费其次微分方程方法的离散模式。总结如下：
  求齐次关系的通解
  求非齐次关系的一个特殊解
  将通解和特殊解合成，确定通解中的常数值

• 如果 b n b_n bn​ 是 $n$ 的 $k$ 次多项式，可以做如下尝试
  h n = r h_n=r hn​=r 如果 b n = d b_n=d bn​=d
  h n = r n + s h_n=rn+s hn​=rn+s 如果 b n = d n + e b_n=dn+e bn​=dn+e
  h n = r n 2 + s n + t h_n=rn^2+sn+t hn​=rn2+sn+t 如果 b n = d n 2 + e n + f b_n=dn^2+en+f bn​=dn2+en+f
  h n = p d n h_n=pd^n hn​=pdn 如果 b n = d n b_n=d^n bn​=dn

• 例子：求解
  h n = 2 h n − 1 + 3 n ( n ≥ 1 ) , h 0 = 2 h_n=2h_{n-1}+3^n\quad(n\ge 1)\quad ,h_0=2 hn​=2hn−1​+3n(n≥1),h0​=2
  解一：因为齐次关系 h n = 2 h n − 1 h_n=2h_{n-1} hn​=2hn−1​，通解为 h n = c 2 n ( n ≥ 1 ) h_n=c2^n\quad(n\ge1) hn​=c2n(n≥1)
  为找其特殊解，我们做下面的尝试： h n = p 3 n h_n=p3^n hn​=p3n
  那么必须满足 p 3 n = 2 p 3 n − 1 + 3 n p3^n=2p3^{n-1}+3^n p3n=2p3n−1+3n
  解得 $p=3$
  因此 h n = c 2 n + 3 n + 1 h_n=c2^n+3^{n+1} hn​=c2n+3n+1
  带入 h 0 = 2 h_0=2 h0​=2，解得 $c=-1$
  于是得到 h n = − 2 n + 3 n + 1 ( n ≥ 0 ) h_n=-2^n+3^{n+1}\quad(n\ge0) hn​=−2n+3n+1(n≥0)
  解二：利用生成函数。设 g ( x ) = ∑ i = 0 ∞ h i x i g(x)=\sum_{i=0}^\infin h_ix^i g(x)=∑i=0∞​hi​xi
  利用原来的递推关系和 h 0 = 2 h_0=2 h0​=2，我们得到
  g ( x ) − 2 x g ( x ) = h 0 + ( h 1 − 2 h 0 ) x + ⋯ + ( h n − 2 h n − 1 ) x n + ⋯ = 2 + 3 x + 3 2 x 2 + ⋯ + 3 n x n + ⋯ = 2 − 1 + ( 1 + 3 x + 3 x 2 x 2 + ⋯ + 3 n x n + ⋯ ) = 1 + 1 1 − 3 x \begin{aligned} g(x)-2xg(x)&=h_0+(h_1-2h_0)x+\cdots+(h_n-2h_{n-1})x^n+\cdots\\ &=2+3x+3^2x^2+\cdots+3^nx^n+\cdots\\ &=2-1+(1+3x+3x^2x^2+\cdots+3^nx^n+\cdots)\\ &=1+\frac{1}{1-3x} \end{aligned} g(x)−2xg(x)​=h0​+(h1​−2h0​)x+⋯+(hn​−2hn−1​)xn+⋯=2+3x+32x2+⋯+3nxn+⋯=2−1+(1+3x+3x2x2+⋯+3nxn+⋯)=1+1−3x1​​
  因此
  g ( x ) = 1 1 − 2 x + 1 ( 1 − 3 x ) ( 1 − 2 x ) = 1 1 − 2 x + 3 1 − 3 x − 2 1 − 2 x = ∑ n = 0 ∞ ( 3 n + 1 − 2 n ) x n g(x)=\frac{1}{1-2x}+\frac{1}{(1-3x)(1-2x)}=\frac{1}{1-2x}+\frac{3}{1-3x}-\frac{2}{1-2x}=\sum_{n=0}^\infin (3^{n+1}-2^n)x^n g(x)=1−2x1​+(1−3x)(1−2x)1​=1−2x1​+1−3x3​−1−2x2​=n=0∑∞​(3n+1−2n)xn

求解卡特兰数的例子

• 令 h n h_n hn​ 表示把凸 $n+1$ 多边形区域分成三角形区域的方案数。则 h n h_n hn​ 满足递推关系
  h n = ∑ k = 1 n = 1 h k h n − k h_n=\sum_{k=1}^{n=1}h_kh_{n-k} hn​=k=1∑n=1​hk​hn−k​
  我们现在希望求出它的通解。令 h 1 = 1 h_1=1 h1​=1，设
  g ( x ) = ∑ i = 1 ∞ h i x i ( g ( x ) ) 2 = h 1 2 x 2 + ⋯ + ( h 1 h n − 1 + h 2 h n − 2 + ⋯ + h n − 1 h 1 ) x n + ⋯ ( g ( x ) ) 2 = h 1 2 x 2 + h 3 x 3 + h 4 x 4 + ⋯ + h n x n + ⋯ = g ( x ) − h 1 x = g ( x ) − x \begin{aligned} g(x)&=\sum_{i=1}^\infin h_ix^i\\ (g(x))^2&=h_1^2x^2+\cdots+(h_1h_{n-1}+h_2h_{n-2}+\cdots+h_{n-1}h_1)x^n+\cdots\\ (g(x))^2&=h_1^2x^2+h_3x^3+h_4x^4+\cdots+h_nx^n+\cdots\\ &=g(x)-h_1x=g(x)-x \end{aligned} g(x)(g(x))2(g(x))2​=i=1∑∞​hi​xi=h12​x2+⋯+(h1​hn−1​+h2​hn−2​+⋯+hn−1​h1​)xn+⋯=h12​x2+h3​x3+h4​x4+⋯+hn​xn+⋯=g(x)−h1​x=g(x)−x​
  因此，$g(x)$ 满足方程
  ( g ( x ) ) 2 − g ( x ) + x = 0 (g(x))^2-g(x)+x=0 (g(x))2−g(x)+x=0
  根据二次公式，$g(x)$ 有两个根 g 1 ( x ) , g 2 ( x ) g_1(x),g_2(x) g1​(x),g2​(x)，其中
  g 1 ( x ) = 1 + 1 − 4 x 2 , g 2 ( x ) = 1 − 1 − 4 x 2 g_1(x)=\frac{1+\sqrt{1-4x}}{2},g_2(x)=\frac{1-\sqrt{1-4x}}{2} g1​(x)=21+1−4x ​​,g2​(x)=21−1−4x ​​
  由 $g(x)$ 的定义可知 $g(0)=0$，因为 g 1 ( 0 ) = 1 , g 2 ( 0 ) = 0 g_1(0)=1,g_2(0)=0 g1​(0)=1,g2​(0)=0，所以得到 g ( x ) = g 2 ( x ) g(x)=g_2(x) g(x)=g2​(x)
  根据牛顿二项式定理得到
  ( 1 + z ) 1 / 2 = 1 + ∑ n = 1 ∞ ( − 1 ) n − 1 n × 2 2 n − 1 C 2 n − 2 n − 1 z n ( ∣ z ∣ < 1 ) (1+z)^{1/2}=1+\sum_{n=1}^\infin \frac{(-1)^{n-1}}{n\times2^{2n-1}}C_{2n-2}^{n-1}z^n\quad(|z|<1) (1+z)1/2=1+n=1∑∞​n×22n−1(−1)n−1​C2n−2n−1​zn(∣z∣<1)
  用 $-4x$ 替代 $z$ ，则得到
  ( 1 − 4 x ) 1 / 2 = 1 + ∑ n = 1 ∞ ( − 1 ) n − 1 n × 2 2 n − 1 C 2 n − 2 n − 1 ( − 1 ) n 4 n x n = 1 + ∑ n = 1 ∞ ( − 1 ) 2 n − 1 2 n C 2 n − 2 n − 1 x n \begin{aligned} (1-4x)^{1/2}&=1+\sum_{n=1}^\infin \frac{(-1)^{n-1}}{n\times2^{2n-1}}C_{2n-2}^{n-1}(-1)^n4^nx^n\\ &=1+\sum_{n=1}^\infin (-1)^{2n-1}\frac{2}{n}C_{2n-2}^{n-1}x^n\\ \end{aligned} (1−4x)1/2​=1+n=1∑∞​n×22n−1(−1)n−1​C2n−2n−1​(−1)n4nxn=1+n=1∑∞​(−1)2n−1n2​C2n−2n−1​xn​
  因此
  g ( x ) = ∑ n = 1 ∞ 1 n C 2 n − 2 n − 1 x n g(x)=\sum_{n=1}^\infin \frac{1}{n}C_{2n-2}^{n-1}x^n g(x)=n=1∑∞​n1​C2n−2n−1​xn
  所以
  h n = 1 n C 2 n − 2 n − 1 h_n= \frac{1}{n}C_{2n-2}^{n-1} hn​=n1​C2n−2n−1​

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！