Let's Go Cycling

操作によって作られる可能性のある全てのグラフについて閉路の個数を求め、その総和をグラフの個数で割ったものが答えとなります。これを愚直に求めることはできないので、各 $k\ (2 \le k \le N)$ ごとにサイズ $k$ の閉路が合計で何回現れるかを数えていきます。

便宜上、閉路に含まれる頂点にある頂点からの距離の順に番号を付けて、それぞれ $a_i$ と呼びます。

• $a_1$ として有り得る頂点は $N$ 通り
• $a_2$ として有り得る頂点は $N-1$ 通り
• $\vdots$
• $a_k$ として有り得る頂点は $N-k+1$ 通り
• 閉路に含まれない頂点はどうなっていてもよく、それらは $(N-1)^{N-k}$ 通り

これらに加え、$\{a_i\}$ を巡回させたものを重複して数えないように注意すれば、サイズ $k$ の閉路が $\displaystyle \frac{N!(N-1)^{N-k}}{(N-k)!k}=\frac{_N P _k(N-1)^{N-k}}{k}$ 回現れることが分かります。

有り得るグラフは $(N-1)^N$ 個あるので、答えは $\displaystyle \frac{1}{(N-1)^N} \sum_{k=2}^{N}\frac{_N P _k(N-1)^{N-k}}{k}$ です。