問題の説明

$A_1,...,A_n$ の $n$ 人の人たちが円卓に座ります．一般性を失うことなく，時計回りに $1,2,...,n$ と番号を割り振って，$i$ 番目の席に，$A_i$ の名札が置いてあるとして構いません．はじめ，$A_1$ は間違えて $2$ 番の席に座ってしまいました．最終的な座り方は，$A_2,...,A_n$ が円卓につく順番に依存します．（つまり，$A_2,...,A_n$ が円卓につく順番をひとつ定めると，座り方がひとつ決まる）円卓につく任意の順番を考えたとき，ありうる座り方は何通りあるか，というのが問題です．

具体例

たとえば，$n=4$ のときを考えてみましょう．$A_1$ のあとに，残りの $3$ 人が来る順番は，$3!=6$ 通りあります．これら $6$ 通りについて，$A_1$〜$A_4$ がそれぞれどの位置に座るのかを調べた結果が下の表です． \begin{array}{|c|c|}\hline & ①②③④\\ \hline 234&4123 \\ \hline 243&3124 \\ \hline 324&4132 \\ \hline 342&2134 \\ \hline 423&3124 \\ \hline 432&2134 \\ \hline \end{array} たとえば，$2$ 行目の左には $234$ と書かれていますが，これは $A_2,A_3,A_4$ の順番で席に座ることを表しています．このとき，どの席にだれが座っているのかが右に書かれています．つまり，$A_2,A_3,A_4$ の順番で席に座るときは，$1$ の席に $A_4$ ，$2$ の席に $A_1$，$3$ の席に $A_2$，$4$ の席に $A_3$ が座るという具合です．

さて，この表の右列の $6$ つのうち，異なるものは $4123,3124,4132,2134$ の $4$ つです．したがって，$n=4$ のときは，異なる座り方は $4$ 通りです．

解答例

求める場合の数を $a_n$ とおいて，$a_n$ の漸化式をつくります．まず，$a_2=1$ であることはすぐにわかります．

$A_1$ が $2$ の席に座ったとします．残りの $A_2,...,A_n$ の $n-1$ 人が適当な順番で席につきます．いま，$A_2$ が $i$ 番目に来るとしましょう．($1\le i \le n-1$)

このとき，$A_2$ より先に席につく $i-1$ 人の人たちは，必ず自分自身の席につくことができます．そこで，$A_1$ の座っている席と，自分自身の席に座れた $i-1$ 人たちの席を円卓から削除して，椅子の数が $n-i$ 個の円卓を新たに考えます．

$i=n-1$ のとき，座り方は一通りに決まります．
$i< n-1$ のときは，$A_2$ より後に席につく $n-i-1$ 人の人たちの座り方はちょうど $a_{n-i}$ 通りです．以上より， $$a_{n}=1+\sum_{i=1}^{n-2}a_{n-i}$$ すなわち， $$a_{n}=a_{n-1}+a_{n-2}+\cdots +a_{2}+1$$ という漸化式が成り立ちます．これと $a_2=1$ より， $$a_{n}=2^{n-2}$$ を得ます．たとえば，数学的帰納法などを用いればよいです． したがって，答えは $2^{n-2}$ 通りです．

---