CodeIQ 挑戦の記録 : 第83回「超」整理法に従って並べなおして！

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

標準入力より本の冊数nが与えられる。
n冊の全ての並び方について元の並び方に戻す事を考える。
並び替え方は任意の本を左端に挿入し、それ以外を順に右にずらす。これの繰り返し。
最短の回数で全パターンの並び替え回数の合計を出力する。

方針

f(n)を全パターンの回数の合計とすると漸化式は次の通り

${f(1)=0}$
${f(n)=n!-1+n \times f(n-1) }$

提出したコードは下記の通り。Ruby(76)

def c(n);return 0 if n==1;(1..n).inject(1,:*)-1+n*c(n-1);end;p c(gets.to_i)

どこからこの漸化式が出てきたかですが、例によって?
勘です。

というか、出題者である増井先生の著書「プログラマ脳を鍛える　数学パズル」にほとんど同じ過去問が記載されています。
その問題では、自動採点では無く1秒の時間制限が無いのと、入力のnが7で、本問の最大15よりかなり小さい数ですので、模範解答も全探索と少し工夫して高速化したものを挙げられてました。
そして、参考程度に以下の様に書かれてありますので引用させて頂きます。

数学的に対称群で考えると、巡回置換の積で求められますので、以下の漸化式で表すことができます。

この後に漸化式が記載されているのですが、大学で数学をやっていない文系趣味グラマーとしては群論はさっぱりですので、この過去問でどうしてその漸化式になるか全く分かりません。
そこで、下記に記載する全探索のコードを書いて、ある程度小さい数値で試した結果から漸化式を予想するという乱暴な方法で上記の式を導いたという次第です。

全探索のコード（但しnの最大は9まで）

言語:c++
幅優先探索を使用して、ある並び方から問題文の逆の並べ方で生成する全てのパターンについてその回数を加算した合計を出力するもの。
実行時間は「実行くん」でn=9のケースで約0.5秒　　

では、