EGMO 2020
問題 4

$1,2,\dots,n$ の並べ替えであって，最初の $m$ 項が $1,2,\dots,m$ の並べ替えであるような $m$ の最小値が $k$ であるようなものは $(n-k)!\cdot f_k$ 個だけあるので，以下の式が成り立つ．

$$n!=\sum_{k=1}^n(n-k)!\cdot f_k$$

この式から

$$\begin{aligned} f_{n-1}&=(n-1)!-\sum_{k=1}^{n-2}(n-1-k)!\cdot f_k\\ f_n&=n!-\sum_{k=1}^{n-2}(n-k)!\cdot f_k-f_{n-1} \end{aligned}$$

がわかるので

$$f_n-nf_{n-1}=\sum_{k=1}^{n-2}(n-1-k)!\cdot kf_k-f_{n-1}$$

が従う．ここで

$$\begin{aligned} (n-1)!&=\sum_{k=1}^{n-1}(n-1-k)!\cdot f_k\\ &=(n-1)\sum_{k=1}^{n-2}(n-2-k)!\cdot f_k-\sum_{k=1}^{n-2}(n-2-k)!\cdot kf_k+f_{n-1}\\ &=(n-1)!-\sum_{k=1}^{n-2}(n-2-k)!\cdot kf_k+f_{n-1} \end{aligned}$$

が成り立つので

$$f_{n-1}=\sum_{k=1}^{n-2}(n-2-k)!\cdot kf_k\leq \sum_{k=1}^{n-2}(n-1-k)!\cdot kf_k$$

が従う．これを用いれば $f_n-nf_{n-1}\geq 0$ が従う．よって示された．