北海道大学 2007年度 前期日程 第2次学力試験理系数学 第2問

(1)
(i)
最後が1で非減少ならば，すべての項が1である。したがって $A_n(1)=1$ である。
最後が2で非減少ならば，列は1がいくつか並んだ後に2が並ぶ形である。最後は必ず2なので，1の個数は $0,1,\dots ,n-1$ の $n$ 通りである。よって $A_n(2)=n$ である。
(ii) $n\geqq 2$ とする。$a_n=j$ で非減少である列は，直前までの最後の値が1から $j$ のいずれかである。したがって $$A_n(j)=A_{n-1}(1)+A_{n-1}(2)+\cdots +A_{n-1}(j)$$ である。
また，$A_n(j)$ は最後の $j$ を1つ固定し，残り $n-1$ 個に1から $j$ までの数字を非減少に並べる方法の数である。したがって個数の分配で数えると $$A_n(3)={}_{n+1}{\mathrm{C}}_2={\displaystyle \frac{n(n+1)}{2}}$$ であり，$$A_n(4)={}_{n+2}{\mathrm{C}}_3={\displaystyle \frac{n(n+1)(n+2)}{6}}$$ である。
(2) $m=n-1$ とおく。最初の $m$ 個が非減少で，その最後の値が $j$ であるとする。このとき $a_n$ は $1,2,\dots ,j-1$ の $j-1$ 通りから選べる。
したがって条件を満たす数列の個数は $A_m(2)+2A_m(3)+3A_m(4)$ である。ここに(1)の結果を代入すると$$\begin{array}{rl}{\displaystyle }& {\displaystyle m+2\cdot {\displaystyle \frac{m(m+1)}{2}}+3\cdot {\displaystyle \frac{m(m+1)(m+2)}{6}}}\\ {\displaystyle }& {\displaystyle =m+m(m+1)+{\displaystyle \frac{m(m+1)(m+2)}{2}}}\end{array}$$である。$m=n-1$ として整理すると ${\displaystyle \frac{(n-1)(n+1)(n+2)}{2}}$ となる。
全事象は，$n$ 回それぞれ4通りなので $4^n$ 通りである。よって求める確率は ${\displaystyle \frac{(n-1)(n+1)(n+2)}{2\cdot 4^n}}$ である。

非減少列は，直前の末尾の値を累積して次の個数を作る。