求解涉及整数有序分拆乘积的递归公式

嘿，这个递归看起来有点绕，但其实用生成函数是完全可行的——你之前可能没找对生成函数的处理方式，我来一步步拆给你看：

首先，先定义普通生成函数 $G(x) = \sum_{n\geq1} S_n x^n$，已知 $S_1=1$，所以 $G(x) = x + S_2x^2 + S_3x^3 + \dots$

第一步：把递归式里的内层和转化为生成函数的幂 #

你递归式里的内层求和 $\sum_{j_1+\dots+j_r=N} S_{j_1}\dots S_{j_r}$，其实就是 $G(x)^r$ 中 $x^N$ 的系数！因为有序分拆（composition）的乘积和，正好对应普通生成函数的r次卷积系数——每一项 $S_{j_1}x^{j_1}\dots S_{j_r}x^{j_r}$ 相乘后x的指数是 $j_1+\dots+j_r=N$，加起来就是 $G(x)^r$ 里 $x^N$ 的系数，我们记为 $[x^N]G(x)r$。

那原递归式可以改写为：
$$S_{N+1} = \frac{1}{N+1} \sum_{r=1}^N 2^{-r} [x^N]G(x)r$$

第二步：把递归式转化为生成函数的方程 #

我们把两边都乘以 $x^N$，然后对 $N\geq1$ 求和：

• 左边：$\sum_{N\geq1} S_{N+1}x^N = \frac{G(x) - S_1x}{x} = \frac{G(x)-x}{x} = \frac{G(x)}{x} - 1$
• 右边：我们交换求和顺序，把r的求和提到外面，得到 $\sum_{r\geq1}2^{-r} \sum_{N\geqr} \frac{1}{N+1}x^N [x^N]G(x)r$

这里注意当 $N<r$ 时，$[x^N]G(x)r=0$，所以N从r开始。接下来用一个小技巧：$\frac{x^N}{N+1} = \frac{1}{x}\int_0^x t^N dt$，所以里面的求和可以写成 $\frac{1}{x}\int_0^x \sum_{N\geqr}[x^N]G(x)r t^N dt$。而 $\sum_{N\geqr}[x^N]G(x)r t^N$ 就是 $G(t)^r$（因为G(t)最低次是 $t^1$，所以 $G(t)^r$ 最低次是 $t^r$，前面的项都是0）。

所以右边就变成 $\frac{1}{x}\int_0^x \sum_{r\geq1}\left(\frac{G(t)}{2}\right)^r dt$，而等比级数 $\sum_{r\geq1}z^r = \frac{z}{1-z}$（当 $|z|<1$ 时成立），这里 $z=\frac{G(t)}{2}$，代入后得到：
$$\frac{1}{x}\int_0^x \frac{\frac{G(t)}{2}}{1 - \frac{G(t)}{2}} dt = \frac{1}{x}\int_0^x \frac{G(t)}{2 - G(t)} dt$$

现在我们得到了生成函数的积分方程：
$$\frac{G(x)}{x} - 1 = \frac{1}{x}\int_0^x \frac{G(t)}{2 - G(t)} dt$$

两边乘x消去分母：
$$G(x) - x = \int_0^x \frac{G(t)}{2 - G(t)} dt$$

第三步：转化为微分方程求解 #

对两边关于x求导，左边导数是 $G'(x)-1$，右边导数就是被积函数在t=x处的值 $\frac{G(x)}{2-G(x)}$，所以得到：
$$G'(x) - 1 = \frac{G(x)}{2 - G(x)}$$

整理一下：
$$G'(x) = 1 + \frac{G(x)}{2 - G(x)} = \frac{2 - G(x) + G(x)}{2 - G(x)} = \frac{2}{2 - G(x)}$$

这是个可分离变量的微分方程，分离变量得：
$$(2 - G)dG = 2dx$$

两边积分，初始条件是x=0时 $G(0)=0$（因为G(x)从 $x^1$ 开始）：
$$\int_0^{G(x)}(2 - g)dg = \int_0^x 2dt$$

计算左边积分：$2G(x) - \frac{1}{2}G(x)^2$，右边是 $2x$，所以：
$$2G(x) - \frac{1}{2}G(x)^2 = 2x$$

两边乘2消去分数：
$$4G(x) - G(x)^2 = 4x$$

这是关于G(x)的二次方程，解出来：
$$G(x) = \frac{4 \pm \sqrt{16 - 16x}}{2} = 2(1 \pm \sqrt{1-x})$$

现在验证哪个解符合初始条件：当x→0时，G(x)≈x。取减号的话，$2(1-\sqrt{1-x})=2\left[1-\left(1 - \frac{x}{2} - \frac{x^2}{8} - \dots\right)\right] = x + \frac{x^2}{4} + \dots$，正好符合 $S_1=1$；取加号的话会得到 $4 -x -...$，显然不对，所以我们取减号的解：
$$G(x) = 2(1 - \sqrt{1 - x})$$

第四步：展开生成函数得到S_N的表达式和Scaling行为 #

现在把G(x)展开成幂级数，用二项式展开 $\sqrt{1-x}$：
$$\sqrt{1-x} = \sum_{n\geq0} \binom{1/2}{n}(-x)^n$$
所以 $1 - \sqrt{1-x} = \sum_{n\geq1} (-1)^{{n+1}\binom{1/2}{n}(-x)}n = \sum_{n\geq1} \frac{(2n-2)!}{2^{{2n-1}n!(n-1)!}x}n$

乘以2后得到G(x)的展开式：
$$G(x) = \sum_{n\geq1} \frac{(2n-2)!}{2^{{2n-2}n!(n-1)!}x}n = \sum_{n\geq1} \frac{\binom{2n-2}{n-1}}{n4^{n-1}}xn$$

所以 $S_n$ 就是 $x^n$ 的系数：
$$S_n = \frac{\binom{2n-2}{n-1}}{n4^{n-1}}$$

这里 $\binom{2n-2}{n-1}$ 是中心二项式系数，这个式子也可以用卡特兰数表示：因为第k个卡特兰数 $C_k = \frac{\binom{2k}{k}}{k+1}$，所以 $C_{n-1}=\frac{\binom{2n-2}{n-1}}{n}$，因此 $S_n = \frac{C_{n-1}}{4^{n-1}}$

最后看Scaling行为，当n很大时，用斯特林公式近似卡特兰数：$C_k \sim \frac{4^k}{k{3/2}\sqrt{\pi}}$，代入k=n-1，得到 $C_{n-1}\sim\frac{4^{n-1}}{(n-1){3/2}\sqrt{\pi}}\approx\frac{4^{n-1}}{n{3/2}\sqrt{\pi}}$，所以：
$$S_n \approx \frac{\frac{4^{n-1}}{n{3/2}\sqrt{\pi}}}{4^{n-1}} = \frac{1}{n^{3/2}\sqrt{\pi}}$$
也就是 $S_N \sim O(N^{-3/2})$，这就是你要的Scaling规律！

备注：内容来源于stack exchange，提问作者EmFed