ホーム >> 組合せ >> 長椅子に詰めて座る場合の数
hide or visible

問題の説明

標準的な順列の問題です.以下,説明をわかりやすくするために座席に左から $1$ から $7$ までの番号を振って区別します.
順列
最初に席に座る人は $7$ つのどの席に座っても良いですが,$2$ 番目以降に座る人は,前に座った人によって,座り方を制限されるという問題です.たとえば,一番目の人が $1$ 番に座った場合,二番目の人は $2$ 番の席にしか座れません.また,一番目の人が $4$ 番に座った場合,二番目の人は $3$ 番か $5$ 番の席にしか座れません.

順列の問題の多くは様々な考え方を用いて解けます.この問題も解き方はいろいろあります.

樹形図を用いる

最も単純ですぐに思いつくであろう方法は全ての場合を数え上げるという方法です.下図のように座席の番号を用いて樹形図を書いていけばいずれはすべての場合を書き上げることができます.
樹形図
このように単に数え上げるという方法も立派な解き方です.もれなくすべての場合を数え上げるためには,注意力と集中力が必要です.

組み合わせとして捉える

もう少し工夫した方法で解いてみましょう.
説明をわかりやすくするために,仮に一番目の人が $3$ 番の席に座ったとします.ここで,残りの $6$ 人の座る座席の番号を順列として表してみましょう.たとえば, $$2→4→5→1→6→7$$ などという順列がありえます.これは,二番目の人が $2$ 番に,三番目の人が $4$ 番に,という風に座っていったことを示しています.このようにして作られた順列について次のことが容易にわかります.

(i) $2,1$ は必ずこの順に並ぶ.
(ii) $4,5,6,7$ は必ずこの順に並ぶ.

すべての人は詰めて座るのですからこれらは当然成り立ちます.
ここで,発想を転換して,$6$ つの空白に $1,2,4,5,6,7$ の数を埋めることを考えます.
空白
$2,1$ をこの順に, $6$ つの空白のいずれかに埋める方法は ${}_6 \mathrm{C} _2 =15$ 通りです.
空白
残りの $4,5,6,7$ は必ずこの順に並ぶので,ただ一通りの埋め方しか存在しません.結局,一番目の人が $3$ 番の席に座った場合の残りの人の座り方は,${}_6 \mathrm{C} _2 =15$ 通りであることがわかります.

他の場合も同様に考えて,一番目の人が $i$ 番 ($1 \le i \le 7$) の席に座った場合の残りの人の座り方は,${}_6 \mathrm{C} _{i-1} $ 通りです.

したがって,すべての席の埋まり方は, $${}_6 \mathrm{C} _{0}+{}_6 \mathrm{C} _{1}+{}_6 \mathrm{C} _{2}+{}_6 \mathrm{C} _{3}+{}_6 \mathrm{C} _{4}+{}_6 \mathrm{C} _{5}+{}_6 \mathrm{C} _{6}=64$$ $64$ 通りです.

別の問題に置き換える

前の解き方の最後の部分を見てみると, $${}_6 \mathrm{C} _{0}+{}_6 \mathrm{C} _{1}+{}_6 \mathrm{C} _{2}+{}_6 \mathrm{C} _{3}+{}_6 \mathrm{C} _{4}+{}_6 \mathrm{C} _{5}+{}_6 \mathrm{C} _{6}$$ という式が現れています.二項展開を思い出してみると, $$2^6=(1+1)^6={}_6 \mathrm{C} _{0}+{}_6 \mathrm{C} _{1}+{}_6 \mathrm{C} _{2}+{}_6 \mathrm{C} _{3}+{}_6 \mathrm{C} _{4}+{}_6 \mathrm{C} _{5}+{}_6 \mathrm{C} _{6}$$ です.ここで,ひとつ疑問となるのが,今回の問題の答えは $64$ 通りで,それは,${}_6 \mathrm{C} _{0}+{}_6 \mathrm{C} _{1}+{}_6 \mathrm{C} _{2}+{}_6 \mathrm{C} _{3}+{}_6 \mathrm{C} _{4}+{}_6 \mathrm{C} _{5}+{}_6 \mathrm{C} _{6}$ として求めたけれど,最初から $2^6$ 通りであることを示すことはできないか,ということです.

この疑問については,実際,一発で $2^6$ 通りであることを示す考え方があります.

まず,横一列に赤玉または青玉を合計 $6$ つ並べる順列を考えます.(片方の色しか並べなくてもよい) これは紛れもなく $2^6=64$ 通りの場合があります.実は今回の問題の $7$ 人の座り方が,この赤玉青玉の並べ方に一対一に対応しているのです!!
なぜそうなるのかは,ご自身で考えてみてください.


$n$ 席の場合は $2^{n-1}$ 通りの埋まり方がありますね.