2北海道大学 2007年 数学 第2問解答・解説

末項が1である列はすべて1なので、$A_n(1)=1$。末項が2である列は、先頭に並ぶ1の個数を0個から$n-1$個まで選べば定まり、$A_n(2)=n$である。

$n\ge2$、$j=3,4$とする。末項の直前の値を$k$とすると、$1\le k\le j$であり、最初の$n-1$項の選び方は$A_{n-1}(k)$通りだから、 $$\displaystyle A_n(j)=\sum\limits _{k=1}^{j}A_{n-1}(k).$$ したがって $$A_n(3)=A_{n-1}(3)+A_{n-1}(1)+A_{n-1}(2)=A_{n-1}(3)+n.$$ $A_1(3)=1$であり、$\displaystyle \frac{n(n+1)}2-\frac{(n-1)n}2=n$だから、漸化式と初項より $$\displaystyle A_n(3)=\frac{n(n+1)}2.$$ また、$A_n(4)=A_{n-1}(4)+A_n(3)$である。$A_1(4)=1$であり、$\displaystyle \frac{n(n+1)(n+2)}6-\frac{(n-1)n(n+1)}6=\frac{n(n+1)}2=A_n(3)$だから、 $$\displaystyle A_n(4)=\frac{n(n+1)(n+2)}6.$$

事象の条件を満たす列を数える。$a_{n-1}=j$なら、最初の$n-1$項は$A_{n-1}(j)$通りで、その後に$a_n$を$1,2,\ldots,j-1$から選ぶので、列数は$(j-1)A_{n-1}(j)$通りである。よって事象を満たす列数は $$\displaystyle \begin{aligned} N_n&=\sum\limits _{j=1}^{4}(j-1)A_{n-1}(j)\\ &=(n-1)+2\cdot\frac{n(n-1)}2+3\cdot\frac{(n-1)n(n+1)}6\\ &=\frac{(n-1)(n+1)(n+2)}2. \end{aligned}$$ 各試行で4通りの数字が等確率で選ばれ、復元抽出なので、長さ$n$の列は全部で$4^n$通りあり、いずれも同確率である。したがって求める確率は $$\displaystyle \frac{N_n}{4^n}=\frac{(n-1)(n+1)(n+2)}{2\cdot4^n}.$$

$A_n(j)$ は非減少な長さ $n$ の列で末項が $j$ の個数。$j=1$ は全項1で1通り、$j=2$ は1の個数を0から $n-1$ まで選べるため $n$ 通り。$j=3,4$ は末尾 $j$ を一つ確保し、残る $n-1$ 個を1から $j$ の値の個数に分配するので、仕切りの数え上げから $\displaystyle \binom{n+1}{2},\binom{n+2}{3}$。最後の小問では $a_{n-1}=j$ ごとに前半 $A_{n-1}(j)$ 通り、最後は $j-1$ 通り。合計有利列は $\displaystyle \frac{(n-1)(n+1)(n+2)}2$ で、全 $4^n$ 列が等確率。