一年了 我终于也能看懂了...
该部分的内容可能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 得到了一个更简单的做法，在上面的推导中不进行最后一个等号的转化，而是重新转化为形式幂级数:
\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) 的证明.
~~从外观上就能看出组合意义和代数的区别~~
-----
定义**广义指数级数**:
$$
\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!