JMO2017予選9を級数で解く

670

JMO2017予選9

1, 2, \dots, 2017

の並べ替え

σ = (σ (1), σ (2), \dots, σ (2017))

について、

σ (i) = i

となる

1 \leq i \leq 2017

の個数を

F (σ)

とする．すべての並べ替え

σ

について

F (σ)^{4}

を足し合わせた値を求めよ．

この問題を級数の力で解こうと思います。

まず、予備知識の解説をします。(知っている方は飛ばしてください)

(完全順列,モンモール数)

1, 2, \dots, n

の順列

σ

のうち、

i = 1, \dots, n

について

σ (i) \neq i

となるものを完全順列と言う。
また、完全順列の個数をモンモール数と言い、

! n

で表す。(

! 0 = 1

とする)

(私も最近まで完全順列とモンモール数が同じものだと思っていましたが実は違うみたいです)
$! n$ を書き並べてみると $1, 0, 1, 2, 9, 44, 265, \dots$ となります。

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

(1)! n = (n - 1) (! (n - 1) +! (n - 2))

(2)! n = n \times! (n - 1) + (- 1)^{n}

(3)! n = \sum_{k = 0}^{n} (- 1)^{k} \frac{n!}{k!}

(4) lim_{n \to \infty} \frac{! n}{n!} = \frac{1}{e}

(3)だけ証明します。

(3の証明)

σ (i) = i

をみたす順列

σ

の集合を

A_{i}

とおく。
有限集合

X

の要素の個数を

| X |

で表す。
包除原理より、

! n = n! - | A_{1} \cup A_{2} \cup \dots \cup A_{n} | = n! - | A_{1} | - | A_{2} | - \dots - | A_{n} | + | A_{1} \cap A_{2} | + \dots + (- 1)^{n - 1} | A_{2} \cap A_{3} \cap \dots \cap A_{n} | + (- 1)^{n} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |

となる。
ここで、

| A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}} |

(

i_{1}, \dots, i_{k}

はすべて異なる)について考える。

A_{i_{1}} \cap A_{i_{2}} \cap A_{i_{k}}

の元

σ

については

σ (i_{j}) = i_{j} (j = 1, \dots, k)

が成り立ち、他の値については制限が無いので、そのような

σ

は

n - k

個の元の並べ替えから

(n - k)!

個である。
また、この形の項は

1, \dots, n

の中から

i_{1}, \dots, i_{k}

を選ぶため(順番が異なるものも同じとして数える)、その個数は

(\binom{n}{k})

個である。
よって、

! n = \sum_{k = 0}^{n} (- 1)^{k} (n - k)! (\binom{n}{k}) = \sum_{k = 0}^{n} (- 1)^{k} \frac{n!}{k!}

が導かれた。

本題に入ります。
$2017$ の代わりに $n$ として計算します。( $n \geq 4$ )
$1, 2, \dots, n$ の順列の集合を $S_{n}$ とします。
このとき、求めるべき値は $\sum_{σ \in S_{n}} F (σ)^{4}$ です。
$S_{n}$ の元のうち $F (σ) = n - k$ となるものの個数を考えると、 $σ (i) = i$ となる $i$ の選び方が $(\binom{n}{k})$ 通り、残りの $k$ 個については $σ (i) \neq i$ となる必要があるのでその $k$ 個について $σ (i)$ の値の組は $! k$ 通りとなり、個数は $(\binom{n}{k}) \cdot! k$ とわかります。
これより、
$\sum_{σ \in S_{n}} F (σ)^{4} = \sum_{k = 0}^{n} (n - k)^{4} (\binom{n}{k}) \cdot! k = n! \sum_{k = 0}^{n} \frac{! k}{k!} \frac{(n - k)^{4}}{(n - k)!}$
となります。
求めやすそうな形になってきましたが、もう少しいじります。
$\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)!}$
としておきます。
以下、 $\sum_{k = 0}^{n} \frac{! k}{k!} \frac{1}{(n - k - m)!} (m = 0, 1, 2, \dots) (n \geq m)$ を求めていきます。(負の整数 $n$ に対して $\frac{1}{n!} = 0$ とします)

$! n$ を級数の係数として表すことを考えます。
先ほど証明した式を使うと、 $\frac{! n}{n!} = \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$ となるので、 $\sum_{n = 0}^{\infty} \frac{! n}{n!} x^{n} = \sum_{n = 0}^{\infty} \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!} x^{n} = \sum_{n = 0}^{\infty} \frac{(- 1)^{n}}{n!} x^{n} \cdot \sum_{n = 0}^{\infty} x^{n} = \frac{e^{- x}}{1 - x}$
また、 $\sum_{n = 0}^{\infty} \frac{1}{(n - m)!} x^{n} = x^{m} e^{x}$ となるので、
$\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} \frac{! k}{k!} \frac{1}{(n - k - m)!} x^{n} = \sum_{n = 0}^{\infty} \frac{! n}{n!} x^{n} \cdot \sum_{n = 0}^{\infty} \frac{x^{n}}{(n - m)!} = \frac{e^{- x}}{1 - x} \cdot x^{m} e^{x} = \frac{x^{m}}{1 - x} = \sum_{n = m}^{\infty} x^{n}$
とできます。
これで、両辺の係数を比較することで $\sum_{k = 0}^{n} \frac{! k}{k!} \frac{1}{(n - k - m)!} = 1 (n \geq m)$ がわかりました。
よって、
$\sum_{σ \in S_{n}} F (σ)^{4} = n! (1 + 7 + 6 + 1) = 15 n!$
であり、答えは $15 \cdot 2017!$ となります。