U636249 别样的第一类斯特林数行求和

设一个有向环的 EGF 为

F (x)

，由于

i

个点可以构成

(i - 1)!

个本质不同的有向环，故

\begin {align*} F (x) & = k \sum _ {n = 0} (n - 1)! \frac {x ^ n} {n!} \\ & = k \sum _ {n = 0} \frac 1 n x ^ n \\ & = -k \ln (1 - x) \tag {1} \end {align*}

其中

(1)

式可用泰勒展开或求导后积分证明。

原图相当于若干个有向环的集合，设原图的 EGF 为

G (x)

，则

\begin {align*} G (x) & = \exp (F (x)) \\ & = \exp (-k \ln (1 - x)) \\ & = (1 - x) ^ {-k} \\ & = \sum _ {n = 0} \binom {n + k - 1} {k - 1} x ^ n \end {align*}

故答案为

\left[\frac {x ^ n} {n!}\right] G (x) = \binom {n + k - 1} {k - 1} n! = (n + k - 1) ^ {\underline n}

文章操作