Stirling & Stirling Inversion

Waiting for the end.

递推式

$$ \begin{aligned} \begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\cdot \begin{Bmatrix}n-1\\k \end{Bmatrix}\\ \begin{bmatrix}n\\k \end{bmatrix}=\begin{bmatrix}n-1\\k-1 \end{bmatrix}+(n-1)\cdot \begin{bmatrix}n-1\\k \end{bmatrix} \end{aligned} $$

与上升幂下降幂的关系

$$ C_n^kk!=n^{\underline k}\\ \Rightarrow \displaystyle n^m=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}C_n^kk!=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}n^{\underline k}\\ $$ $$ \displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k $$

可以归纳法证明上式。

反演

$$ \displaystyle f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k) \Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k) $$

首先有 $(-1)^n(-x^{\underline n}) = x^{\underline n}$ ，这个直接打开化简就可以得到。同理可以有 $(-1)^n(-x^{\overline n}) = x^{\overline n}$ 。

于是带入 $\displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k$ 得到下式

$$ \begin{aligned} \displaystyle n^m&=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k(-n)^{\overline{k}}\\ &=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k\sum_{j=0}^k\begin{bmatrix}k\\j\end{bmatrix}(-n)^j\\ &=\sum_{j=0}^mn^j\sum_{k=j}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j} \end{aligned} $$

于是得到了

$$ \begin{aligned} \displaystyle \sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]\\ \sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n] \end{aligned} $$

下面的式子是同理能得到的。

于是有

$$ \begin{aligned} \displaystyle g(n)&=\sum_{j=0}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}f(j)\\ \Rightarrow f(n)&=\sum_{j=0}^n[j=n]f(j)\\ &=\sum_{j=0}^n\sum_{k=j}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{j=0}^k(-1)^{k-j}\begin{bmatrix}k\\j\end{bmatrix}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix} g(k) \end{aligned} $$

Crash 的文明世界

$$ \begin{aligned} S(u) &= \sum_{v = 1}^{n} \mathrm{dist}(u, v)^{k} \\ &= \sum_{v = 1}^{n} \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} \binom{\mathrm{dist}(u, v)}{i}i! \\ &= \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{v = 1}^{n} \binom{\mathrm{dist}(u, v)}{i} \end{aligned} $$

令 $dp_{u, i} = \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i}$ 。

$$ \begin{aligned} \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i} &= \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v) - 1}{i} + \binom{\mathrm{dist}(u, v) - 1}{i - 1} \\ &= \sum_{v \in son(u)} dp_{v, i} + dp_{v, i - 1} \end{aligned} $$

Summary

$$ n^k = \sum_{i = 1}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \binom{n}{i} $$

Crash 的文明世界

$$ \begin{aligned} S(u) &= \sum_{v = 1}^{n} \mathrm{dist}(u, v)^{k} \\ &= \sum_{v = 1}^{n} \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} \binom{\mathrm{dist}(u, v)}{i}i! \\ &= \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{v = 1}^{n} \binom{\mathrm{dist}(u, v)}{i} \end{aligned} $$

令 $dp_{u, i} = \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i}$ 。

$$ \begin{aligned} \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i} &= \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v) - 1}{i} + \binom{\mathrm{dist}(u, v) - 1}{i - 1} \\ &= \sum_{v \in son(u)} dp_{v, i} + dp_{v, i - 1} \end{aligned} $$

CF932E

$$ \begin{aligned} &\sum_{i = 1}^{n} \binom{n}{i} i^k \\ =&\sum_{i = 1}^{n} \binom{n}{i} \sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{i}{j} \\ =&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \sum_{i = j}^{n} \binom{n}{i} \binom{i}{j} \\ =&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \sum_{i = j}^{n} \binom{n}{j} \binom{n - j}{i - j} \\ =&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{n}{j} \sum_{i = 0}^{n - j} \binom{n}{i} \\ =&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{n}{j} 2^{n - j} \\ \end{aligned} $$

可以 $\Theta(k^2 + k \log n)$ 。