[F] Slow and Steady
前半の解説
置換 $\sigma$ が巡回置換 $\tau_1, \cdots, \tau_r$ の積で $\sigma=\tau_1\cdots \tau_r$ と表せたとき，$\sigma$ の近道度 $m(\sigma)$ は $\tau_1, \cdots, \tau_r$ の近道度の積
$$
m(\sigma)=m(\tau_1)\cdots m(\tau_r)
$$
になります。これを利用すると，$f_n$ の漸化式を導くことができます。
自然数 $n$ に対して，$\mathfrak{S}_n$ の元の近道度の和を
$$
M_n:=\sum_{\sigma\in\mathfrak{S}_n}m(\sigma)
$$
とおくことにします。これは，$M_n=n!f_n$ とおいたことに相当します。
$n!$ 個の置換の近道度の和を考える際に，$n$ が含まれる巡回置換の長さが同じものごとにまとめて計算してみましょう。
$n$ が含まれる巡回置換の長さが $k$ であるものを考えます。例えば $n=3$ なら，$\mathfrak{S}_3$ の元は
$$
(1)(2)(3), (12)(3), (13)(2), (1)(23), (123), (132)
$$
の $6$ 個ですが，そのうち，$3$ が含まれる巡回置換の長さが $k=1,2,3$ であるものは
\begin{align}
k=1: & \; (1)(2)(3), (12)(3)\\
k=2: & \; (13)(2), (1)(23)\\
k=3: & \; (123), (132)
\end{align}
のように $2$ 個ずつ存在します。より一般に，$n$ が含まれる巡回置換の長さが $k$ であるような置換の個数は
$$
(n-k)! {}_{n-1}{\rm C}_{k-1}(k-1)!
$$
です。なぜなら，$n$ が含まれる巡回置換に登場する $n$ 以外の数の選び方が ${}_{n-1}{\rm C}_{k-1}$ 通り，それらを並べる方法の総数が $(k-1)!$ 通り（$k$ 個の円順列です），それ以外の巡回置換の決め方が $(n-k)!$ 通りあるからです。$n$ が含まれる巡回置換の近道度は $1/k$ ですから，$n$ が含まれる巡回置換の長さが $k$ であるような置換の近道度の和は
$$
{}_{n-1}{\rm C}_{k-1}(k-1)! \sum_{\sigma\in\mathfrak{S}_{n-k}} m(\sigma)\cdot \frac{1}{k}={}_{n-1}{\rm C}_{k-1}(k-1)!\frac{M_{n-k}}{k}
$$
と表されます（ここで近道度が積に分解できるという冒頭で述べた性質を使いました）。したがって，$n!$ 個の置換の近道度の和は，これを $k=1,\cdots, n$ に対して加え合わせた
$$
M_n=\sum_{k=1}^n {}_{n-1}{\rm C}_{k-1}(k-1)!\frac{M_{n-k}}{k}
$$
となります。あとは，$M_n=n!f_n$ の関係を用いれば，$f_n$ が満たすべき漸化式
\begin{align}
f_n&=\frac{1}{n!}\sum_{k=1}^n {}_{n-1}{\rm C}_{k-1}(k-1)!\frac{(n-k)!f_{n-k}}{k}\\
&=\frac{1}{n!}\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!}(k-1)!\frac{(n-k)!f_{n-k}}{k}\\
&=\frac{1}{n}\sum_{k=1}^n \frac{f_{n-k}}{k}\quad (n=1,2,\cdots )
\end{align}
を得ることができます。これを繰り返し用いると
$$
f_2=\frac{3}{4},\; f_3=\frac{19}{36},\; f_4=\frac{107}{288}
$$
が分かります。
後半の解説
唐突ですが，$t$ の関数 $f(t)$ を
$$
f(t)=\sum_{n=0}^{\infty} f_nt^n
$$
で定義します。級数
$$
\sum_{n=0}^{\infty} f_n
$$
が収束することは問題文で与えられているので，$f(t)$ は少なくとも $-1 < t \leq 1$ で定義されています。そこで今から，$f(t)$ の関数形を求めることにしましょう。
試しに $f(t)$ を $t$ で微分すると
\begin{align}
f'(t)&=\frac{d}{dt}\left(\sum_{n=0}^{\infty} f_nt^n\right)\\
&=\sum_{n=1}^{\infty} nf_nt^{n-1}\\
&=\sum_{n=1}^{\infty} nt^{n-1}\left(\frac{1}{n}\sum_{k=1}^n \frac{f_{n-k}}{k}\right)\\
&=\sum_{n=1}^{\infty}\sum_{k=1}^n \frac{f_{n-k}}{k}t^{n-1}\\
&=\sum_{n=0}^{\infty}\sum_{k=0}^{n} \frac{f_{n-k}}{k+1}t^{n}\\
&=\left(\sum_{n=0}^{\infty} f_nt^n\right)\left(\sum_{n=0}^{\infty} \frac{t^n}{n+1}\right)\\
&=f(t)\left(\sum_{n=0}^{\infty} \frac{t^n}{n+1}\right)
\end{align}
が成り立ちます。ただし，$3$ 行目への変形には $f_n$ の漸化式を利用し，$5$ 行目への変形では和の変数 $n, k$ をずらしました。また，$5$ 行目はたたみこみの形になっているため $6$ 行目の形に変形しました。
これは $f(t)$ についての微分方程式になっており，変数分離形を利用することで簡単に解くことができます。$f(0)=1$ に注意して積分すると
\begin{align}
\log f(t)&=\int_0^t \sum_{n=0}^{\infty} \frac{(t')^n}{n+1}dt'\\
&=\sum_{n=0}^{\infty} \frac{t^{n+1}}{(n+1)^2}\\
&=\sum_{n=1}^{\infty} \frac{t^n}{n^2}
\end{align}
が得られます。よって
$$
f(t)=\exp\left(\sum_{n=1}^{\infty} \frac{t^n}{n^2}\right)
$$
が成り立つことが分かりました。両辺に $t=1$ を代入すれば
$$
\sum_{n=0}^{\infty} f_n=\exp\left(\sum_{n=1}^{\infty} \frac{1}{n^2}\right)=\exp\left(\frac{\pi^2}{6}\right)=5.18\cdots
$$
となり，したがって答えは 5.2 です。
補足
-
上で登場した関数$$
{\rm Li}_2(t):=\sum_{n=1}^{\infty} \frac{t^n}{n^2}
$$は二重対数関数（dilogarithm）と呼ばれる特殊関数で，積分表示$$
{\rm Li}_2(t)=-\int_0^t \frac{\log (1-u)}{u}du
$$をもちます。 -
$f_n$ はオンライン整数列辞典（OEIS）に載っているようです（特に情報量はありませんが）。
分子 A323290 (https://oeis.org/A323290)
分母 A323291 (https://oeis.org/A323291) -
漸化式が求まったら、級数の値を数値計算により求めることも可能です。要求精度を得るために必要な項数を $N$ とすると、計算量は $O(N^2)$ になります。
-
級数が収束することの証明は読者の演習問題とします。また、解答中で極限操作の入れ替えをしていますが、その正当化も演習問題とします。
おすすめ問題
この問題を解いた人はこんな問題も解いています
