入試数学コンテスト第5回第4問解答解説

文字列 $S$ の長さを $L(S)$ で表すことにすると，$n \geq 1$ のとき $$\begin{aligned} l_n&=L(w_n)\\ &=L(\{w_0, \dots, w_{n-1}\})\\ &=L(w_0)+\cdots +L(w_{n-1})+2+(n-1)\\ &=l_0+\cdots+l_{n-1}+n+1\\ &=n+1+\sum_{i=0}^{n-1}l_i \end{aligned}$$ となる．これと$$l_{n+1}=(n+1)+1+\sum_{i=0}^n l_i$$との差をとって$$l_{n+1}-l_n=l_n+1$$すなわち$$l_{n+1}+1=2(l_{n}+1)$$が $n \geq 1$ で成り立つ．（$n=0$ では正しくないことに注意！）これと$$l_1+1=4+1=5$$を合わせると，$n \geq 1$ のとき$$l_n=5\cdot 2^{n-1}-1$$が成り立つ．以上より $$\begin{equation*}l_n= \left \{ \begin{array}{ll} 5\cdot 2^{n-1}-1　&(n \geq 1) \\ 2　&(n=0) \end{array} \right. \end{equation*}$$ となる．

まず $a_n$ を計算する．文字列 $S$ に含まれるカンマ $,$ の個数を $A(S)$ で表すことにすると，$n \geq 1$ のとき $$\begin{aligned} a_n&=A(w_n)\\ &=A(\{w_0, \dots, w_{n-1}\})\\ &=A(w_0)+\cdots+A(w_{n-1})+(n-1)\\ &=(n-1)+\sum_{i=0}^{n-1}a_i \end{aligned}$$ となる．これと$$a_{n+1}=n+\sum_{i=0}^na_i$$の差をとって$$a_{n+1}-a_n=a_n+1$$すなわち$$a_{n+1}+1=2(a_n+1)$$が $n \geq 1$ で成り立つ．これと$$a_1+1=0+1=1$$を合わせると，$n \geq 1$ のとき$$a_n=2^{n-1}-1$$が成り立つ．以上より $$\begin{equation*}a_n= \left \{ \begin{array}{ll} 2^{n-1}-1　&(n \geq 1) \\ 0　&(n=0) \end{array} \right. \end{equation*}$$ となる．

また定義より$$l_n=a_n+b_n+c_n$$であり，$w_n$ の中に左括弧 $\{$ と右括弧 $\}$ は必ずペアで出現するから$$b_n=c_n$$が成り立つ．よって $n \geq 1$ のとき $$\begin{aligned} b_n=c_n&=\frac{1}{2} (l_n-a_n)\\ &=\frac{1}{2}\left(5 \cdot 2^{n-1}-1-(2^{n-1}-1)\right)\\ &=2^n \end{aligned}$$となる．これは $n=0$ でも正しいから $$b_n=c_n=2^n$$である．

$n \geq 1$ のとき，$$w_n=\{ w_0, \dots , w_{n-1} \}$$と書ける．条件を満たすような２文字の選び方を，左括弧 $\{$ の位置で場合分けして数える．

• $\{ w_0, \dots , w_{n-1} \}$ の左端の $\{$ を選ぶとき

右括弧 $\}$ は $w_n$ に含まれるものならどれでもいいので，選び方は $$c_n \; \text{通り}$$である．

• $\{ w_0, \dots , w_{n-1} \}$ の $w_i$ の中の $\{$ を選ぶとき

$\{\}$ の作り方としてあり得るのは

1. 「 $w_i$ の中で $\{\}$ を作る」

もしくは

2. 「 $w_i$ から $\{$ を選び， $w_i$ より右側の$$,w_{i+1},\dots, w_{n-1}\}$$の部分から $\}$ を選ぶ」

のどちらかである．それぞれの選び方は$$x_i \; \text{通り}$$$$b_i \cdot (c_{i+1}+\cdots +c_{n-1}+1) \; \text{通り}$$ である．

以上を足し合わせることで，$n \geq 1$ のとき $$\begin{aligned} x_n&=c_n+\sum_{i=0}^{n-1}\left\{x_i+b_i \cdot (c_{i+1}+\cdots +c_{n-1}+1)\right\}\\ &=2^n + \sum_{i=0}^{n-1}2^i\cdot\left(2^{i+1}+\cdots+2^{n-1}+1 \right)+\sum_{i=0}^{n-1}x_i \end{aligned}$$ が成り立つ．これと$$x_{n+1}=2^{n+1} + \sum_{i=0}^{n}2^i\cdot\left(2^{i+1}+\cdots+2^{n-1}+2^n+1 \right)+\sum_{i=0}^nx_i$$の差をとると $$\begin{aligned} x_{n+1}-x_n&=2^{n+1}-2^n+\sum_{i=0}^{n-1}2^i\cdot2^n + 2^n \cdot 1 + x_n\\ &= 2^{n+1}+2^n\cdot \frac{2^n-1}{2-1}+x_n\\ &=x_n+2^n(2^n+1) \end{aligned}$$ となるから$$x_{n+1}=2x_n+2^n(2^n+1)$$ が $n \geq 1$ で成り立つ．また $n=0$ のときも $x_0=1,x_1=4$ だから正しい． $$\frac{x_{n+1}}{2^{n+1}}=\frac{x_n}{2^n}+\frac{1}{2}(2^n+1)$$と変形することで $n \geq 0$ のとき $$\begin{aligned} \frac{x_n}{2^n}&=\frac{x_0}{2^0}+\sum_{i=0}^{n-1}\frac{1}{2}(2^i+1)\\ &=1+\frac{1}{2}\cdot\frac{2^n-1}{2-1}+\frac{1}{2}n\\ &=1+\frac{1}{2}(2^n-1+n)\\ &=\frac{1}{2}(2^n+n+1) \end{aligned}$$ となる．よって$$x_n=(2^n+n+1)\;2^{n-1}$$である．

(1) $$l_n = \begin{cases} 5 \cdot 2^{n-1} - 1 & (n \geqq 1)\\ 2 & (n=0) \end{cases}$$

(2) $$\begin{aligned} a_n &= \begin{cases} 2^{n-1} - 1 & (n \geqq 1)\\ 0 & (n=0) \end{cases}\\ b_n &= 2^n\\ c_n &= 2^n \end{aligned}$$

(3)

$$x_n = (2^n+n+1) \; 2^{n-1}$$