11

JMO2017予選9を級数で解く

515
1
$$$$
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$となります。

モンモール数については次の性質が成り立ちます。

$(1)\ !n=(n-1)(!(n-1)+!(n-2))$
$(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)だけ証明します。

(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!$となります。

投稿日:2021118

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

tria_math
tria_math
476
34858
大学2年生

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中