\(N\) を \(5\) 以上の整数とする. \(1\) 以上 \(2N\) 以下の整数から, 相異なる \(N\) 個の整数を選ぶ. ただし \(1\) は必ず選ぶこととする. 選んだ数の集合を \(S\) とし, \(S\) に関する以下の条件を考える.
条件 1 : \(S\) は連続する \(2\) 個の整数からなる集合を \(1\) つも含まない.
条件 2 : \(S\) は連続する \(N-2\) 個の整数からなる集合を少なくとも \(1\) つ含む.
ただし, \(2\) 以上の整数 \(k\) に対して, 連続する \(k\) 個の整数からなる集合とは, ある整数 \(l\) を用いて \(\{ l , l+1 , \cdots , l+k-1 \}\) と表される集合を指す. 例えば \(\{ 1 , 2 , 3 , 5 , 7 , 8 , 9 , 10 \}\) は連続する \(3\) 個の整数からなる集合 \(\{ 1 , 2 , 3 \}\) , \(\{ 7 , 8 , 9 \}\) , \(\{ 8 , 9 , 10 \}\) を含む.
(1) 条件 1 を満たすような選び方は何通りあるか.
(2) 条件 2 を満たすような選び方は何通りあるか.
【 解 答 】
(1)
選ぶ数字を ○ , 選ばない数字を × に置きかえると, ○ が隣り合わない並べ方を考えればよい.
\(1\) は必ず選ぶので, \(N\) 個の ○ に対して, 以下のように並べれば条件をみたす.
\(N-1\) か所の間と右端に × を \(1\) つずつ並べる.
\(N-1\) か所の間のうち \(1\) か所に \(2\) つ, 残りに \(1\) つずつ × を並べる.
よって, 求める選び方は \[ 1 +( N-1 ) = \underline{N} \text{通り} \]
(2)
○ が \(K\) 個並ぶ部分を \(\underbrace{\text{○ … ○}} _ K\) と表す.
\(N \geqq 5\) より \(N-2 \gt 2\) なので, 条件をみたす選び方は, 以下の通り.
1* 「 \(\underbrace{\text{○ … ○}} _ N\) × 」で始まるとき
残りはすべて × で, \(1\) 通り.2* 「 \(\underbrace{\text{○ … ○}} _ {N-1}\) × 」で始まるとき
残り \(N\) か所のうち \(1\) か所が ○ で残りが × である場合で \[ N \ \text{通り} \]3* 「 \(\underbrace{\text{○ … ○}} _ {N-2}\) × 」で始まるとき
残り \(N+1\) か所のうち \(2\) か所が ○ で残りが × である場合で \[ {} _ {N+1} \text{C}{} _ {2} = \dfrac{N (N+1)}{2} \ \text{通り} \]4* 「 ○ ○ × 」で始まるとき
残り \(2N-3\) か所に \(\underbrace{\text{○ … ○}} _ {N-2}\) が \(1\) つある場合で \[ (2N-3) -(N-2) +1 = N \ \text{通り} \]5* 「 ○ × 」で始まるとき
残り \(2N-2\) 箇所について- \(\underbrace{\text{○ … ○}} _ {N-1}\) が \(1\) つある場合で \[ (2N-2) -(N-1) +1 = N \ \text{通り} \]
- \(\underbrace{\text{○ … ○}} _ {N-2}\) が \(1\) つ, これと離れた ○ が \(1\) つの場合のうち,
\(\underbrace{\text{○ … ○}} _ {N-2}\) が両端にある場合（\(2\) 通りある）は, ○ の場所の選び方は \(N-1\) 通りあり,
\(\underbrace{\text{○ … ○}} _ {N-2}\) が両端にない場合（\(N-1\) 通りある）は, ○ の場所の選び方は \(N-2\) 通りあるので \[ 2 (N-1) +(N-1) (N-2) = N (N-1) \ \text{通り} \]
以上より, 求める選び方は \[\begin{align} & 1 +N +\dfrac{N (N+1)}{2} +N +N +N (N-1) \\ & \qquad = \dfrac{3}{2} N^2 +\dfrac{5}{2} N +1 \\ & \qquad = \underline{\dfrac{1}{2} (3N+2) (N+1) \ \text{通り}} \end{align}\]