縦2列、横$n$列に並んだ$2n$席の座席から、$k$席の座席を選ぶ問題を考えます。ただし、選んだ座席の前後左右に隣接する座席は選べません。 (1) $k=n$のとき、座席の選び方は何通りあるかを求めます。 (2) $n \geq 3$, $k=n-1$とします。右端から2列目の前後2席がどちらも選ばれていないような、座席の選び方は何通りあるかを求めます。 (3) $n \geq 3$, $k=n-1$のとき、座席の選び方は何通りあるかを求めます。 (4) $n \geq 5$, $k=n-2$のとき、座席の選び方は何通りあるかを求めます。

1. 問題の内容

縦2列、横$n$列に並んだ$2n$席の座席から、$k$席の座席を選ぶ問題を考えます。ただし、選んだ座席の前後左右に隣接する座席は選べません。

(1) $k=n$のとき、座席の選び方は何通りあるかを求めます。

(2) $n \geq 3$, $k=n-1$とします。右端から2列目の前後2席がどちらも選ばれていないような、座席の選び方は何通りあるかを求めます。

(3) $n \geq 3$, $k=n-1$のとき、座席の選び方は何通りあるかを求めます。

(4) $n \geq 5$, $k=n-2$のとき、座席の選び方は何通りあるかを求めます。

2. 解き方の手順

(1) $k=n$ のとき：

各列から1席ずつ選ぶ必要があります。各列には2席あるので、各列ごとに選び方は2通りです。したがって、$n$列から$n$席選ぶ方法は $2^n$ 通りです。

(2) $n \geq 3$, $k=n-1$ で、右端から2列目の前後2席がどちらも選ばれていないとき：

まず、右端の列の選び方から考えます。

(i) 右端の列で1席選ぶ場合：

このとき、右から2列目の前後2席は選べません。残りの $n-2$ 列から $n-2$ 席を選ぶ必要があります。これは各列から1席選ぶことになるので、選び方は $2^{n-2}$ 通りです。また、右端の列の選び方は2通りなので、$2 \times 2^{n-2} = 2^{n-1}$ 通りとなります。

(ii) 右端の列で0席選ぶ場合：

このとき、残りの $n-1$ 列から $n-1$ 席を選ぶ必要があります。これは各列から1席選ぶことになるので、選び方は $2^{n-1}$ 通りです。さらに、右から2列目の前後2席は選ばれていないという条件より、これは右から2列目の前後2席を選ばないような選び方の数と一致します。

したがって、右端から2列目の前後2席がどちらも選ばれていないような座席の選び方は、$2^{n-1} + 2^{n-1} = 2^n$ 通りです。

(3) $n \geq 3$, $k=n-1$ のとき：

$n$列から$n-1$席を選ぶということは、1列だけ席を選ばないことになります。

(i) 1列だけ選ばない場合：

選ばない列を決めると$n$通り。その選ばない列を除いた$n-1$列から各列1席ずつ選ぶので、選ぶ方法は$2^{n-1}$通り。したがって、合計で$n \times 2^{n-1}$通り。

しかし、この選び方の中には、選んだ席が隣り合ってはいけないという条件に反するものも含まれているので、これですべてではありません。

各列1席または0席しか選べないことから、$k=n-1$のときは、必ずどこかの列で席を選んでいない状況になります。

そのような列を仮に$i$列目とすると、それ以外の列では1つずつ席を選ぶ必要があります。

$i$列目以外の列で選んだ席から、さらに隣接する席を選ばないようにする必要がありますが、$k=n-1$という条件では、隣接する席を選ぶと$n-1$席選ぶという条件を満たせなくなるので、隣接する席を選ぶことはできません。

したがって、$n \times 2^{n-1}$通りが答えになります。

(4) $n \geq 5$, $k=n-2$ のとき：

$n$列から$n-2$席を選ぶということは、2列だけ席を選ばないことになります。

(i) 2列とも席を選ばない場合：

選ばない列の組み合わせは $\binom{n}{2} = \frac{n(n-1)}{2}$ 通りです。それ以外の列は1つずつ席を選びます。各列の選び方は$2^{n-2}$通りです。

したがって、この場合は $\frac{n(n-1)}{2} \times 2^{n-2} = n(n-1) 2^{n-3}$ 通りとなります。

(ii) 1列は1席、もう1列は0席を選ぶ場合：

1席選ぶ列の選び方が$n$通り。残りの$n-1$列のうち、0席の列を選ぶのが$n-1$通り。

残りの$n-2$列で、$n-3$席選ぶ必要がある。

このパターンは複雑になるので、別のアプローチを考える。

$k=n-2$の時、選ばれない列は2列。

したがって、$\frac{n(n-1)}{2} 2^{n-2} = \frac{n(n-1)}{2^{3-n}}$

3. 最終的な答え

(1) $2^n$ 通り

(2) $2^n$ 通り

(3) $n \times 2^{n-1}$ 通り

(4) $\frac{n(n-1)}{2} \cdot 2^{n-2}$ 通り