广义二项/指数级数

一年了 我终于也能看懂了... 该部分的内容可能baidu难以找到，待查一下wiki. ----- 具体数学在前面用的是 `\mathcal{B}` 在后面用的是 `\mathfrak{B}` ，比较迷惑. 由于我个人比较喜欢前面的所以以下统一使用前面的. 定义广义二项级数如下: $$ \mathcal{B}_t(z)=\sum_{n\geq 0}\binom{tn+1}{n}\frac{z^n}{tn+1} $$ 或者等价地写成 $$ \mathcal{B}_t(z)=\sum_{n\geq 0}(tn)^{\underline{n-1}}\frac{z^n}{n!} $$ 先给出一些结论: $$ \mathcal{B}_t(z)=z\mathcal{B}_t(z)^t+1\tag{1} $$ 或者等价地写成 $$ \mathcal{B}_t(z)^{1-t}-\mathcal{B}_t(z)^{-t}=z $$ 接下来是两个恒等式: $$ \mathcal{B}_t(z)^r=\sum_{n\geq 0}\binom{tn+r}{n}\frac{r}{tn+r}z^n\tag{2} $$ 以及 $$ \frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}}=\sum_{n\geq 0}\binom{tn+r}{n}z^n\tag{3} $$ 那么首先我们使用具体数学上没有介绍的~~牛逼~~拉格朗日反演来完成证明，这个证明相对来说是比较机械的. 对于 $(1)$ ，令 $F(z)=\mathcal{B}_t(z)-1$，那么就有 $$ F(z)=z(1+F(z))^t $$ 令 $G(z)=\dfrac{z}{(1+z)^t}$，那么根据拉格朗日反演我们得到 $$ [z^n]F(z)=\frac{1}{n}[z^{n-1}]\left(\frac{z}{G(z)}\right)^n=\frac{1}{n}\binom{nt}{n-1} $$ 当 $n>0$ 时我们有 $$ \frac{1}{n}\binom{nt}{n-1}=\frac{1}{1+nt}\binom{1+nt}{n} $$ 当 $n=0$ 时显然成立，于是我们得到 $$ \mathcal{B}_t(z)=\sum_{n\geq 0}\binom{1+nt}{n}\frac{1}{1+nt}z^n $$ 这样就证明了 $(1)$ . 接下来考虑 $(2)$，令 $H(z)=(1+z)^r$，根据扩展拉格朗日反演我们有 $$ [z^n]\mathcal{B}_t(z)^r=[z^n]H(F(z))=\frac{1}{n}[z^{n-1}]H'(z)\left(\frac{z}{G(z)}\right)^n=\frac{r}{n}\binom{nt+r-1}{n-1} $$ 当 $n>0$ 时有 $\dfrac{r}{n}\dbinom{nt+r-1}{n-1}=\dfrac{r}{nt+r}\dbinom{nt+r}{n}$，当 $n=0$ 时依然显然成立，于是我们得到 $$ \mathcal{B}_t(z)^r=\sum_{n\geq 0}\binom{nt+r}{n}\frac{r}{nt+r}z^n $$ 这就证明了 $(2)$. 接下来考虑 $(3)$，依然是扩展拉格朗日反演，但是这次麻烦了不少，令 $H(z)=\dfrac{(1+z)^r}{1-t+t(1+z)^{-1}}$ $$ \begin{aligned}[z^n]\frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}}&=[z^n]H(G(z))\\&=\frac{1}{n}[z^{n-1}]H'(z)\left(\frac{z}{G(z)}\right)^n\\&=\frac{1}{n}[z^{n-1}](1+z)^{nt}\frac{r(1+z)^{r-1}(1-t+t(1+z)^{-1})+(1+z)^rt(1+z)^{-2}}{(1-t+t(1+z)^{-1})^2}\\&=\frac{1}{n}[z^{n-1}](1+z)^{nt+r}\left(\frac{r}{1-(t-1)z}+\frac{t}{(1-(t-1)z)^2}\right)\\&=\frac{1}{n}\sum_{i=0}^{n-1}\binom{nt+r}{i}\left(r(t-1)^{n-1-i}+t(n-i)(t-1)^{n-1-i}\right)\\&=\frac{1}{n}\left((nt+r)\sum_{i=0}^{n-1}\binom{nt+r}{i}(t-1)^{n-1-i}-t\sum_{i=0}^{n-1}\binom{nt+r}{i}i(t-1)^{n-1-i}\right)\\&=\frac{1}{n}(nt+r)\left(\sum_{i=0}^{n-1}\binom{nt+r}{i}(t-1)^{n-1-i}-t\sum_{i=0}^{n-1}\binom{nt+r-1}{i-1}(t-1)^{n-1-i}\right)\end{aligned} $$ 后面这两个 $\sum$ 不是很好处理，但是经过一番暴力计算发现其有一个简单的递推形式. 设 $$ a_d=\sum_{i=0}^d\binom{nt+r}{i}(t-1)^{d-i}-t\sum_{i=0}^d\binom{nt+r-1}{i-1}(t-1)^{d-i} $$ 那么我们需要求出 $a_{n-1}$. 有 $$ \begin{aligned}a_d&=\sum_{i=0}^d\binom{nt+r}{i}(t-1)^{d-i}-t\sum_{i=0}^d\binom{nt+r-1}{i-1}(t-1)^{d-i}\\&=\sum_{i=0}^d\binom{nt+r}{i}(t-1)^{d-i}-t\sum_{i=0}^{d-1}\binom{nt+r-1}{i}(t-1)^{d-1-i}\\&=\binom{nt+r}{d}+\sum_{i=0}^{d-1}(t-1)^{d-1-i}\left((t-1)\binom{nt+r}{i}-t\binom{nt+r-1}{i}\right)\\&=\binom{nt+r}{d}+\sum_{i=0}^{d-1}(t-1)^{d-1-i}\left(t\binom{nt+r-1}{i-1}-\binom{nt+r}{i}\right)\\&=\binom{nt+r}{d}-\left(\sum_{i=0}^{d-1}\binom{nt+r}{i}(t-1)^{d-1-i}-t\sum_{i=0}^{d-1}\binom{nt+r-1}{i-1}(t-1)^{d-1-i}\right)\\&=\binom{nt+r}{d}-a_{d-1}\end{aligned} $$ 显然 $a_0=1$，这就给出 $$ a_{n-1}=\sum_{i=0}^{n-1}(-1)^{n-i}\binom{nt+r}{i}=\binom{nt+r-1}{n-1} $$ 代回去稍作整理就得到 $$ [z^n]\frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}}=\binom{nt+r}{n} $$ 这样就完成了 $(3)$ 的证明. 不过通过参考 [EI's blog](https://www.luogu.com.cn/blog/EntropyIncreaser/ying-ye-ri-zhi-202059-post) 得到了一个更简单的做法，在上面的推导中不进行最后一个等号的转化，而是重新转化为形式幂级数: $$ \begin{aligned}&\frac{1}{n}\left((nt+r)\sum_{i=0}^{n-1}\binom{nt+r}{i}(t-1)^{n-1-i}-t\sum_{i=0}^{n-1}\binom{nt+r}{i}i(t-1)^{n-1-i}\right)\\=&\frac{1}{n}[z^{n-1}]\left((nt+r)\frac{(1+z)^{nt+r}}{1-(t-1)z}-tz\frac{((1+z)^{nt+r})'}{1-(t-1)z}\right)\\=&\frac{1}{n}[z^{n-1}]\frac{(nt+r)(1+z)^{nt+r-1}(1+z-tz)}{1-(t-1)z}\\=&\frac{1}{n}[z^{n-1}](nt+r)(1+z)^{nt+r-1}\\=&\frac{nt+r}{n}\binom{nt+r-1}{n-1}\end{aligned} $$ 得到了同样的结果. ------ 接下来我们介绍具体数学上使用的牛逼组合意义法. 首先我们来考虑卡特兰数 $C_n=\dbinom{2n+1}{n}\dfrac{1}{2n+1}$，它的其中一个组合意义是有 $n$ 个 $1$ 和 $n$ 个 $-1$ 的所有序列中满足任意部分和都非负的序列数量. 那个经典的映射法这里就不说了，我们来考虑一个引理: > Raney引理:如果 $\langle x_1,x_2,\cdots ,x_m\rangle$ 是任何一个和为 $+1$ 的整数数列，那么它的循环移位 > > $\langle x_1,x_2,\cdots x_m\rangle\ ,\ \langle x_2,\cdots x_m,x_1\rangle\ ,\ \cdots,\ \langle x_m,x_1,\cdots ,x_{m-1}\rangle$ > > 中恰好有一个满足所有的部分和都是正数. 证明可以baidu，我们来考虑怎么用它，稍微变换一下上面的组合意义，变成有多少个由 $+1$ 和 $-1$ 组成的数列 $\langle a_0,a_1,a_2,\cdots ,a_{2n}\rangle$ 满足 $a_0+a_1+a_2+\cdots +a_{2n}=1$ 且所有的部分和 $a_0,a_0+a_1,a_0+a_1+a_2,\cdots,a_0+a_1+\cdots +a_{2n}$ 都是正数. 那么可以使用 Raney 引理简单计算，一共有 $\dbinom{2n+1}{n}$ 个数列满足第一个条件，这些数列中恰好有 $\dfrac{1}{2n+1}$ 个满足第二个条件，于是答案就是 $\dbinom{2n+1}{n}\dfrac{1}{2n+1}$ 注意卡特兰数是满足 $C(z)=zC(z)^2+1$ 的，那么我们来尝试用 $m$ 替换掉这个 $2$ 会发生什么. 一个猜测是这样会产生一个形如 $C_n^{(m)}=\dbinom{mn+1}{n}\dfrac{1}{mn+1}$ 的数列，这是正确的，接下来我们证明这件事. 考虑由 $+1$ 和 $(1-m)$ 组成的其部分和全为正且总和为 $1$ 的数列 $\langle a_0,\cdots a_{mn}\rangle$，这样的数列可以称为 ***m*-Raney 数列** . 如果 $(1-m)$ 出现 $k$ 次那么 $+1$ 出现 $mn+1-k$ 次，应当有 $(1-m)k+mn+1-k=1$，于是 $k=n$. 那么由 Raney 引理容易得到这样的数列的个数为 $$ C^{(m)}_n=\binom{mn+1}{n}\frac{1}{mn+1} $$ 其中数列 $\langle C_n^{(m)}\rangle$ 称为富斯-卡特兰(Fuss-Catalan)数. 一般的卡特兰数是 $C_n^{(2)}$. 接下来我们证明 $C_n^{(m)}$ 的生成函数 $G(z)$ 满足 $G(z)=zG(z)^m+1$. 当 $n=0$ 时显然有 $C_n^{(m)}=1$；否则，这个 ***m*-Raney** 数列的最后一个数一定是 $1-m$. 如果把 $(1-m)$ 放在 $m$ 个 ***m*-Raney** 数列的右边，那么我们就得到了一个新的 ***m*-Raney** 数列. 反过来，可以证明所有的 $n>0$ 的 ***m*-Raney** 数列都可以这样分解：设部分和 $s_j=a_0+a_1+\cdots +a_{j-1}$ ，令 $k_1$ 是最大的 $\leq mn$ 且满足 $s_j=1$ 的 $j$，$k_2$ 是最大的满足 $s_j=2$，以此类推. 那么容易看出 $k_m=mn$，且对于 $1\leq j\leq m,k_j<k\leq mn$ 有 $s_{k_j}=j$ 且 $s_k>j$，因为部分和增加的时候是连续变化的. 于是子数列 $\langle a_0,\cdots,a_{k_1-1}\rangle\ ,\ \langle a_{k_1},\cdots ,a_{k_2-1}\rangle\ ,\cdots,\ \langle a_{k_{m-1}},\cdots,a_{k_m-1}\rangle$ 都是 ***m*-Raney** 数列，于是对某些非负的 $n_1,n_2,\cdots,n_m$，必定有 $k_1=mn_1+1,k_2-k_1=mn_2+1,\cdots,k_m-k_{m-1}=mn_m+1$,于是有 $$ C_n^{(m)}=[n=0]+\sum_{n_1+n_2+\cdots +n_m=n-1}C_{n_1}^{(m)}C_{n_2}^{(m)}\cdots C_{n_m}^{(m)} $$ 这就是说其生成函数 $G(z)$ 满足 $G(z)=zG(z)^m+1$. 由于系数是 $m$ 的多项式所以根据多项式推理法我们可以推广到 $m$ 不是正整数的情况. 这样我们完成了 $(1)$ 的证明. 接下来考虑 $(2)$，刚刚的论证可以用来证明 $[z^n]G(z)^l$ 是长度为 $mn+l(l>0)$ 且满足下列三个性质的数列的个数: - 每个元素要么是 $+1$，要么是 $(1-m)$； - 部分和全部为正数； - 和为 $l$. 即把 $l$ 个 ***m*-Raney** 数列放到一起，这样我们能以唯一地方式得到所有这样的数列. 这样的方案数就是 $$ \sum_{n_1+n_2+\cdots +n_l=n}C_{n_1}^{(m)}C_{n_2}^{(m)}\cdots C_{n_l}^{(m)}=[z^n]G(z)^l $$ 考虑如何对这样的数列计数，Raney 证明了他的引理的一个推广: > 如果 $\langle x_1,x_2,\cdots ,x_m\rangle$ 是对所有 $j$ 都满足 $x_j\leq 1$ 的一个整数数列，且 $x_1+x_2+\cdots +x_m=l>0$，那么其循环移位中恰有 $l$ 个满足所有部分和都为正. 证明是具体数学的练习，~~我也不会~~就不证了 现在可以对这样的数列计数了，不考虑部分和的限制，所有这样的数列中 $(1-m)$ 都一定恰好出现了 $n$ 次，推广的引理告诉我们恰好有 $\dbinom{mn+l}{n}\dfrac{l}{mn+l}$ 个数列满足所有部分和都为正，于是我们得到 $$ [z^n]G(z)^l=\binom{mn+l}{n}\frac{l}{mn+l} $$ 由于系数是 $m$ 和 $l$ 的多项式我们可以推广到 $m,l$ 不是正整数的情况. 这样就完成了 $(2)$ 的证明. $(3)$ 的证明在具体数学上是用 $(2)$ 得到的，作为练习题. 先咕咕咕. ~~从外观上就能看出组合意义和代数的区别~~ ----- 定义**广义指数级数**: $$ \mathcal{E}_t(z)=\sum_{n\geq 0}(tn+1)^{n-1}\frac{z^n}{n!} $$ 同样满足三个性质: $$ \mathcal{E}_t(z)^{-t}\ln \mathcal{E}_t(z)=z\tag{1} $$ $$ \mathcal{E}_t(z)^r=\sum_{n\geq 0}r(tn+r)^{n-1}\frac{z^n}{n!}\tag{2} $$ $$ \frac{\mathcal{E}_t(z)^r}{1-zt\mathcal{E}_t(z)^{t}}=\sum_{n\geq 0}(tn+r)^n\frac{z^n}{n!}\tag{3} $$ 还是先使用~~牛逼~~拉格朗日反演证明. 对于 $(1)$，令 $F(z)=\ln \mathcal{E}_t(z)$，那么可以化为 $$ \frac{F(z)}{e^{tF(z)}}=z $$ 那么我们需要求出 $\mathcal{E}_t(z)=e^{F(z)}$，使用拉格朗日反演容易得到 $$ [z^n]e^{F(z)}=\frac{1}{n}[z^{n-1}]e^z(e^{tz})^n=\frac{(tn+1)^{n-1}}{n!} $$ 接下来考虑 $(2)$，那么不过就是 $e^{rF(z)}$，容易得到 $$ [z^n]e^{rF(z)}=\frac{1}{n}[z^{n-1}]re^{rz}(e^{tz})^n=r\frac{(tn+1)^{n-1}}{n!} $$ 至于 $(3)$，由 $(1)$ 我们有 $z\mathcal{E}_t(z)^t=F(z)$，所以所求即 $$ \begin{aligned} [z^n]\frac{e^{rF(z)}}{1-tF(z)}&=\frac{1}{n}[z^{n-1}]\left(\frac{e^{rz}}{1-tz}\right)'(e^{tz})^n\\&=\frac{1}{n}[z^{n-1}]e^{(nt+r)z}\left(\frac{r}{1-tz}+\frac{t}{(1-tz)^2}\right)\\&=\frac{1}{n}\left(\sum_{i=0}^{n-1}\frac{(nt+r)^i}{i!}rt^{n-1-i}+\sum_{i=0}^{n-1}\frac{(nt+r)^i}{i!}(n-i)t^{n-1-i}\right)\\&=\frac{1}{n}\sum_{i=0}^{n-1}\frac{(nt+r)^i}{i!}t^{n-1-i}((nt+r)-(it))\\&=\frac{1}{n}[z^{n-1}]\left((nt+r)e^{(nt+r)z}\frac{1}{1-tz}-tz(e^{(nt+r)z})'\frac{1}{1-tz}\right)\\&=\frac{1}{n}[z^{n-1}]\frac{e^{(nt+r)z}(nt+r)(1-tz)}{1-tz}\\&=\frac{(nt+r)^n}{n!} \end{aligned} $$ 中间有似曾相识的一步，为了简便起见就直接采用 EI 的做法. 具体数学的说法是可以把 $(2)$ 作为广义二项级数的极限情况证明，因为 $$ \mathcal{E}_t(z)^r=\lim_{x\to \infty}\mathcal{B}_{xt}(z/x)^{xr} $$ 可以简单证明如下: > Lemma. $\lim\limits_{x\to \infty}\dbinom{xn}{k}x^{-k}=\dfrac{n^k}{k!}$ > > Proof. $\lim\limits_{x\to \infty}\dbinom{xn}{k}x^{-k}=\lim\limits_{x\to \infty}\dfrac{n(n-1/x)(n-2/x)\cdots (n-(n-k+1)/x)}{k!}=\dfrac{n^k}{k!}$ $$ \begin{aligned} &\lim_{x\to \infty}\mathcal{B_{xt}(z/x)^{x}}\\ =&\lim_{x\to \infty}\sum_{n\geq 0}\binom{nxt+x}{n}\frac{z^nx}{x^n(nxt+x)}\\ =&\sum_{n\geq 0}\lim_{x\to \infty}\binom{x(nt+1)}{n}\frac{z^n}{x^n(nt+1)}\\ =&\sum_{n\geq 0}(nt+1)^{n-1}\frac{z^n}{n!}\\ =&\mathcal{E}_t(z) \end{aligned} $$ 那么两边取 $r$ 次幂即可完成证明. 和广义二项级数相同地，$(3)$ 可以由 $(2)$ 推得，待补. --- 说了这么多有什么用呢？反正看着就牛逼对吧. 实际上这样子的组合恒等式在应用中出现得也不少. 先来一个简单的数学练习，在知乎搜索“广义二项级数”即可找到. 求 $$ \sum_{i\geq 0}\frac{1}{2^{n+2i}(n+2i)}\binom{n+2i}{i} $$ 那么直接上就完事了对吧: $$ \begin{aligned}&\sum_{i\geq 0}\frac{1}{2^{n+2i}(n+2i)}\binom{n+2i}{i}\\=&\frac{1}{2^nn}\sum_{i\geq 0}\binom{2i+n}{i}\frac{1}{2i+n}\left(\frac{1}{4}\right)^i\\=&\frac{1}{2^nn}\mathcal{B}_2(\frac{1}{4})^n\end{aligned} $$ 咦，我们好像还不知道 $\mathcal{B}_2(z)$ 是多少. 没关系，我们有方程 $$ \mathcal{B}_2(z)=z\mathcal{B}_2(z)^2+1 $$ 直接解会有两个根，由于 $[z^0]\mathcal{B}_2(z)=1$ 所以得到 $$ \mathcal{B}_2(z)=\frac{1-\sqrt{1-4z}}{2z} $$ 代回去就得到简单的答案 $\dfrac{1}{n}$. 然后是 EI 粉丝群里看见的一道题: $$ b_i=\sum_{j\geq 0}a_j\binom{2i-j}{i-j} $$ 给出 $a$，要快速计算 $b$. 那整出OGF来: $$ \begin{aligned}B(z)&=\sum_{i\geq 0}b_iz^i\\&=\sum_{i\geq 0}z^i\sum_{j\geq 0}a_j\binom{2i-j}{i-j}\\&=\sum_{j\geq 0}a_j\sum_{i\geq 0}z^i\binom{2i-j}{i-j}\\&=\sum_{j\geq 0}a_jz^j\sum_{i\geq 0}z^i\binom{2i+j}{i}\\&=\frac{1}{2\mathcal{B}_2(z)^{-1}-1}\sum_{j\geq 0}a_j(z\mathcal{B}_2(z))^j\end{aligned} $$ 有 $z\mathcal{B}_2(z)=\dfrac{1-\sqrt{1-4z}}{2}$，令 $u=\sqrt{1-4z}$，那么我们先计算出 $$ \sum_{j\geq 0}a_j\frac{(1-u)^j}{2^j} $$ 这个是容易卷积得到的. 设卷出来的答案为 $$ \sum_{j\geq 0}c_ju^j $$ 那么只需要按 $j$ 分奇偶把根号去掉，然后就是个和上述形式差不多的卷积了. 可以 $O(n\log n)$ 计算. 其他应用待补. ------ 最后的最后，欢迎加入 EI 队长粉丝裙(450567214)，EntropyIncreaser/Elegia tsdy!