闲话
好久没写闲话了。大家是不是都忘记我了？
大家好啊，我是[数据删除]；今天来点大家[已编辑]想看的东西啊。
可能这个方法很古老，但是多个方法多条路(?)
浅谈如何用 50 多年前的学术界分析方法求二元生成函数的对角线
抄一点复变函数基础
复分析是研究 \(\mathbb C\) 上的函数——即复变函数，特别是亚纯函数、复解析函数等函数——的理论。下文默认读者拥有高中级别的复数知识，或阅读过此 OI Wiki 页面。
（开）圆盘：一个以 \(z_0\) 为圆心、\(r\) 为半径的开圆盘为集合 \(D(z_0, r) = \{z : \lvert z - z_0 \rvert < r\}\)。特别的，\(D(0, 1)\) 被称为单位圆盘。
区域：\(S\subset \mathbb C\) 是区域，当且仅当其是一个非空的道路连通开集，即 \(\forall z \in S, \exists r > 0, D(z, r) \subset S\)，且任意 \(S\) 内两点都可以被有限条完全包含在 \(S\) 内的线段首尾连接地相连。
边界：对区域 \(S\)，记其边界为 \(\partial S\)。\(z_0\) 在 \(S\) 的边界 \(\partial S\) 上（或称 \(z_0\) 是 \(S\) 的边界点），当且仅当 \(z_0\) 满足 \(\forall r > 0, D(z_0, r) \cap S \neq \varnothing\) 且 \(D(z_0, r) \cap \mathbb (C \setminus S) \neq \varnothing\)。
曲线：一条曲线 \(\gamma\) 形如 \(z = z(t), t \in [a,b]\)。若 \(z(a) = z(b)\) 那么其是闭曲线。若 \(\forall t_1 \in (a, b), t_2 \in [a,b]\)，\(t_1 \neq t_2 \to z(t_1) \neq z(t_2)\)，那么曲线是简单的。
有限区域的边界 \(\partial D : z = z(t), t \in [a, b]\) 是一条简单闭曲线。规定其方向是逆时针的，即随着 \(t\) 的增大，\(z(t)\) 从某点开始，沿着逆时针方向（向下一刻所在位置看去，此时位置的左侧是区域内部）绕简单闭曲线一圈。
曲线积分：复变函数 \(f(z)\) 沿曲线 \(\gamma\) 的曲线积分为
\[\int_\gamma f(z) \mathrm dz = \int_a^b f(z(t)) z'(t) \mathrm dt = F(z(b)) - F(z(a)) \]其中 \(F\) 为 \(f\) 的原函数（不一定存在）。
\(\textbf{定义 1 }\text{(复导数，全纯函数)}\)
设映射 \(f : U \to \mathbb C\)，其中 \(U \subset \mathbb C\) 为开集。设 \(z_0 \in U\)，则 \(f\) 在 \(z_0\) 处的复导数（若存在）定义为
\[f'(z_0) = \lim_{z \to z_0} \dfrac{f(z) - f(z_0)}{z - z_0} \]其中 \(z\) 可以从各个方向任意地趋近 \(z_0\)。若 \(\exists r > 0\)，\(f\) 在 \(D(z_0, r)\) 内都有复导数，就称 \(f\) 在 \(z_0\) 处解析。若 \(f\) 在 \(U\) 中每点都有复导数，就说 \(f\) 为 \(U\) 上的全纯函数。
整（entire）函数是在 \(\mathbb C\) 上全纯的函数。注意：函数只能是开区域上的全纯函数，若区域内有边界点，这个点处的复导数是不存在的。
Cauchy-Riemann 方程：将复平面的坐标写作 \(z = x + \mathrm iy\)，考虑开集上的复变函数 \(f(x, y) = u(x, y) + \mathrm iv(x, y)\)，其中 \(u, v\) 是实值函数，那么 \(f\) 全纯当且仅当其满足 Cauchy-Riemann 方程
\[\left\{\begin{aligned} \dfrac{\partial u}{\partial x} &= \dfrac{\partial v}{\partial y} \\ \dfrac{\partial u}{\partial y} &= -\dfrac{\partial v}{\partial x} \end{aligned}\right. \]\(\textbf{定理 1 }\text{(Cauchy 定理)}\)
设 \(f\) 在圆盘 \(D\) 上全纯，闭曲线 \(\gamma \subset D\)，那么
\[\int_\gamma f(z) \mathrm dz = 0 \]
这可以推知，若 \(f\) 在包含了圆周 \(C\) 和其内部的区域上全纯，那么 \(\int_C f(z) \mathrm dz = 0\)。
奇点（singular）：\(f\) 在该点不全纯。
- 可去奇点：若 \(U \subset \mathbb C\) 是开集，\(z_0\) 是 \(U\) 中一点，\(f : (U \setminus \{z_0\}) \to \mathbb C\) 是全纯函数，若存在一个在 \(U\) 上全纯的函数 \(g(z)\)，使得 \(\forall z \in (U \setminus \{z_0\}), f(z) = g(z)\)，那么 \(z_0\) 是 \(f\) 的一个可去奇点，并称 \(f\) 在 \(z_0\) 点可以全纯延拓。（其等价于 \((z - z_0) f(z)\) 在 \(z_0\) 处的极限为 \(0\)）
- 极点（poles）：若存在 \(m \in \mathbb N\)，\((z - a)^{m + 1} f(z)\) 在不可去极点 \(z_0\) 处的极限为 \(0\)，那么称 \(z_0\) 为 \(f\) 的一个极点，最小的满足上述条件的 \(m\) 称为 \(z_0\) 的阶。由此也知道可去极点恰为零阶奇点。（在极点附近全纯的函数在趋近极点时一致发散到无穷远处）
- 本性奇点：若 \(f\) 的一个孤立奇点既非可去奇点，也非极点，那么其即为本性奇点。
半纯函数：除了可数个奇点外全纯的函数。
\(\textbf{定理 2 }\text{(Laurent 展开)}\)
设 \(f(z)\) 在以 \(z_0\) 为圆心的圆环 \(\{z : r < \lvert z - z_0 \rvert < R\}\) 上解析，那么对环内部任意一点 \(z\)，都可以找到一个（唯一的）级数，满足
\[f(z) = \sum_{n = -\infty}^{\infty} c_n (z - z_0)^n \]\(c_n\) 可为 \(0\)。其中 \(n \ge 0\) 的部分被称为正则部分（normal part，或解析部分），其在 \(D(z_0, R)\) 内绝对收敛；\(n < 0\) 的部分被称为主要部分（简称主部），其在 \(D(z_0, r)\) 外绝对收敛。
无穷远处展开：设 \(f(z)\) 在圆环 \(\{z : r < \lvert z - z_0 \rvert < \infty\}\) 上解析，那么令 \(s = 1/z\)，\(g(s) = f(1/z)\) 在 \(D(0, 1/r) \setminus \{0\}\) 上解析，将 \(g\) 在 \(0\) 处展开，得到 \(g(s) = \sum_{n} c_n s^n\)，且当 \(z\to\infty\) 时 \(f(z)\) 与 \(s\to 0\)时 \(g(s)\) 的极限状态相同，故 \(f\) 在无穷远处的 Laurent 级数为 \(\sum_n c_{-n} z^n\)。
我们也可以用函数的 Laurent 展开考察奇点的情况。若 \(f\) 在 \(z_0\) 处的 Laurent 展开式不含负次幂项，则 \(z_0\) 为 \(f\) 的可去奇点；若只有有限个负次幂项，则为极点；若有无限个负次幂项，则为本性奇点。
\(\textbf{定义 2 }\text{(留数)}\)
若 \(f\) 的一个孤立奇点为 \(z_0\)，那么 \(\exists r > 0\)，\(f\) 在 \(D(z_0, r) \setminus \{z_0\}\) 上解析，Laurent 展开式为 \(\sum_n c_n (z - a)^n\)，那么 \(f\) 在 \(z_0\) 处的留数
\[\text{Res}(f, z_0) = c_{-1} = \int_\gamma f(z) \mathrm dz \]其中 \(\gamma\) 为 \(D(z_0, r) \setminus \{z_0\}\) 中的一条逆时针可求长曲线。
对无穷远处的留数的定义类似。
由上可知，若 \(z_0\) 为 \(f\) 的 \(m\) 阶极点，那么
\[\text{Res}(f, z_0) = \dfrac{1}{(m-1)!} \lim_{z\to z_0} \dfrac{\mathrm d^{m - 1}}{\mathrm dz^{m - 1}}(z - z_0)^m f(z) \]\(\textbf{定理 3 }\text{(留数定理)}\)
设 \(D \subset \mathbb C\) 是由有限条可求长简单闭曲线围成的区域，若 \(f\) 在 \(D\) 上除孤立奇点 \(z_1,\dots,z_n\) 外都是全纯的，且连续到 \(\partial D\)，那么
\[\dfrac{1}{2\pi \mathrm i} \int_{\partial D} f(z) \mathrm dz = \sum_{k = 1}^n \text{Res}(f, z_k) \]
抄自 M. L. J. Hautus and D. A. Klarner, The diagonal of a double power series, Duke Math. J. 38 (1971), 229–235.
定义二元序列 \(\{f_{m, n} \mid m, n\in \mathbb N\}\) 的对角线序列为 \(\{f_n = f_{n, n} \mid n \in \mathbb N\}\)。本文提出了一种通过 \(f_{m, n}\) 的二元生成函数的积分表示 \(f_n\) 的生成函数的方法。由于这个方法依赖于二元生成函数的封闭形式，一般 \(f_{m, n}\) 具有某些递归关系。
令 \(A(z), B(z)\) 为 \(\{a_n\}, \{b_n\}\) 的普通生成函数，且 \(A(z), B(z)\) 在 \(z = 0\) 的邻域内解析，那么必然存在正实数 \(\alpha, \beta\)，使得
\[A(z) = \sum_{n\ge 0} a_n z^n \qquad B(z) = \sum_{n\ge 0} b_nz^n \]的 Taylor 展开形式分别在圆盘 \(\{z : \lvert z \rvert < \alpha \}, \{z : \lvert z \rvert < \beta \}\) 上成立。那么在圆盘 \(\{z : \lvert z \rvert < \alpha\beta \}\) 上级数
\[C(z) = \sum_{n \ge 0} a_n b_n z^n \]一致绝对收敛，故这个级数表示一个在圆盘上解析的函数 \(C(z)\)。在 Hadamard 乘积定理的证明中，也证明了 \(C(z)\) 的一个积分表示。由于我们关注于这个结论的推广形式，下面会一并写出证明。
证明：我们断言，对所有复数 \(z \text{ s.t. } \lvert z \rvert < \alpha\beta\)，有
\[C(z) = \dfrac{1}{2\pi \mathrm i}\int_C A(s) B\left(\dfrac{z}{s}\right) \dfrac{\mathrm ds}{s} \]其中 \(C = \{s : \lvert s \rvert = (\alpha + \lvert z\rvert / \beta ) / 2\}\)。当然，这里的 \(C\) 也可以换成任意满足 \(A(s)\) 在内部解析、\(B(z/s)\) 在外部解析、包含原点的周线。
注意到 Laurent 级数
\[A(s) B\left(\dfrac{z}{s}\right) \dfrac{1}{s} = \sum_{k=-\infty}^{\infty} \sum_n a_{n + k + 1} b_n z^n s^k \]在圆环 \(D = \{s : \lvert z \rvert / \beta < \lvert s \rvert < \alpha\}\) （由于 \(\lvert z \rvert < \alpha\beta\)，\(\lvert z \rvert /\beta < \alpha\beta/\beta = \alpha\)，故 \(D\) 非空）上一致绝对收敛，故级数在 \(D\) 上表示对应函数。这是由于 \(A(s)\) 的 Laurent 级数在 \(\{s : \lvert s \rvert < \alpha \}\) 上收敛，且 \(B\left(\dfrac{z}{s}\right) \dfrac{1}{s}\) 的 Laurent 级数对所有满足 \(\left \lvert \dfrac{z}{s} \right\rvert < \beta\) 的 \(s\) 都收敛，即在圆盘 \(\{s : \lvert s \rvert < \lvert z \rvert / \beta \}\) 外收敛，故二者的乘积也收敛，重排即可得到上方式子。
若 \(B(z/s)\) 只有孤立奇点，那么它们都在 \(\{s : \lvert s \rvert = \lvert z \rvert /\beta \}\) 内部，故在 \(C\) 内部。只要 \(A(s)\) 的奇点和 \(B\left(\dfrac{z}{s}\right) \dfrac{1}{s}\) 的奇点在不同的区域内，那么无论路径 \(C\) 如何变形，积分的值都不会变化。这一点很重要，因为上面的积分有时可以通过求 \(A(s) B\left(\dfrac{z}{s}\right) \dfrac{1}{s}\) 在 \(B\left(\dfrac{z}{s}\right) \dfrac{1}{s}\) 被 \(C\) 包含在内的奇点处的留数之和来计算。
对 Laurent 级数两侧同时对 \(s\) 沿 \(C\) 积分，\(\text{RHS}\) 在 \(C\) 内部只有 \(s = 0\) 一个奇点，那么据留数定理，得到的 \(s^{-1}\) 项系数就是对所有 \(\lvert z \rvert < \alpha\beta\) 的 \(z\) 都适用的 \(C(z)\) 的 Taylor 级数表示。\(\square\)
\(\textbf{定理 1}\)
令
\[F(x, y) = \sum_{m=0}^{\infty} \sum_{n=0}^{\infty} f_{m,n} x^m y^n \]对所有满足 \(\lvert x \rvert < \alpha, \lvert y \rvert < \beta\) 的 \(x, y\) 收敛，那么对所有满足 \(\lvert z \rvert < \alpha\beta\) 的 \(z\)，有
\[G(z) = \sum_{n = 0}^{\infty} f_{n, n} z^n = \dfrac{1}{2\pi \mathrm i} \int_C F\left(s, \dfrac zs\right) \dfrac{\mathrm ds}{s} \]其中 \(C := \{s : \lvert s \rvert = (\alpha + \lvert z\rvert / \beta ) / 2\}\)。进一步的，若 \(F\left(s, \dfrac zs\right) \dfrac{1}{s}\) 在 \(C\) 内部只有孤立奇点，那么上述积分可以通过求这些奇点处的留数之和来计算。
证明：\(F(x, y)\) 的级数形式对所有满足 \(\lvert x \rvert < \alpha, \lvert y \rvert < \beta\) 的 \(x, y\) 一致绝对收敛，那么 \(G(z)\) 的级数形式对所有满足 \(\lvert z \rvert < \alpha\beta\) 的 \(z\) 一致绝对收敛。不妨取 \(z\) 满足 \(\lvert z \rvert < \alpha\beta\)，那么
\[s^{-1} \sum_{m = 0}^{\infty} \sum_{n = 0}^{\infty} f_{m,n} s^m \left(\dfrac zs \right)^n \]对所有 \(\lvert s \rvert < \alpha, \lvert z/s\rvert < \beta\) 都显然一致绝对收敛，这样的 \(s\) 形成了非空圆环 \(D = \{s : \lvert z \rvert / \beta < \lvert s \rvert < \alpha\}\)。那么可以重排上面的各项得到
\[\sum_{k = -\infty}^{\infty} \sum_n f_{n+k+1,n} z^n s^k \]该级数对所有 \(D\) 中的 \(s\) 都一致绝对收敛，值与 \(F\left(s, \dfrac zs\right) \dfrac{1}{s}\) 相同。那么两侧对 \(s\) 沿 \(C\) 积分即可得到 \(G(z)\) 满足的所有性质。\(\square\)
既然有了一个方法，我们就要用一下子。论文中给出了一个 general case：\(F(x,y) = (1 - ax - by - cxy)^{-1}\)，但我们不分析那么难的情况，而是看一个经典问题。（原题是愿望幽灵）
快进到生成函数阶段。要求一行 \(a_n = [z^n](1 + 2cz)^n(1 - z)^{-n-1}\)，不妨建立二元生成函数
\[F(z, t) = \sum_{n\ge 0} (1 + 2cz)^n(1 - z)^{-n-1}t^n = \dfrac{1}{1 - z - t - 2czt} \]那么 \(a_n = [z^nt^n] F\)，即 \(F\) 的对角线。根据上面的定理，有
\[G(z) = \dfrac{1}{2\pi \mathrm i} \int_C \dfrac{1}{1-s-z/s-2cz} \dfrac{\mathrm ds}{s} = \dfrac{1}{2\pi \mathrm i} \int_C \dfrac{-\mathrm ds}{z + (2cz-1)s+s^2} \]显然这个复变函数的两个瑕点是 \(p(s) = z + (2cz-1)s+s^2\) 的两个根
\[\left\{\begin{aligned} \alpha(z) = \dfrac{1-2cz + \sqrt{(2cz - 1)^2 - 4z}}{2}\\ \beta(z) = \dfrac{1-2cz - \sqrt{(2cz - 1)^2 - 4z}}{2} \end{aligned}\right. \]但是这两个根都在 \(C\) 的内部吗？这可不一定。显然 \(z\to 0\) 时 \(\alpha(z) \to 1, \beta(z) \to 0\)，那么由于 \(F(0, 0) \neq 0\)，取一定的 \(A > 0, B > 0\) 去卡圆盘，\(\beta(z)\) 一定在 \(C\) 内部，但 \(\alpha(z)\) 不在。故据留数定理，\(G(z) = \mathrm{Res}(-1/p(s), \beta(z))\)。由于 \(p(s) = [s - \alpha(z)][s -\beta(z)]\)，这个提取其实很简单。作换元 \(x = s - \beta(z)\)，
\[G(z) = [x^{-1}] \dfrac{-1}{x(x + \beta(z) - \alpha(z))} = [x^0] \dfrac{-1}{x + \beta(z) - \alpha(z)} = \dfrac{1}{\alpha(z) - \beta(z)} = \dfrac{1}{\sqrt{(1 - 2cz)^2 - 4z}} \]和 Alpha1022 得到的结果相同。
此外，论文得到了 \(F(x,y) = (1 - ax - by - cxy)^{-1}\) 的对角线的生成函数是
\[G(z) = \dfrac{1}{\sqrt{1 - 2(c + 2ab)z + c^2 z^2}} \]导出方法完全相同。
标签：25.1,rvert,23,闲话,lvert,beta,dfrac,alpha,mathrm From： https://www.cnblogs.com/joke3579/p/-/chitchat250123