miscalc のブログ

主に競プロの話をします

JMO 2017 予選 9 を母関数で解いてみた

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

問題

問題リンク

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) で求まる。