1東京医科歯科大学 2014年 数学 第1問解答・解説

(2) $C_{12}$ を満たさない列を数える。2が一つもない列は $2^n$ 個。2がある場合、最後の2の位置を $j$ とする。位置 $1,\ldots,j-1$ には1が現れないので各項は2または3、位置 $j+1,\ldots,n$ には2が現れないので各項は1または3である。よってこの場合の個数は各 $j$ につき $2^{j-1}2^{n-j}=2^{n-1}$ 個であり、$j=1,\ldots,n$ を足して $n2^{n-1}$ 個。したがって $f(n)=2^n+n2^{n-1}=(n+2)2^{n-1}$。特に $f(4)=48$。

(3) 長さ $n+1$ の列の最初の項で場合分けする。最初が1なら、残りの列に「2の後に3」があることと全体が $C_{123}$ を満たすことは同値である。残りがそのような2項列を含まない個数は、数字の置換対称性により $f(n)$。最初が2または3なら、その最初の項は $1,2,3$ の順の組に使えず、$C_{123}$ の有無は残りの長さ $n$ の列だけで決まるので各場合 $g(n)$ 個。ゆえに $g(n+1)=f(n)+2g(n)$。

(1) $f(1)=3$, $f(2)=8$, $f(3)=20$ であり、$g(1)=3$。上の漸化式から $g(2)=3+2\cdot3=9$, $g(3)=8+2\cdot9=26$, $g(4)=20+2\cdot26=72$。従って $f(4)=48$, $g(4)=72$。

(4) $h(n)=g(n)/2^n$ と置くと、漸化式と $f(n)=(n+2)2^{n-1}$ から $h(n+1)-h(n)=f(n)/2^{n+1}=(n+2)/4$。また $h(1)=3/2$ だから、$\displaystyle h(n)=3/2+\frac14\sum\limits _{j=1}^{n-1}(j+2)=3/2+\frac{n^2+3n-4}{8}=\frac{n^2+3n+8}{8}$。よって $\displaystyle g(n)=\frac{2^n(n^2+3n+8)}{8}$。