第五章
5.1 组合数基础
P140 5.24
求证：
\[\sum_k \binom l {m+k}\binom {s+k}n(-1)^k=(-1)^{l+m}\binom {s-m}{n-l} \]H_W_Y 老师有点太强了，归纳法纯 shaber，考虑直接推式子：
\[LHS=\sum_{k}\binom {m+k-l-1}{m+k}\binom {n-s-k-1}{n}(-1)^{m+n}\\ =(-1)^{m+n}\sum_k \binom {m-l-1+k}{-l-1}\binom {n-s-1-k}{n}\\ =(-1)^{m+n}\binom{m+n-s-l-1}{n-l}\\ RHS=(-1)^{n+m}\binom {n-l-s+m-1}{n-l}=LHS \]5.2 基本练习
P143 Q1
求
\[S=\sum_{k=0}^m \binom m k/\binom n k,n\ge m\ge 0 \]我们考虑
\[\binom n m\binom m k=\binom n k\binom{n-k}{m-k}\\ \binom m k=\binom n k\binom{n-k}{m-k}/\binom n m\\ \]则：
\[S=\sum_{k=0}^m \binom {n-k}{m-k}/\binom n m\\ =\frac 1 {\binom nm}\sum_{k=0}^m\binom {n-m+k}k\\ =\frac 1 {\binom n m} \binom {n+1}m\\ =\frac {n+1}{n-m+1} \]P145 Q2
化简
\[S=\sum_{k=0}^nk\binom {m-k-1}{m-n-1}\\ \]法一：
\[S=\sum_{k=0}^n(m-(m-k))\binom {m-k-1}{m-n-1}\\ =m\sum_{k=0}^n\binom{m-n-1+k}{m-n-1}-\sum_{k=0}(m-k)\binom {m-k-1}{m-n-1} \]因为
\[\frac n m\binom {n-1}{m-1}=\binom n m\\ n\binom {n-1}{m-1}=m\binom n m \]所以
\[S=m\binom {m}{m-n}-(m-n)\sum_{k=0}^n\binom {m-k}{m-n}\\ =m\binom m {m-n}-(m-n)\binom {m+1}{m-n+1}\\ =m\binom m {m-n}-(m-n)\frac {m+1}{m-n+1}\binom {m}{m-n}\\ =\frac {n}{m-n+1}\binom m {m-n}=\binom m{n-1} \]法二：
\[S=\sum_{k=0}^n\binom k 1\binom {m-k-1}{m-n-1}\\ =\binom{m}{m-n+1}=\binom{m}{n-1} \]P150 Q5
\[S=\sum_k \binom n k\binom sk k \]\[S=\sum\binom n k\binom {s-1}{k-1}s\\ =s\sum\binom n k\binom {s-1}{s-k}\\ =s\binom {n+s-1}{s} \]P150 Q6
\[S=\sum_{k\ge 0}\binom {n+k} {2k}\binom {2k}k\frac {(-1)^k}{k+1} \]\[S=\sum_{k\ge 0}\binom {n}{k}\binom {n+k}k\frac{(-1)^k}{k+1} \]\[S=\sum\binom {n+1} {k+1}\binom{-n-1}k\frac {1}{n+1}\\ =\frac 1 {n+1}\binom 0 n \]P152 Q7
\[\sum_{k\ge 0}\binom {n+k} {m+2k}\binom {2k}k\frac {(-1)^k}{k+1} \]我们发现这跟上面一个的差距就是 \(2k\) 变成了 \(2k+m\)，我们考虑把这个二次项系数拆开。
我们知道
\[\sum_j\binom {j}{m-1}\binom {n+k-1-j}{2k}=\binom {n+k}{m+2k} \]\[S=\sum_{k}\sum_j\binom j {m-1}\binom {n+k-1-j}{2k}\binom {2k} k\frac {(-1)^k}{k+1}\\ =\sum_j\binom j {m-1}\sum_{k}\binom {n+k-1-j}{k}\binom {n-j-1}{k}\frac {(-1)^k}{k+1}\\ =\sum_j\binom j {m-1}\sum_{k}\binom {j-n}{k}\binom {n-j}{k+1}\frac {1}{n-j}\\ =\sum_j\binom j {m-1}\frac {1}{n-j}\sum_{k}\binom {j-n}{k}\binom {n-j}{n-j-k-1}\\ =\sum_j\binom j {m-1}\frac {1}{n-j}\binom 0 {n-j-1}\\=\sum_j\binom j {m-1}\frac {1}{n-j}[n-j-1=0]\\ =\binom {n-1}{m-1} \]P153 Q8
\[S=\sum_{k\ge 0}\binom {n+k} {2k}\binom {2k}k\frac {(-1)^k}{k+1+m} \]根据 Q1，我们知道：
\[\sum_{k=0}^m\binom m j/\binom n j=\frac {n+1}{n-m+1}=\frac {-n-1}{m-n-1} \]将 \(S\) 中的 \(-k-2\) 代替上面式子的 \(n\)，则
\[\frac {k+1}{k+1+m}=\sum_j \binom mj/\binom {-k-2}j \]所以
\[S=\frac 1 {n+1}\sum \binom {n+k}{k}\binom {n+1}{k+1} {(-1)^k}\sum \binom m j\binom {-k-2}j^{-1}\\ S=\sum_k\sum_j(-1)^k\frac {(n+k)!n!m!j!(-k-2-j)!}{n!k!(k+1)!(n-k)!j!(m-j)!(-k-2)!}\\ S=m!\sum_k\sum_j(-1)^k\frac {(n+k)!(-k-2-j)!}{k!(k+1)!(n-k)!(m-j)!(-k-2)!}\\ \]uob 先生告诉我们，当 \(a,b\in \Z\) 时，虽然负数不存在阶乘，但是可以这样理解：
然后看看具体数学的答案，可以得到：
\[S=\frac {m!n!}{(m+n+1)!}\sum_j(-1)^j\binom {n+1+m}{n+1+j}\sum_k\binom{n+1+j}{k+1+j}\binom{-n-1}{k}\\ \frac {m!n!}{(m+n+1)!}\sum_{j\ge 0}(-1)^j\binom {n+1+m}{n+1+j}\binom j n\\ \]由 5.24 知道，这个式子在 \(j\ge 0\) 时等于 \(0\)。
5.3 处理的技巧
1.取一半
\[r^{\underline k}(r-\frac 1 2)^{\underline k}=(2r)^{\underline{2k}}/2^{2k}\\ \binom rk \binom {r-\frac 12 }k=\binom {2r}{2k}\binom {2k}k/2^{2k}\\ \]令 \(r=k=n\)，得到：
\[\binom {n-\frac 12}{n}=\binom {2n}n/2^{2n},\binom {-\frac 12}{n}=(\frac {-1}4)^n\binom {2n}n\ \]2.高阶差分
\[\Delta^nf(x)=\sum_{k=0}^n\binom n k(-1)^{n-k}f(x+k)\\ \Delta^n=(E-1)^n=\sum_{k=0}^n\binom n k(-1)^{n-k}E^k \]设 \(deg\ f=d\)，则
\[\Delta^nf(0)= \begin{cases} c_n &\text{if } n\le d \\ 0 &\text{if } n>d \end{cases} \]所以
\[f(x)=\sum_{0\le i\le d} \Delta^if(0)\binom xi\\ \sum\binom n k (-1)^{n-k}f(k)=c_n\\ \sum_k\binom n k(-1)^{n-k}(\sum_jc_j\binom k j)=c_n\\ \sum_k\binom n k(-1)^{k}(\sum_ja_jk^j)=(-1)^nn!c_n\\ \sum_k\binom n k(-1)^{k}f(k)=(-1)^nn!c_n\\ \]我们考虑证明恒等式：
\[\sum_k\binom n k\binom {r-sk}{n}(-1)^k=s^n\\ 设 f(k)=\binom {r-sk}n\\ =\frac {1}{n!}{(r-sk)^{\underline n}}\\ =\frac 1 {n!}(-1)^ns^nk^n+\ldots\\ =(-1)^ns^n\binom k n+\ldots \]所以 \([z^n]f(z)=\frac {(-1)^ns^n}{n!}\)
所以带入上面的式子即可证明。
然后你令 \(f(x)=(x-1)^{\underline{-1}}=\frac {1}x\)，然后你能得到一些神秘的式子：
\[\Delta^nf(x)=\frac {(-1)^\underline n}{x^{\overline {n+1}}} \]然后根据
\[\Delta^nf(x)=\sum_k\binom n k(-1)^{n-k}f(x+k) \]得到：
\[\sum_k\binom n k\frac{(-1)^k}{x+k}=\frac {n!}{x(x+1)(x+2)\ldots (x+n)}=x^{-1}\binom {x+n}n^{-1} \]3.反演
似乎本节就介绍了一个二项式反演：
\[f(n)=\sum_k\binom n k(-1)^kg(k)\Leftrightarrow g(n)=\sum_k\binom n k(-1)^kf(k) \]然后我们可以证明一下这个式子：
\[f(i)=\sum_k\binom i k(-1)^k\sum_j\binom k j(-1)^jf(j)\\ =\sum_{j}(-1)^jf(j)\sum_k\binom i k \binom k j(-1)^k\\ =\sum_{j}\binom i j(-1)^jf(j)\sum_k \binom {i-j} {k-j}(-1)^k\\ =\sum_{j}\binom i j(-1)^jf(j)\sum_{k'} \binom {i-j} {k'}(-1)^{k'+j}\\ =\sum_{j}\binom i jf(j)\sum_{k'} \binom {k'-i+j-1} {j-i-1}\\ =\sum_{j}\binom i jf(j)\binom 0 {j-i}=\sum_j[i=j]f(j)=f(i) \]而且我们可以知道一个公式：
\[f(n)=\sum_k \binom n kg(k)\Leftrightarrow g(n)=\sum_k(-1)^{n-k}\binom n kf(k) \]这个可以简单自己证一下。
然后我们对于一个之前推出来的公式反演：
\[\sum_k\binom n k\frac{(-1)^k}{x+k}=\frac 1 x\binom {x+n}n^{-1} \]设 \(g(k)=\frac {(-1)^k}{x+k}\)，\(f(n)=\frac 1 x\binom {x+n}n^{-1}\)，则：
\[\sum_k\binom n kg(k)=f(n)\\ g(n)=\sum_k(-1)^{n-k}\binom n kf(k)\\ \frac {(-1)^n}{x+n}=\sum_k\binom n k(-1)^{n-k}\frac 1 x\binom {x+k}k^{-1}\\ \frac x {x+n}=\sum_k\binom n k(-1)^k\binom {x+k}k^{-1}\\ \frac x {x+n}=\sum_k\binom n k\binom {-x-1}k^{-1}\\ \frac {-m-1} {-m-1+n}=\sum_k\binom n k\binom {m}k^{-1}\\ \frac {m+1} {m+1-n}=\sum_k\binom n k\binom {m}k^{-1}\\ \]天哪，这简直就是 Q1
5.4 生成函数
拉格朗日反演
如果存在 \(F(z),G(z)\) 无常数项，有一次项，且互为复合逆，那么我们有拉格朗日反演和拓展拉格朗日反演：
\[[z^n]G(z)=\frac 1 n[z^{n-1}](\frac {F(z)} {z})^{-n}\\ [z^n]H(G(z))=\frac 1 n[z^{n-1}]H(z)'(\frac {F(z)}z)^{-n}\\ \]然后我们考虑证明这个东西，首先我们要知道一个引理（形式留数）：
对于无常数项，有一次项的函数 \(F(z)\)：
\[[z^{-1}]F(z)F^k(z)=[k=-1] \]证明：
\[k\not=-1 ,[z^{-1}]F'(z)F^k(z)=[z^{-1}](\frac {1}{k+1}F^{k+1}(z))' \]此时求导不会产生 \([z^{-1}]\) 项。
\[k=-1,[z^{-1}]\frac {F'(z)}{F(z)}=[z^0]\frac {F'(z)}{F(z)/z}=\frac {f_1+2f_2z+3f_3z^2+\ldots}{f_1+f_2z+f_3z^2+\ldots}=1 \]证毕。
然后我们证明一下拉格朗日反演：
\[G(F(z))=z\\ \sum_{i=0}G[i]iF^{i-1}F'=1\\ \sum_{i=0}G[i]iF^{i-n-1}F'=F^{-n}\\ \sum_{i=0}G[i]i[z^{-1}]F^{i-n-1}F'=[z^{-1}]F^{-n}\\ \sum_{i=0}G[i]i[i-n-1=-1]=[z^{-1}]F^{-n}\\ nG[n]=[z^{-1}]F^{-n}\\ [z^n]G(z)=\frac 1 n[z^{n-1}](\frac{F(z)}{z})^{-n}\\ \]然后拓展拉格朗日反演就是记 \(T(z)=H(G(z))\)，则 \(T(F(z))=H(G(F(z)))=H(z)\)，然后差不多的流程做即可。
但是拉格朗日反演在 \(n=0\) 时不能使用，我们要考虑另外一种方法，我们称其为另类拉格朗日反演及其拓展：
\[[z^n]G(z)=[z^{n-1}](\frac {F(z)}z)^{-n-1}F'(z)\\ [z^n]H(G(z))=[z^n](\frac {F(z)}z)^{-n-1}F'(z)H(z) \]证明大概是把本来用求导构造出 \(F'\) 变成了两端直接乘 \(F'\) 即可。
\[\begin{align} G(F(z))&=z\\ \sum_{i=0}G[i]F^{i}F'&=zF'\\ \sum_{i=0}G[i]F^{i-n-1}F'&=zF'F^{-n}\\ \sum_{i=0}G[i][z^{-1}]F^{i-n-1}F'&=[z^{-1}]zF'F^{-n-1}\\ \sum_{i=0}G[i][i-n-1=-1]&=[z^{-2}]F'F^{-n-1}\\ G[n]&=[z^{-2}]F'F^{-n-1}\\ [z^{n}]G(z)&=[z^{n-1}](\frac{F(z)}{z})^{-n-1}F'\\ \end{align} \]拓展也是类似的证明即可。
我们可以把目前知道的四个式子列在一起，方便后面查询
我们来个例题：
[ABC222H] Beautiful Binary Tree
对于一个正整数 \(n\)，我们称满足以下条件的有根二叉树是一棵美丽的 \(n\) 阶二叉树。
- 每个节点有一个数字 \(0\) 或 \(1\)，节点 \(i\) 的数字记为 \(a_i\)。
- 每个叶子节点的数字定是 \(1\)。
- 可以通过进行如下的操作至多 \(n - 1\) 次，使得最终根节点上的数字为 \(n\)，其余节点的数字是 \(0\)
选择两个节点 \(u, v\)，其中 \(u\) 需要是 \(v\) 的父节点或父节点的父节点。作赋值 \(a_u\leftarrow a_u + a_v, a_v\leftarrow 0\)。
给定 \(n\)，请计算美丽的 \(n\) 阶二叉树的数量。答案对 \(998244353\) 取模。
\(n \le 10^7\)。
我们考虑什么样的树是合法的。
- 根节点为权值 \(1\)
- 所有点权值和为 \(n\)。
- 不存在一条边上两个都是 \(0\)。
我们不妨设 \(F\) 为这样的树个数且树可以为空的生成函数，\(G\) 为根节点为 \(0\) 其他都满足的树且树不为空个数的生成函数，则：
\[F=z(F+G)^2+1\\ G=F^2-1 \]然后得到：
\[F=z(F^2+F-1)^2+1 \]由于 \([z^0]F(z)=1\)，我们令 \(A(z)=F(z)-1\)，则：
\[A(z)=z(A^2(z)+3A(z)+1)^2 \]构造 \(A\) 的复合逆 \(B\)，则 \(B(z)=\frac {z}{z^2+3z+1}\)，由拉格朗日反演得到：
\[[z^n]A(z)=\frac 1 n[z^{n-1}](\frac {z}{B(z)})^n\\ =\frac 1 n[z^{n-1}](z^2+3z+1)^{2n}\\ =\frac 1 n\sum_{i=0}^{\lfloor \frac{n-1}2\rfloor} \begin{pmatrix} 2n \\ i\ \ \ n-1-2i\ \ n+i+1 \end{pmatrix} 3^{n-2i-1} \]然后即可 \(O(n)\) 解决。
广义二项级数
定义广义二项级数如下：
\[\mathcal B_t(z)=\sum_{n\ge 0}\binom {tn+1}{n}\frac {z^n}{tn+1}=\sum_{n\ge 0}(tn)^{\underline{n-1}}\frac {z^n}{n!} \]然后关于这个有一些等式：
\[\begin{align} \mathcal B_t(z) &=z\mathcal B_t(z)^t+1\Leftrightarrow \mathcal B_t(z)^{1-t}-\mathcal B_t(z)^{-t}=z \tag{1}\\ \mathcal B_t(z)^r &=\sum_{n\ge 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\ge 0}\binom {tn+r}{n} z^n\tag{3}\\ \end{align} \]我们可以使用拉格朗日反演来证明这些等式。
对于 \((1)\)，我们令 \(F(z)=\mathcal B_t(z)-1\)，那么我们得到：
\[F(z)=z(F(z)+1)^t \]令 \(G(z)=\frac {z}{(z+1)^t}\)，则我们得到：
\[[z^n]F(z)=\frac 1 n[z^{n-1}](\frac {z}{G(z)})^n=\frac 1 n \binom {nt}{n-1} \]当 \(n>0\) 时我们有
\[\frac 1 n\binom{nt}{n-1}=\frac {1}{tn+1}\binom{tn+1}n \]然后对于 \(n=0\) 时明显成立，所以
\[B_t(z)=\sum_{n\ge 0}\binom {tn+1}n\frac {z^n}n \]这样我们就证明了 \((1)\)。
对于 \((2)\)，我们考虑令 \(H(z)=(1+z)^r\)，则运用拓展拉格朗日定理可以知道
\[[z^n]\mathcal B_t(z)^r&=\frac 1 n[z^{n-1}]r(1+z)^{tn+r-1}\\ &=\frac r n\binom {tn+r-1}{n-1}\\ \]当 \(n>0\) 时，\(\frac r n\binom {tn+r-1}{n-1}=\frac {r}{tn+r}\binom {tn+r}n\)
当 \(n=0\) 时，两者 \([z^0]\) 系数相同，所以 \((2)\) 得证。
对于 \((3)\)，我们设 \(H(z)=\frac {(1+z)^r}{1-t+t(1+z)^{-1}}\)，则：
\[\begin{align} [z^n]\mathcal B_t(z)&=\frac 1 n[z^{n-1}](1+z)^{tn}\frac {r(1+z)^{r-1}(1-t+t(1+z)^{-1})+(1+z)^{r-2}t}{(1-t+t(1+z)^{-1})^2}\\ &=\frac 1 n[z^{n-1}](1+z)^{tn+r}(\frac {r}{1-(t-1)z}+\frac t{(1-(t-1)z)^2})\\ &=\frac 1 n\sum_{i=0}^{n-1}\binom {tn+r}i(r(t-1)^{n-1-i}+t(n-i)(t-1)^{n-1-i})\\ &=\frac {1} n((tn+r)\sum_{i=0}^{n-1}\binom {tn+r}i(t-1)^{n-1-i}-t\sum_{i=0}^{n-1}\binom {tn+r}ii(t-1)^{n-1-i})\\ &=\frac 1 n[z^{n-1}]((tn+r)\frac {(1+z)^{tn+r}}{1-(t-1)z}-tz\frac {((1+z)^{tn+r})'}{1-(t-1)z})\\ &=\frac 1 n[z^{n-1}]\frac {(tn+r)(1+z)^{tn+r-1}(1+z-tz)}{1-(t-1)z}\\ &=\frac {tn+r}n\binom {tn+r-1}{n-1}=\binom {tn+r}n \end{align} \]但是有没有更简单的做法呢。
我们考虑运用拓展另类拉格朗日反演：
\[\begin{align} [z^n]\mathcal B_t(z)&=[z^n]H(z)G'(z)(\frac z {G(z)})^{n+1}\\ &=[z^n]\frac {(1+z)^r}{1-t+t(1+z)^{-1}}\frac {(1+z)^t-tz(1+z)^{t-1}}{(1+z)^{2t}}(1+z)^{tn+t}\\ &=[z^n]\frac {(1+z)^{r+1}}{1+z-tz}\frac {1+z-tz}{(1+z)^{t+1}}(1+z)^{tn+t}\\ &=[z^n](1+z)^{tn+r}=\binom {tn+r}n \end{align} \]具体数学上使用了牛牛的 Raney 定理进行组合意义的证明，但是不想去看了。
我们考虑给广义二项级数找组合意义，我们发现如下例题：
\(n\) 个点无标号有根 \(m\) 叉树计数，子树顺序可以区分。
我们考虑用符号化方法表示，即 \(\mathcal A=\mathcal E+\mathcal Z\times \mathcal A^m\)，写成生成函数就是 \(F(z)=zF(z)^t+1\)，我们发现这跟 \(\mathcal B_m(z)\) 相同，所以我们就找到了广义二项级数的一个组合意义。
我们考虑把 \((2),(3)\) 等式两端相乘，得到：
\[\mathcal B_t(z)^r\frac {B_t(z)^s}{1-t+t\mathcal B_t(z)^{-1}}=\sum_{n\ge 0}\sum_{k\ge 0}(\binom {tn+r}r\frac r {tn+r})\binom {t(n-k)+s}{n-k}z^n\\ LHS=\frac {\mathcal B_t(z)^{r+s}}{1-t+t\mathcal B_t(z)^{-1}}=\sum_{n\ge 0}\binom {tn+r+s}nz^n \]所以我们得到恒等式：
\[\sum_{k\ge 0}\binom {tn+r}r\binom {t(n-k)+s}{n-k}\frac r {tn+r}=\binom {tn+r+s}n \]我们来点习题：
\[\begin{align} S&=\sum_{i\ge 0}\frac 1 {2^{n+2i}(n+2i)}\binom {n+2i}i\\ &=\frac 1 {2^nn}\sum_{i\ge 0}\binom {2i+n}{i}\frac{n}{(n+2i)}(\frac 1 4)^i\\ &=\frac 1 {2^nn}\mathcal B_2(\frac 1 4)^n \end{align} \]然后根据
\[\begin{align} \mathcal B_2(z)&=z\mathcal B_2(z)^2+1\\ \mathcal B_2(z)&=\frac {1\pm \sqrt{1-4z}}{2z} \end{align} \]然后由于 \([z^0]\mathcal B_2(z)=1\)，所以我们得到：
\[\mathcal B_2(z)=\frac {1-\sqrt {1-4z}}{2z} \]然后代入 \(S\) 得到 \(S=\frac 1 n\)。
\[\begin{align} S&=\sum_k\binom {2k-1}k\binom {4n-2k-1}{2n-k}\frac {(-1)^{k+1}}{(2k-1)(4n-2k-1)}\\ \end{align} \]我们知道：
\[\mathcal B_2(z)^{-1}=-\sum_{k\ge 0}\binom {2k-1}{k}\frac {z^k}{2k-1}\\ \mathcal B_2(-z)^{-1}=\sum_{k\ge 0}\binom {2k-1}{k}\frac {(-1)^{k+1}z^k}{2k-1}\\ \]\[\begin{align} S&=-[x^{2n}]\mathcal B_2(z)^{-1}\mathcal B_2(-z)^{-1}\\ &=-[x^{2n}]\frac {1+\sqrt {1-4z}}2\times \frac {1+\sqrt {1+4z}}2\\ &=-[x^{2n}]\frac {\sqrt{1-16z^2}}4+\frac 1 4+\frac {\mathcal B_2(z)^{-1}}2+\frac {\mathcal B_2(-z)^{-1}}2 \end{align} \]然后我们拆成几部分做：
\[\begin{align} [x^{2n}]\sqrt{1-16z^2}&=\binom {\frac 1 2}n(-1)^n16^n\\ &=\binom {n-\frac 2 3}n16^n\\ &=\frac {(2n-3)(2n-5)(2n-7)\ldots (-1)}{n!}8^n\\ &=-\frac 1 {2n-1}\frac {2^n\prod_{i=1}^n(2i-1)}{n!}4^n\\ \end{align} \]我们可以证明：
\[2^n\prod_{i=1}^n{(2i-1)}=(2n)^\underline n \]具体来说就是你构造双射后用勒得让定理随便证一下，所以：
\[\begin{align} [x^{2n}]\sqrt{1-16z^2}&=-\frac 1 {2n-1}\binom {2n} n4^n\\ \end{align} \]剩下几项可以类似得到，最后我们得到：
\[S=\frac{\binom {2n}n4^{n-1}}{2n-1}+\frac {\binom {4n-1}{2n}}{4n-1} \]广义指数级数
定义广义指数级数为：
\[\mathcal E_t(z)=\sum_{n\ge 0}(tn+1)^{n-1}\frac {z^n}{n!} \]\[\begin{align} \mathcal E_t(z)^{-t}\ln \mathcal E_t(z)&=z\tag{1}\\ \mathcal E_t(z)^{r}&=\sum_{n\ge 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\ge 0}(tn+r)^n\frac {z^n}{n!}\tag3 \end{align} \]我们考虑证明 \((1)\)，令 \(F(z)=\ln \mathcal E_t(z),H(z)=e^z\)，则 \(\mathcal E_t(z)=H(F(z))\)：
\[\begin{align} e^{-tF(z)}F(z)&=z\\ [z^n]\mathcal E_t(z)&=[z^n]H(F(z))\\ &=\frac 1 n[z^{n-1}]H'(z)(\frac {z}{G(z)})^n\\ &=\frac 1 n[z^{n-1}]e^z(\frac {z}{e^{-tz}z})^n\\ &=\frac 1 n[z^{n-1}]e^{z(tn+1)}\\ &=\frac {(tn+1)^{n-1}}{n!} \end{align} \]我们考虑 \((2)\)，发现令 \(H(z)=e^{zr}\) 即可。
然后得到：
\[\begin{align} [z^n]\mathcal E_t(z)^r&=[z^n]H(F(z))\\ &=\frac 1 n[z^{n-1}]re^{rz}(\frac z {G(z)})^n\\ &=\frac r n[z^{n-1}]e^{z(tn+r)}\\ &=r\frac {(tn+r)^{n-1}}{n!} \end{align} \]由于 \((1)\)，我们知道 \(F(z)=\ln \mathcal E_t(z)=\mathcal zE_t(z)^t\)，那么我们就令 \(H(z)=\frac {e^{rz}}{1-tz}\)
\[\begin{align} [z^n]\frac {\mathcal E_t(z)^r}{1-zt\mathcal E_t(z)^t} &=[z^{n}]H(F(z))\\ &=\frac 1 n[z^{n-1}]H(z)'(\frac {z}{G(z)})^n\\ &=\frac 1 n[z^{n-1}]\frac {re^{rz}(1-tz)+te^{rz}}{(1-tz)^2}e^{tnz}\\ &=\frac 1 n[z^{n-1}]e^{(tn+r)z}(\frac r {1-tz}+\frac t{(1-tz)^2})\\ \end{align} \]然后接下来套路推一下就行了，实际上是我不想推了
我们考虑另类拉格朗日反演：
\[\begin{align} [z^n]\frac {\mathcal E_t(z)^r}{1-zt\mathcal E_t(z)^t} &=[z^n]H(F(z))\\ &=[z^n]H(z)(\frac z {G(z)})^{n+1}G'(z)\\ &=[z^n]\frac {e^{rz}}{1-tz}e^{t(n+1)z}(1-tz)e^{-tz}\\ &=[z^n]e^{(tn+r)z}\\ &=\frac {(tn+r)^n}{n!} \end{align} \]但是非常有趣的是，这个东西可能并没有什么用
为了方便以后查阅，我们可以把所有的式子放在一起：
\[\begin{align} \mathcal B_t(z)&=\sum_{n\ge 0}\binom {tn+1}{n}\frac {z^n}{tn+1}\\ \mathcal B_t(z) &=z\mathcal B_t(z)^t+1 \\ \mathcal B_t(z)^r &=\sum_{n\ge 0}\binom {tn+r}{n} \frac {r}{tn+r}z^n\\ \frac{\mathcal B_t(z)^r}{1-t+t\mathcal B_t(z)^{-1}} &=\sum_{n\ge 0}\binom {tn+r}{n} z^n\\ \mathcal E_t(z)&=\sum_{n\ge 0}(tn+1)^{n-1}\frac {z^n}{n!}\\ \mathcal E_t(z)^{-t}\ln \mathcal E_t(z)&=z\\ \mathcal E_t(z)^{r}&=\sum_{n\ge 0}r(tn+r)^{n-1}\frac {z^n}{n!}\\ \frac {\mathcal E_t(z)^r}{1-zt\mathcal E_t(z)^t}&=\sum_{n\ge 0}(tn+r)^n\frac {z^n}{n!} \end{align} \]5.5 超几何函数
一般的超几何级数是一个关于 \(z\) 且带有 \(n+m\) 个参数的幂级数，它用上升的阶乘幂定义如下：
\[\begin{align} F\left( \begin{gathered} a_1,\cdots,a_m\\ b_1,\cdots,b_n \end{gathered} \middle|z\right)=F(a_1,\cdots,a_m;b_1,\cdots,b_n;z)=\sum_{k\ge 0}\frac {a_1^\overline k\cdots a_m^\overline kz^k}{b_1^\overline k\cdots b_n^\overline kk!} \end{align} \]首先我们可以发现一些常用的：
\[\begin{align} F\left(\begin{gathered} 1\\1 \end{gathered}\middle|\ z\right) &=\sum_{k\ge 0}\frac {z^k}{k!}=e^z\\ F\left(\begin{gathered} 1,1\\1 \end{gathered}\middle|\ z\right)&=\sum_{k\ge 0}z^k=\frac {1}{1-z}\\ F\left(\begin{gathered} a,1\\1 \end{gathered}\middle|\ z\right)&=\sum_{k\ge 0}\binom {a-1+k}{k}z^k=\frac {1}{(1-z)^a}\\ F\left(\begin{gathered} -a,1\\1 \end{gathered}\middle|\ -z\right)&=\sum_{k\ge 0}\binom {a-1+k}{k}z^k=(1+z)^a\\ \end{align} \]高斯超几何函数：
\[\begin{align} F\left(\begin{gathered} a,b\\c \end{gathered}\middle|\ z\right) =\sum_{k\ge 0}\frac {a^\overline kb^\overline kz^k}{c^\overline kk!} \end{align} \]有一个重要的特殊情形是：
\[\ln (1+z)=zF\left(\begin{gathered} 1,1\\2 \end{gathered}\middle|\ z\right)=z\sum_{k\ge 0}\frac {k!k!(-z)^k}{(k+1)k!}\\ =z-\frac {z^2}2+\frac {z^3}3+\cdots \]所以我们知道 \(z^{-1}\ln(1+z)\) 是一个超几何函数，但是 \(\ln(1+z)\) 一定不是一个超几何函数，因为超几何级数在 \(z=0\) 时一定为 \(1\)。
我们设一个超几何级数：
\[\begin{align} F\left(\begin{gathered} a_1,\cdots a_m\\b_1,\cdots b_n \end{gathered}\middle|\ z\right)=\sum_{k\ge 0}t_kz^k \end{align} \]则我们知道：
\[\frac {t_{k+1}}{t_k}=\frac {(k+a_1)\cdots (k+a_m)z}{(k+b_1)\cdots (k+b_n)(k+1)} \]然后我们就能构造一些超几何函数。
比如
\[\sum_{k\le n}\binom {r+k}k=\sum_{k\ge 0}\binom {r+n-k}{n-k}=\sum_{k\ge 0}\frac {(r+n-k)!}{r!(n-k)!}=\sum_{k\ge 0}t_k \]所以
\[\frac {t_{k+1}}{t_k}=\frac {(r+n-k-1)!r!(n-k)!}{r!(n-k-1)!(r+n-k)!}=\frac {n-k}{r+n-k}\\ =\frac {(k+1)(k-n)(1)}{(k-n-r)(k+1)}\\ t_0=\binom {n+r}n \]所以我们得到：
\[\begin{align} \binom {n+r}n F\left(\begin{gathered} 1,-n\\-n-r \end{gathered}\middle|\ 1\right)=\binom {n+r+1}n\\ F\left(\begin{gathered} 1,-n\\-n-r \end{gathered}\middle|\ 1\right)=\frac {r+n+1}{r+1} \end{align} \]这个时候我们讨论一下阶乘这个东西，有一个最有用的定义，它实际上是 \(\frac 1 {z!}\) 的定义：
\[\frac 1 {z!}=\lim_{n\to \infty} \binom {n+z}n n^{-z} \]这个对于所有复数 \(z\) 都存在，而且它仅当 \(z\) 是负整数时取值为 \(0\)。
还有另外一个有意义的定义是：
\[z!=\int_0^\infty t^ze^{-t}dt,\mathfrak Rz>-1 \]当然还有很类似的函数，称为 $\Gamma $ 函数，然后有公式：
\[\Gamma (z+1)=z!\\ (-z)!\Gamma(z)=\frac \pi {\sin {\pi z}} \]uob 先生告诉我们，当 \(a,b\in \Z\) 时，虽然负数不存在阶乘，但是可以这样理解：
我们看一看范德蒙德卷积：
\[%\begin{align} \sum_k\binom rk \binom s {n-k}=\binom {r+s}k\\ t_k=\frac {r!s!}{(r-k)!k!(s-n+k)!(n-k)!}\\ \frac {t_{k+1}}{t_k}=\frac {(k-r)(k-n)}{(k+1)(s-n+k+1)}\\ \binom sn F\left(\begin{gathered} -r,-n\\s-n+1 \end{gathered}\middle|\ 1\right) =\binom {r+s}n %\end{align} \]所以我们可以知道：
\[F\left(\begin{gathered} a,b\\c \end{gathered}\middle|\ 1\right)=\frac {(c-a-b-1)!(c-1)!}{(c-a-1)!(c-b-1)!} %=\frac {\Gamma (c-a-b)\Gamma(c)}{\Gamma (c-a)\Gamma(c-b)} %;(b\in \Z,b\ge 0)，或者 \mathfrak R_c>\mathfrak R_a+\mathfrak R_b \]很抱歉，P176~P213 页内容鸽了
第六章
6.1 斯特林数
P220
求证：
\[\begin{align} x^n=\sum_k{n\brace k}(-1)^{n-k}x^\overline k\\ x^\underline n=\sum_k{n\brack k}(-1)^{n-k}x^ k\\ \end{align} \]考虑归纳
\[\begin{align} x^{n+1}&=x\times x^{n}\\ &=x\sum_k{n\brace k}(-1)^{n-k}x^\overline k\\ &=\sum_k{n\brace k}(-1)^{n-k}x^\overline{k+1}-\sum_kk{n\brace k}(-1)^{n-k}x^\overline{k}\\ &=\sum_k{n\brace k-1}(-1)^{n-k+1}x^\overline{k}+\sum_kk{n\brace k}(-1)^{n-k+1}x^\overline{k}\\ &=\sum_k({n\brace k-1}+k{n\brace k})(-1)^{n+1-k}x^\overline{k}\\ &=\sum_k{n+1\brace k}(-1)^{n+1-k}x^\overline k \end{align} \]另外一个差不多的方式证明。
标签：frac,sum,更新,tn,数学,笔记,mathcal,binom,align From： https://www.cnblogs.com/Nityacke/p/18122383/Math