斯特林数·后缀

给定 $n,k$，对于 $0\leq i\leq k$，求出 $\begin{Bmatrix}n\\n-i\end{Bmatrix}$ 和 $\begin{bmatrix}n\\n-i\end{bmatrix}$

需要 $O(k\log k)$ 复杂度

~~做法0:从具体数学表7.3上抄下来两个式子~~

$$
\left(\frac{z}{\ln(1+z)}\right)^{n}=\sum_{i\geq 0}\frac{z^i}{i!}\begin{Bmatrix}n\\n-i\end{Bmatrix}\left/\binom{n-1}{i}\right.
$$

$$
\left(\frac{z}{1-e^{-z}}\right)^{n}=\sum_{i\geq 0}\frac{z^i}{i!}\begin{bmatrix}n\\n-i\end{bmatrix}\left/\binom{n-1}{i}\right.
$$

对第一个式子的~~阴间~~证明:

$$
\begin{aligned}\left(\frac{-z}{\ln\left(\frac{1}{1-(-z)}\right)}\right)^m
=&(-z)^m\left(\ln\left(\frac{1}{1-(-z)}\right)\right)^{-m}\\
=&(-z)^m(-m)!\sum_n\begin{bmatrix}n\\-m\end{bmatrix}\frac{(-z)^n}{n!}\\
=&(-z)^m(-m)!\sum_n\begin{Bmatrix}m\\-n\end{Bmatrix}\frac{(-z)^n}{n!}\\
=&\sum_n\begin{Bmatrix}m\\n\end{Bmatrix}(-z)^{m-n}\frac{(-m)!}{(-n)!}\\
=&\sum_n\begin{Bmatrix}m\\m-n\end{Bmatrix}z^n\frac{(-1)^n}{(-m+n)^{\underline{n}}}\\
=&\sum_n\frac{z^n}{n!}\begin{Bmatrix}m\\m-n\end{Bmatrix}\left/\binom{m-1}{n}\right.
\end{aligned}
$$

第二个式子也类似.

----

做法1:拉格朗日反演(感谢EI教育)

考虑

$$
\begin{bmatrix}n\\n-i\end{bmatrix}(n-i)!=[n!z^n]\left(\ln\frac{1}{1-z}\right)^{n-i}
$$

那么再加一个元可以写为

$$
\begin{bmatrix}n\\n-i\end{bmatrix}(n-i)!=[n!z^nt^{n-i}]\sum_{i\geq 0}\left(t\ln\frac{1}{1-z}\right)^i=[n!z^nt^{n-i}]\frac{1}{1-t\ln(1/(1-z))}
$$

使用拉格朗日反演得到

$$
[z^n]\frac{1}{1-t\ln(1/(1-z))}=\frac{1}{n}[z^{n-1}]\left(\frac{1}{1-tz}\right)'\left(\frac{z}{1-e^{-z}}\right)^n
$$

因为 $\ln(1/(1-z))$ 的复合逆即 $1-e^{-z}$.

$(1/(1-tz))'$ 具有简单的形式

$$
\sum_{i\geq 0}(i+1)t^{i+1}z^i
$$

那么 $t^{n-i}$ 前的系数就应当是

$$
\frac{n-i}{n}[z^i]\left(\frac{z}{1-e^{-z}}\right)^n
$$

这就给出

$$
\left(\frac{z}{1-e^{-z}}\right)^n=\sum_{i\geq 0}\frac{z^i}{i!}\begin{bmatrix}n\\n-i\end{bmatrix}\left/\binom{n-1}{i}\right.
$$

于是就用阳间的方式完成了证明. 第一个式子也类似.

----
这告诉我们了什么呢？审视方法 $0$ 中的式子，在证明中我们使用了这样一个事实:

$$
\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{bmatrix}-m\\-n\end{bmatrix}
$$

这实际上可以由拉格朗日反演得到. 由于 $\ln(\dfrac{1}{1-z})$ 的复合逆为 $1-e^{-z}$，由拉格朗日反演我们有

$$
[z^n](1-e^{-z})^m=\frac{1}{n}[z^{-1}]mz^{m-1}\ln(\dfrac{1}{1-z})^{-n}=\frac{m}{n}[z^{-m}]\ln(\frac{1}{1-z})^{-n}
$$

那么展开成对应的斯特林数（允许拓展到负数），我们就得到

$$
(-1)^{n+m}\frac{m!}{n!}\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{m}{n}\frac{(-n)!}{(-m)!}\begin{bmatrix}-m\\-n\end{bmatrix}
$$

把阶乘约去，我们就得到了

$$
\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{bmatrix}-m\\-n\end{bmatrix}
$$

于是这个看起来非常诡异的东西就得到了说明.