数学B 漸化式の応用 問題 6 解説

方針・初手

隣り合う車両の少なくとも一方が赤色であるという条件は、「赤色でない車両が隣り合ってはいけない」と言い換えられる。

したがって、赤色でない車両をどの位置に置くかを数え、その各位置を青色または黄色に塗る方法を数えればよい。

解法1

赤色でない車両を $k$ 両選ぶとする。この $k$ 両は互いに隣り合ってはいけない。

$n$ 個の位置から、隣り合わないように $k$ 個の位置を選ぶ方法は

$$ {}_{n-k+1}\mathrm{C}_{k} $$

通りである。

実際、選んだ位置を

$$ 1 \leq a_1<a_2<\cdots<a_k\leq n $$

とすると、隣り合わない条件は

$$ a_{i+1}-a_i\geq 2 $$

である。ここで

$$ b_i=a_i-(i-1) $$

とおくと、

$$ 1\leq b_1<b_2<\cdots<b_k\leq n-k+1 $$

となるので、これは $n-k+1$ 個から $k$ 個を選ぶことに対応する。

また、赤色でない位置はそれぞれ青色または黄色の $2$ 通りで塗れるので、赤色でない車両が $k$ 両ある場合の塗り方は

$$ {}_{n-k+1}\mathrm{C}_{k}2^k $$

通りである。

赤色でない車両は最大でも

$$ \left\lfloor \frac{n+1}{2}\right\rfloor $$

両まで置けるから、求める塗り方の総数は

$$ \sum_{k=0}^{\left\lfloor (n+1)/2\right\rfloor} {}_{n-k+1}\mathrm{C}_{k}2^k $$

である。

さらに、この和は次の漸化式から簡単な形にできる。

解法2

条件を満たす $n$ 両編成の塗り方の数を $a_n$ とする。

最後尾の第 $n$ 車両に注目する。

（i） 第 $n$ 車両が赤色の場合

第 $1$ 車両から第 $n-1$ 車両までは条件を満たせばよいので、

$$ a_{n-1} $$

通りである。

（ii） 第 $n$ 車両が青色または黄色の場合

第 $n$ 車両が赤色でないため、第 $n-1$ 車両は必ず赤色でなければならない。

第 $n$ 車両の色は青色または黄色の $2$ 通りであり、第 $1$ 車両から第 $n-2$ 車両までは条件を満たせばよいので、

$$ 2a_{n-2} $$

通りである。

よって、$n\geq 3$ に対して

$$ a_n=a_{n-1}+2a_{n-2} $$

が成り立つ。

初期値は

$$ a_1=3 $$

であり、また $n=2$ のときは、両方とも赤色でない場合だけが不可なので

$$ a_2=3^2-2^2=5 $$

である。

漸化式

$$ a_n=a_{n-1}+2a_{n-2} $$

の特性方程式は

$$ x^2=x+2 $$

すなわち

$$ (x-2)(x+1)=0 $$

である。したがって、

$$ a_n=A2^n+B(-1)^n $$

と表せる。

初期値 $a_1=3,\ a_2=5$ を代入すると、

$$ \begin{cases} 2A-B=3,\\ 4A+B=5 \end{cases} $$

である。これを解いて

$$ A=\frac{4}{3},\qquad B=-\frac{1}{3} $$

を得る。

よって

$$ a_n=\frac{4}{3}2^n-\frac{1}{3}(-1)^n $$

すなわち

$$ a_n=\frac{2^{n+2}-(-1)^n}{3} $$

である。

解説

この問題の条件は、「赤を含む隣接対」ではなく、「赤でないものが連続しない」と見直すのが本質である。

数え上げとしては、赤でない車両の位置を隣り合わないように選ぶ方法で数える解法1が直接的である。一方、最後尾に注目して場合分けすると、漸化式

$$ a_n=a_{n-1}+2a_{n-2} $$

が自然に出る。最終的な閉じた形まで求めるなら、解法2の方が簡潔である。

答え

求める塗り方の数は

$$ \boxed{\frac{2^{n+2}-(-1)^n}{3}} $$

通りである。

同値な形として、

$$ \boxed{ \sum_{k=0}^{\left\lfloor (n+1)/2\right\rfloor} {}_{n-k+1}\mathrm{C}_{k}2^k } $$

とも表せる。