北海道大学 2007年 理系 第2問 解説

方針・初手

与えられた条件 $a_1 \leqq a_2 \leqq \cdots \leqq a_n$ は、数列が単調非減少であることを示しています。 (1) は末尾の項 $a_n$ の値を固定し、漸化式または場合の数を直接考えることで求められます。(ii) では問題の指示に従い、$a_{n-1}$ の値で場合分けして $A_n(j)$ と $A_{n-1}(k)$ の関係式を導きます。 (2) は、(1) で求めた $A_{n-1}(j)$ の結果を利用します。条件が $a_{n-1}$ までと $a_n$ とで分かれているため、$a_{n-1}$ の値を固定して条件を満たす $a_n$ の個数を掛けることで、場合の数を数え上げます。

解法1

(1)(i)

$A_n(1)$ について考える。 条件より $1 \leqq a_1 \leqq a_2 \leqq \cdots \leqq a_n = 1$ であるから、すべての項は $1$ になるしかない。 すなわち、$a_1 = a_2 = \cdots = a_n = 1$ となる $1$ 通りのみである。 したがって、

$$ A_n(1) = 1 $$

である。

次に、$A_n(2)$ について考える。 条件より $a_n = 2$ であり、各項は $1$ または $2$ のいずれかである。 数列は単調非減少であるから、ある項まで $1$ が続き、それ以降は $2$ になる。 数列 $a_1, a_2, \dots, a_{n-1}$ において、$1$ となる項の個数を $k$ とすると、$k$ は $0$ 個から $n-1$ 個までのいずれかであり、その選び方は $n$ 通り存在する。 したがって、

$$ A_n(2) = n $$

である。

(1)(ii)

$n \geqq 2$ のとき、条件を満たす長さ $n$、末尾が $j$ の数列について、$n-1$ 番目の項 $a_{n-1}$ に注目する。 数列が単調非減少であるため、$a_{n-1}$ は $1$ 以上 $j$ 以下の整数をとる。 $a_{n-1} = k$ ($1 \leqq k \leqq j$) となるような数列の部分列 $a_1, a_2, \dots, a_{n-1}$ の総数は、$A_{n-1}(k)$ 通りである。 これらをすべて足し合わせることで $A_n(j)$ が得られるため、

$$ A_n(j) = A_{n-1}(1) + A_{n-1}(2) + \cdots + A_{n-1}(j) $$

と表せる。

これを用いて $A_n(3)$ を求める。

$$ A_n(3) = A_{n-1}(1) + A_{n-1}(2) + A_{n-1}(3) $$

より、

$$ A_n(3) - A_{n-1}(3) = A_{n-1}(1) + A_{n-1}(2) = 1 + (n-1) = n $$

となる。数列 $\{ A_n(3) \}$ の階差数列が $n$ であるから、$n \geqq 2$ のとき、

$$ \begin{aligned} A_n(3) &= A_1(3) + \sum_{k=2}^{n} k \\ &= 1 + \frac{(n-1)(2+n)}{2} \\ &= \frac{n(n+1)}{2} \end{aligned} $$

を得る。（これは $n=1$ のときも $A_1(3) = 1$ となり成り立つ。）

同様に $A_n(4)$ を求める。

$$ A_n(4) = A_{n-1}(1) + A_{n-1}(2) + A_{n-1}(3) + A_{n-1}(4) $$

より、

$$ A_n(4) - A_{n-1}(4) = A_n(3) = \frac{n(n+1)}{2} $$

となる。数列 $\{ A_n(4) \}$ の階差数列が $\frac{n(n+1)}{2}$ であるから、$n \geqq 2$ のとき、

$$ \begin{aligned} A_n(4) &= A_1(4) + \sum_{k=2}^{n} \frac{k(k+1)}{2} \\ &= 1 + \left( \sum_{k=1}^{n} \frac{k(k+1)}{2} - 1 \right) \\ &= \frac{n(n+1)(n+2)}{6} \end{aligned} $$

を得る。（これも $n=1$ のとき $A_1(4) = 1$ となり成り立つ。）

(2)

$1$ 回の試行で $4$ 種類の数字が等確率で出るため、$n$ 回の試行で得られる数列の総数は $4^n$ 通りである。

条件 $a_1 \leqq a_2 \leqq \cdots \leqq a_{n-1}$ かつ $a_{n-1} > a_n$ を満たす数列の個数を考える。 $n-1$ 番目の項 $a_{n-1}$ の値を $j$ と固定する。 条件 $a_{n-1} > a_n$ より、$j > a_n \geqq 1$ を満たす必要があるため、$j$ は $2, 3, 4$ のいずれかである。

$a_{n-1} = j$ のとき、 前半の条件 $a_1 \leqq a_2 \leqq \cdots \leqq a_{n-1} = j$ を満たす部分列 $a_1, \dots, a_{n-1}$ の個数は、$A_{n-1}(j)$ 通りである。 また、後半の条件 $a_{n-1} > a_n$ を満たす $a_n$ の選び方は、$1 \leqq a_n \leqq j-1$ の $(j-1)$ 通りである。

したがって、条件を満たす数列の総数は、各 $j$ の場合を足し合わせて、

$$ \sum_{j=2}^{4} A_{n-1}(j) \times (j-1) $$

となる。それぞれを計算すると、

$$ \begin{aligned} j=2 \text{ のとき} &: A_{n-1}(2) \times 1 = n-1 \\ j=3 \text{ のとき} &: A_{n-1}(3) \times 2 = \frac{(n-1)n}{2} \times 2 = n(n-1) \\ j=4 \text{ のとき} &: A_{n-1}(4) \times 3 = \frac{(n-1)n(n+1)}{6} \times 3 = \frac{(n-1)n(n+1)}{2} \end{aligned} $$

これらを合計すると、

$$ \begin{aligned} & (n-1) + n(n-1) + \frac{(n-1)n(n+1)}{2} \\ &= (n-1) \left\{ 1 + n + \frac{n(n+1)}{2} \right\} \\ &= (n-1) \left( \frac{n^2 + 3n + 2}{2} \right) \\ &= \frac{(n-1)(n+1)(n+2)}{2} \end{aligned} $$

以上より、求める確率は、

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

である。

解説

単調非減少な数列の個数を数える典型的な問題です。 (1) では誘導に従って階差数列を利用して一般項を求めましたが、単調非減少な数列の総数は「重複組合せ」を用いて計算することもできます。 $1$ から $j$ までの数字から重複を許して $n-1$ 個選び、それらを小さい順に $a_1, \dots, a_{n-1}$ に割り当てる方法の数と考えれば、$A_n(j) = {}_{j}\mathrm{H}_{n-1} = {}_{n+j-2}\mathrm{C}_{j-1}$ と直ちに一般化できます。 (2) は、直前までの事象と最後の事象を分けて掛け合わせるという、確率・場合の数の基本に忠実な処理が求められます。事象が排反であること（$a_{n-1}$ の値で場合分けしていること）と、独立な選択（前段の数列の形と $a_n$ の値の選び方）を整理して立式できるかが鍵となります。

答え

(1)(i) $A_n(1) = 1, \ A_n(2) = n$ (1)(ii) $A_n(j) = A_{n-1}(1) + A_{n-1}(2) + \cdots + A_{n-1}(j)$ $A_n(3) = \frac{n(n+1)}{2}, \ A_n(4) = \frac{n(n+1)(n+2)}{6}$ (2) $\frac{(n-1)(n+1)(n+2)}{2 \cdot 4^n}$