斯特林数·后缀

· · 个人记录

给定 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}.

$$ \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} $$ 于是这个看起来非常诡异的东西就得到了说明.