https://miscalc.hatenablog.com/entry/2024/01/11/000343

競プロにもありそうな教育的な問題だと思いました。

問題

$1, 2, \ldots, 2017$ の並べ替え $\sigma = (\sigma(1), \sigma(2), \ldots, \sigma(2017))$ について、 $\sigma(i) = i$ となる $1 \leq i \leq 2017$ の個数を $F(\sigma)$ とする。すべての並べ替え $\sigma$ について $F(\sigma) ^ 4$ を足し合わせた値を求めよ。

解答

$a _ {n, m}$ を、 $F(\sigma) = m$ であるような $1, \ldots, n$ の順列 $\sigma$ の個数とします。

$m = 0$ のときは撹乱順列の個数で、包除原理から $\displaystyle a _ {n, 0} = \sum _ {k=0} ^ {n} (-1) ^ k \binom{n}{k} (n-k)! = n! \sum _ {k=0} ^ {n} \frac{(-1) ^ k}{k!}$ とわかります（母関数による導出もあります：指数型母関数入門 – 37zigenのHP）。

一般の $m$ に対しては、一致する箇所 $m$ 個を選んだ後、残り $n-m$ 個の場所で撹乱順列を作ると考えて、 $\displaystyle a _ {n,m} = \binom{n}{m} a _ {n-m, 0} = \frac{n!}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!}$ となります。

答えは $\displaystyle \sum _ {m=0} ^ n m ^ 4 a _ {n, m} = n! \sum _ {m=0} ^ n \frac{m ^ 4}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!}$ （で $n = 2017$ としたもの）です。

母関数を使って考察します。まずは撹乱順列の個数 $\displaystyle \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!}$ の母関数を考えましょう。 $\displaystyle \frac{(-1) ^ k}{k!} = \lbrack x ^ k \rbrack e ^ {-x}$ であり、撹乱順列の個数はその累積和なので $\displaystyle \frac{1}{1 - x}$ をかけたものが母関数になります。つまり $\displaystyle \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} = \lbrack x ^ {n-m} \rbrack \frac{e ^ {-x}}{1 - x}$ です。

次に $\displaystyle \frac{m ^ 4}{m!}$ の母関数を考えましょう。このままでは考えにくいので、 $m ^ 4 = m + 7m(m-1) + 6m(m-1)(m-2) + m(m-1)(m-2)(m-3)$ と変形します（このように冪乗を下降冪の級数で表したときの係数は第 2 種スターリング数です）。すると

$\begin{align*} \frac{m ^ 4}{m!} &= \frac{1}{(m - 1)!} + \frac{7}{(m - 2)!} + \frac{6}{(m - 3)!} + \frac{1}{(m - 4)!} \\ &= \lbrack x ^ {m-1} \rbrack e ^ x + 7 \lbrack x ^ {m-2} \rbrack e ^ x + 6 \lbrack x ^ {m-3} \rbrack e ^ x + \lbrack x ^ {m-4} \rbrack e ^ x \\ &= \lbrack x ^ m \rbrack ( x e ^ x + 7 x ^ 2 e ^ x + 6 x ^ 3 e ^ x + x ^ 4 e ^ x) \end{align*}$

となります（負の階乗の逆数や負冪の係数は $0$ とみなしておきます）。よって答えは

$\begin{align*} &\phantom{{}={}} n! \sum _ {m=0} ^ n \frac{m ^ 4}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} \\ &= n! \sum _ {m=0} ^ n \lbrack x ^ m \rbrack (x + 7 x ^ 2 + 6 x ^ 3 + x ^ 4) e ^ x \cdot \lbrack x ^ {n-m} \rbrack \frac{e ^ {-x}}{1 - x} \\ &= n! \lbrack x ^ n \rbrack \frac{x + 7 x ^ 2 + 6 x ^ 3 + x ^ 4}{1 - x} \\ &= n! \lbrack x ^ n \rbrack (x + 8 x ^ 2 + 14 x ^ 3 + 15 x ^ 4 + 15 x ^ 5 + 15 x ^ 6 + \cdots) \\ &= 15 \cdot 2017! \end{align*}$

となります。（補足：2 行目から 3 行目は FPS の積の定義、3 行目から 4 行目は $\displaystyle \frac{1}{1 - x}$ 倍が累積和）

競プロ

$2017$ を $n$ に、 $4$ を $d$ に一般化したときの答えを $\mathrm{ans}(n, d)$ とすると、 $\displaystyle \mathrm{ans}(n, d) = n! \sum _ {k = 0} ^ {\min(n, d)} S(d, k)$ です（ $S(\cdot, \cdot)$ は第 2 種スターリング数）。これを（mod 998 とかで）計算する競プロの問題だと思うことにします。[多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP を参考にすると、次のことがわかります。

$D$ 固定、クエリ $n$ に対して $\mathrm{ans}(n, D)$ を求める：「第 2 種 Stirling 数」の項の「前者」の方法で $S(D, 0), \ldots, S(D, D)$ を $O(D \log D)$ で前計算して累積和をとることで、各クエリについて（階乗の計算を除いて） $O(1)$ で求まる。
$N$ 固定、 $d = 0, 1, \ldots, D \ (D \leq N)$ に対して $\mathrm{ans}(N, d)$ を求める： $S(d, k)$ がすべての $k = 0, 1, \ldots, d$ について足されることから Bell 数になって、 $O(D \log D)$ で求まる（「Bell 数」の項も参照）。
$N$ 固定、 $d = 0, 1, \ldots, D$ に対して $\mathrm{ans}(N, d)$ を求める：「第 2 種 Stirling 数」の項の「後者」を参考にすると $\displaystyle \sum _ {k=0} ^ {\min(N, D)} \frac{1}{k!} (e ^ x - 1) ^ k$ を $D$ 次まで求めればよい。これは $\displaystyle \sum _ {k=0} ^ {\min(N, D)} \frac{1}{k!} x ^ k$ を Polynomial Taylor Shift した後 $e ^ x$ を代入すればよいので（「Polynomial Taylor Shift」および「特殊な合成」の項を参照）、（階乗の計算を除いて）全体 $O(D \log ^ 2 D)$ で求まる。