4北海道大学 2011年 数学 第4問解答・解説

第1箱から第2箱へ球を移し、その後も第i箱から第i+1箱へ移して第n箱で終了する操作である。$m=q+r$ とおく。第1箱からは初期球を1個選んで送るので $m$ 通り。中間の第$i$箱（$2\le i\le n-1$）では、直前から来た球をそのまま送る1通り、または初期球のうち1個を送る $m$ 通りがある。番号付きの球を区別するため、これらの選択は最終配置を区別する。よって $$s_n=m(m+1)^{n-2}=(q+r)(q+r+1)^{n-2}.$$

第n箱は最後に球を1個受け取るだけなので、その白玉数が $q+1$ となるのは、そこへ届く球が白玉のときである。中間箱のうち、来た球でなく初期球を送る箱の番号の集合を $T$ とする。$T$ の要素は $2,\ldots,n-1$ の中から選ぶ。$T$ が空なら第1箱から届く球を白玉にする選び方は $q$ 通り。$T$ が空でないなら、最も番号の大きい箱 $\displaystyle \max T$ が第n箱へ届く球の出所なので、そこで白玉を選ぶ方法が $q$ 通り。他の出発箱は第1箱と $T$ から最大の番号を除いた箱で、合わせて $|T|$ 箱あり、それぞれ初期球を $m$ 通りに選べる。したがって固定した $T$ に対する数は $qm^{|T|}$ である。$T$ の要素が $j$ 個となる選び方は $\displaystyle \binom{n-2}{j}$ 通りだから、 $$\displaystyle a_n=\sum\limits _{j=0}^{n-2}\binom{n-2}{j}qm^j=q(1+m)^{n-2}=q(q+r+1)^{n-2}.$$ 特に $a_2=q$、$a_3=q(m+1)=q(q+r+1)$。また $$a_{n+1}-a_n=q(m+1)^{n-1}-q(m+1)^{n-2}=qm(m+1)^{n-2}=q(q+r)(q+r+1)^{n-2}.$$ 差の式と初期値 $a_2=q$ からも $$\displaystyle a_n=q+qm\sum\limits _{j=2}^{n-1}(m+1)^{j-2}=q(m+1)^{n-2}=q(q+r+1)^{n-2}$$ を得る（$n=2$ では和は空）。