U636249 别样的第一类斯特林数行求和
yemuzhe
·
·
题解
设一个有向环的 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}