ホーム >> 組合せ >> 円卓に座る場合の数
hide or visible

問題の説明

$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}$ 通りです.