JMO2017予選9を級数で解く
$1,2,\cdots,2017$の並べ替え$\sigma=(\sigma(1),\sigma(2),\cdots,\sigma(2017))$について、$\sigma(i)=i$となる$1\leq i\leq2017$の個数を$F(\sigma)$とする．すべての並べ替え$\sigma$について$F(\sigma)^4$を足し合わせた値を求めよ．
この問題を級数の力で解こうと思います。
まず、予備知識の解説をします。(知っている方は飛ばしてください)
$1,2,\cdots,n$の順列$\sigma$のうち、$i=1,\cdots,n$について$\sigma(i)\neq i$となるものを完全順列と言う。
また、完全順列の個数をモンモール数と言い、$!n$で表す。($!0=1$とする)
(私も最近まで完全順列とモンモール数が同じものだと思っていましたが実は違うみたいです)
$!n$を書き並べてみると$1,0,1,2,9,44,265,\cdots$となります。
モンモール数については次の性質が成り立ちます。
$(2)\ !n=n\times!(n-1)+(-1)^n$
$(3)\ \displaystyle!n=\sum_{k=0}^n(-1)^k\frac{n!}{k!}$
$(4)\ \displaystyle\lim_{n\to\infty}\frac{!n}{n!}=\frac{1}{e}$
(3)だけ証明します。
$\sigma(i)=i$をみたす順列$\sigma$の集合を$A_i$とおく。
有限集合$X$の要素の個数を$|X|$で表す。
包除原理より、$!n=n!-|A_1\cup A_2\cup\cdots\cup A_n| \\=n!-|A_1|-|A_2|-\cdots-|A_n| \\+|A_1\cap A_2|+\cdots+(-1)^{n-1}|A_2\cap A_3\cap\cdots\cap A_n| \\+(-1)^n|A_1\cap A_2\cap\cdots\cap A_n|$
となる。
ここで、$|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|$($i_1,\cdots,i_k$はすべて異なる)について考える。
$A_{i_1}\cap A_{i_2}\cap A_{i_k}$の元$\sigma$については$\sigma(i_j)=i_j\ (j=1,\cdots,k)$が成り立ち、他の値については制限が無いので、そのような$\sigma$は$n-k$個の元の並べ替えから$(n-k)!$個である。
また、この形の項は$1,\cdots,n$の中から$i_1,\cdots,i_k$を選ぶため(順番が異なるものも同じとして数える)、その個数は$\binom{n}{k}$個である。
よって、
$\displaystyle!n=\sum_{k=0}^n(-1)^k(n-k)!\binom{n}{k} \\\displaystyle=\sum_{k=0}^n(-1)^k\frac{n!}{k!}$
が導かれた。
本題に入ります。
$2017$の代わりに$n$として計算します。($n\geq4$)
$1,2,\cdots,n$の順列の集合を$S_n$とします。
このとき、求めるべき値は$\sum_{\sigma\in S_n}F(\sigma)^4$です。
$S_n$の元のうち$F(\sigma)=n-k$となるものの個数を考えると、$\sigma(i)=i$となる$i$の選び方が$\binom{n}{k}$通り、残りの$k$個については$\sigma(i)\neq i$となる必要があるのでその$k$個について$\sigma(i)$の値の組は$!k$通りとなり、個数は$\binom{n}{k}\cdot!k$とわかります。
これより、
$\displaystyle\sum_{\sigma\in S_n}F(\sigma)^4=\sum_{k=0}^n(n-k)^4\binom{n}{k}\cdot!k
\\\displaystyle=n!\sum_{k=0}^n\frac{!k}{k!}\frac{(n-k)^4}{(n-k)!}$
となります。
求めやすそうな形になってきましたが、もう少しいじります。
$\displaystyle\frac{(n-k)^4}{(n-k)!}=\frac{1}{(n-k-1)!}+\frac{7}{(n-k-2)!}+\frac{6}{(n-k-3)!}+\frac{1}{(n-k-4)!}$
としておきます。
以下、$\displaystyle\sum_{k=0}^n\frac{!k}{k!}\frac{1}{(n-k-m)!}\ (m=0,1,2,\cdots)\ (n\geq m)$を求めていきます。(負の整数$n$に対して$\frac{1}{n!}=0$とします)
$!n$を級数の係数として表すことを考えます。
先ほど証明した式を使うと、$\displaystyle\frac{!n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}$となるので、$\displaystyle\sum_{n=0}^\infty\frac{!n}{n!}x^n=\sum_{n=0}^\infty\sum_{k=0}^n\frac{(-1)^k}{k!}x^n
\\\displaystyle=\sum_{n=0}^\infty\frac{(-1)^n}{n!}x^n\cdot\sum_{n=0}^\infty x^n=\frac{e^{-x}}{1-x}$
また、$\displaystyle\sum_{n=0}^\infty\frac{1}{(n-m)!}x^n=x^me^x$となるので、
$\displaystyle\sum_{n=0}^\infty\sum_{k=0}^n\frac{!k}{k!}\frac{1}{(n-k-m)!}x^n
\\\displaystyle=\sum_{n=0}^\infty\frac{!n}{n!}x^n\cdot\sum_{n=0}^\infty\frac{x^n}{(n-m)!}
\\\displaystyle=\frac{e^{-x}}{1-x}\cdot x^me^x=\frac{x^m}{1-x}
\\\displaystyle=\sum_{n=m}^\infty x^n$
とできます。
これで、両辺の係数を比較することで$\displaystyle\sum_{k=0}^n\frac{!k}{k!}\frac{1}{(n-k-m)!}=1\ (n\geq m)$がわかりました。
よって、
$\displaystyle\sum_{\sigma\in S_n}F(\sigma)^4=n!(1+7+6+1)=15n!$
であり、答えは$15\cdot2017!$となります。
