「营业日志 2021.2.5」反射容斥的代数推导

· · 个人记录

设 Q(x,t) 是由 \{\overline 1,1\} 所构成的游走方案，即 Q(x,t) = \sum_{n,k} a_{n,k} x^nt^k 表示从 0 位置走 k 步，最后走到 n 位置，且过程中坐标均 \ge 0 的方案数。

首先这个方程应该大致长这样：

Q(x,t) = 1 + (\overline x + x)t Q(x,t) - \overline xQ(0,t)

其中 \overline x = x^{-1}。

于是就有

K(x,t) \cdot xQ(x,t) = x - Q(0,t)

此时我们代入 x\mapsto \overline x，注意到 K(x,t) = 1 - (\overline x + x)t 在作用下不变，就有了第二个方程

K(x,t) \cdot \overline xQ(\overline x,t) = \overline x - Q(0,t)

两式做差，就有

\begin{aligned} K(x,t) \cdot (xQ(x,t) - \overline x Q(\overline x ,t)) &= x - \overline x\\ xQ(x,t) - \overline x Q(\overline x ,t) &= \frac{x - \overline x}{1 - (\overline x + x)t} \end{aligned}

接下来是一个重要观察，xQ(x,t) 的系数全都在 x 的正次幂，而 \overline x Q(\overline x,t) 的系数全在负次幂，因此 Q(x,t) 的系数和

\frac{1 - \overline {x^2}}{1 - (\overline x + x)t}

的非负次项是一致的！将式子展开，我们就得到了和反射容斥相同的结果。

这样方法在高维情况具有一些扩展，参看 Counting walks with large steps in an orthant, Journal of the European Mathematical Society, Alin Bostan, Mireille Bousquet-Mélou, Stephen Melczer。