北海道大学 2007年度文系数学前期第3問解答・解説

問題

数 $1, 2, 3$ を重複を許して $n$ 個並べてできる数列 $a_{1}, a_{2}, \dots, a_{n}$ を考える．

(1) 条件 $a_{1} ≦ a_{2} ≦ \dots ≦ a_{n} = j$ を満たす数列が $A_{n} (j)$ 通りあるとする．ただし， $j = 1, 2, 3$ とする．

(i) $A_{n} (1)$ ， $A_{n} (2)$ を求めよ．

(ii) $n ≧ 2$ のとき， $A_{n} (3)$ を $A_{n - 1} (1)$ ， $A_{n - 1} (2)$ ， $A_{n - 1} (3)$ で表し， $A_{n} (3)$ を求めよ．

(2) $n ≧ 2$ のとき，条件 $a_{1} ≦ a_{2} ≦ \dots ≦ a_{n - 1}$ かつ $a_{n - 1} > a_{n}$ を満たす数列は何通りあるか．

出典：北海道大学 2007年度前期日程第2次学力試験文系前期第3問

方針

非減少列は，1の個数，2の個数，3の個数を決めれば一意に定まる。 $A_{n} (1)$ ， $A_{n} (2)$ は直接数え， $A_{n} (3)$ は最後の3を除いた長さ $n - 1$ の非減少列を数えるか，漸化式から求める。(2)は $a_{n - 1}$ の値が2または3の場合に分け，最後の $a_{n}$ をそれより小さい値から選ぶ。

解答

(1)(i)

$a_{1} ≦ a_{2} ≦ \dots ≦ a_{n} = 1$ なら，すべての項が1でなければならない。したがって $A_{n} (1) = 1$ である。 $a_{1} ≦ \dots ≦ a_{n} = 2$ の場合，列は

r 個 1, \dots, 1, n - r 個 2, \dots, 2

の形で，最後が2なので $0 ≦ r ≦ n - 1$ である。よって $A_{n} (2) = n$ である。

(1)(ii)

$n ≧ 2$ とする。最後の項が3である非減少列の，直前までの最後の値は1,2,3のいずれかである。したがって $A_{n} (3) = A_{n - 1} (1) + A_{n - 1} (2) + A_{n - 1} (3)$ である。

また， $A_{n} (3)$ を直接数えると，最後の3を1つ固定した後，残り $n - 1$ 個の中に1,2,3がそれぞれ何個あるかを決めればよい。1,2,3の個数を $r_{1}, r_{2}, r_{3}$ とすると $r_{1} + r_{2} + r_{3} = n - 1$ であり，非負整数解の個数は $_{n + 1} C_{2} = \frac{n ( n + 1 )}{2}$ である。よって $A_{n} (3) = \frac{n ( n + 1 )}{2}$ である。

(2)

$a_{1} ≦ \dots ≦ a_{n - 1}$ であり，さらに $a_{n - 1} > a_{n}$ である。 $a_{n - 1} = 1$ では最後にそれより小さい数を選べないので不可能である。 $a_{n - 1} = 2$ のとき，前半 $a_{1}, \dots, a_{n - 1}$ は $A_{n - 1} (2) = n - 1$ 通りで， $a_{n}$ は1のみである。したがって $n - 1$ 通りである。 $a_{n - 1} = 3$ のとき，前半は $A_{n - 1} (3) = \frac{( n - 1 ) n}{2}$ 通りで， $a_{n}$ は1または2の2通りである。したがって $2 \cdot \frac{( n - 1 ) n}{2} = n (n - 1)$ 通りである。

合計して $(n - 1) + n (n - 1) = (n - 1) (n + 1) = n^{2} - 1$ 通りである。

北海道大学 2007年度文系数学 前期 第3問

問題

方針

解答

(1)(i)

(1)(ii)

(2)

北海道大学 2007年度
文系数学前期第3問