問 $n$ を $2$ 以上の自然数とする.円卓に $n$ 個の椅子が用意されていて,$n$ 人の人が順番に座る.各椅子には $n$ 人それぞれの名札が置いてある.はじめ,$A_1$ 氏は間違えて自分の席ではなく,(時計回りに)そのとなりの席に座ってしまった.ほかの人々は順に,自分の席に座るか,そこにすでにほかの人が座っていれば時計回りにその席に一番近い空いている席に座った.このようにして座るとき,異なる座り方は何通りあるか.
2018/7/11
組合せ
★★☆☆☆
$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}$ 通りです.